AggressiveInstCombine.cpp Source File (original) (raw)

36using namespace llvm;

37using namespace PatternMatch;

39#define DEBUG_TYPE "aggressive-instcombine"

41 STATISTIC(NumAnyOrAllBitsSet, "Number of any/all-bits-set patterns folded");

43 "Number of guarded rotates transformed into funnel shifts");

45 "Number of guarded funnel shifts transformed into funnel shifts");

46 STATISTIC(NumPopCountRecognized, "Number of popcount idioms recognized");

50 cl::desc("Max number of instructions to scan for aggressive instcombine."));

54 cl::desc("The maximum length of a constant string for a builtin string cmp "

55 "call eligible for inlining. The default value is 3."));

59 cl::desc("The maximum length of a constant string to "

60 "inline a memchr call."));

66 if (I.getOpcode() != Instruction::PHI || I.getNumOperands() != 2)

67 return false;

73 if ( $isPowerOf2\_32$ (I.getType()->getScalarSizeInBits()))

74 return false;

80 unsigned Width = V->getType()->getScalarSizeInBits();

88 return Intrinsic::fshl;

89 }

97 return Intrinsic::fshr;

98 }

101 };

102

103

104

105

106

107

108 PHINode &Phi = cast(I);

109 unsigned FunnelOp = 0, GuardOp = 1;

110 Value *P0 = Phi.getOperand(0), *P1 = Phi.getOperand(1);

111 Value *ShVal0, *ShVal1, *ShAmt;

114 (IID == Intrinsic::fshl && ShVal0 != P1) ||

115 (IID == Intrinsic::fshr && ShVal1 != P1)) {

118 (IID == Intrinsic::fshl && ShVal0 != P0) ||

119 (IID == Intrinsic::fshr && ShVal1 != P0))

120 return false;

121 assert((IID == Intrinsic::fshl || IID == Intrinsic::fshr) &&

122 "Pattern must match funnel shift left or right");

124 }

125

126

127

128

129

130 BasicBlock *GuardBB = Phi.getIncomingBlock(GuardOp);

131 BasicBlock *FunnelBB = Phi.getIncomingBlock(FunnelOp);

133

134

136 return false;

137

142 return false;

143

145

146 if (ShVal0 == ShVal1)

147 ++NumGuardedRotates;

148 else

149 ++NumGuardedFunnelShifts;

150

151

152

153 bool IsFshl = IID == Intrinsic::fshl;

154 if (ShVal0 != ShVal1) {

159 }

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175 Phi.replaceAllUsesWith(

176 Builder.CreateIntrinsic(IID, Phi.getType(), {ShVal0, ShVal1, ShAmt}));

177 return true;

178}

179

180

181

182

183

184namespace {

185struct MaskOps {

186 Value *Root = nullptr;

188 bool MatchAndChain;

189 bool FoundAnd1 = false;

190

191 MaskOps(unsigned BitWidth, bool MatchAnds)

193};

194}

195

196

197

198

199

200

201

202

204 Value *Op0, *Op1;

205 if (MOps.MatchAndChain) {

206

207

208

210 MOps.FoundAnd1 = true;

212 }

215 } else {

216

219 }

220

221

222

223 Value *Candidate;

224 const APInt *BitIndex = nullptr;

226 Candidate = V;

227

228

229 if (!MOps.Root)

230 MOps.Root = Candidate;

231

232

233 if (BitIndex && BitIndex->uge(MOps.Mask.getBitWidth()))

234 return false;

235

236

237 MOps.Mask.setBit(BitIndex ? BitIndex->getZExtValue() : 0);

238 return MOps.Root == Candidate;

239}

240

241

242

243

244

245

246

247

248

250

251

252 bool MatchAllBitsSet;

254 MatchAllBitsSet = true;

256 MatchAllBitsSet = false;

257 else

258 return false;

259

260 MaskOps MOps(I.getType()->getScalarSizeInBits(), MatchAllBitsSet);

261 if (MatchAllBitsSet) {

262 if ( matchAndOrChain (cast(&I), MOps) || !MOps.FoundAnd1)

263 return false;

264 } else {

265 if ( matchAndOrChain (cast(&I)->getOperand(0), MOps))

266 return false;

267 }

268

269

270

272 Constant *Mask = ConstantInt::get(I.getType(), MOps.Mask);

277 I.replaceAllUsesWith(Zext);

278 ++NumAnyOrAllBitsSet;

279 return true;

280}

281

282

283

284

285

286

287

288

289

290

291

292

294 if (I.getOpcode() != Instruction::LShr)

295 return false;

296

297 Type *Ty = I.getType();

299 return false;

300

302

303 if (!(Len <= 128 && Len > 8 && Len % 8 == 0))

304 return false;

305

311

312 Value *Op0 = I.getOperand(0);

313 Value *Op1 = I.getOperand(1);

315

319

324

325 if (match(ShiftOp0,

329 Value *Root, *SubOp1;

330

334 LLVM_DEBUG(dbgs() << "Recognized popcount intrinsic\n");

336 I.replaceAllUsesWith(

337 Builder.CreateIntrinsic(Intrinsic::ctpop, I.getType(), {Root}));

338 ++NumPopCountRecognized;

339 return true;

340 }

341 }

342 }

343 }

344

345 return false;

346}

347

348

349

350

351

352

353

354

355

357

359 const APInt *MinC, *MaxC;

366 return false;

367

368

369 if (!(*MinC + 1).isPowerOf2() || -*MaxC != *MinC + 1)

370 return false;

371

372 Type *IntTy = I.getType();

373 Type *FpTy = In->getType();

374 Type *SatTy =

376 if (auto *VecTy = dyn_cast(IntTy))

377 SatTy = VectorType::get(SatTy, VecTy->getElementCount());

378

379

380

387

397

398 if (SatCost >= MinMaxCost)

399 return false;

400

403 Builder.CreateIntrinsic(Intrinsic::fptosi_sat, {SatTy, FpTy}, In);

404 I.replaceAllUsesWith(Builder.CreateSExt(Sat, IntTy));

405 return true;

406}

407

408

409

410

414

415

416

417

418

419

420 Type *Ty = Call->getType();

421 Value *Arg = Call->getArgOperand(0);

423 (Call->hasNoNaNs() ||

425 Arg, 0,

426 SimplifyQuery(Call->getDataLayout(), &TLI, &DT, &AC, Call)))) {

429 Builder.CreateIntrinsic(Intrinsic::sqrt, Ty, Arg, Call, "sqrt");

430 Call->replaceAllUsesWith(NewSqrt);

431

432

433

434 Call->eraseFromParent();

435 return true;

436 }

437

438 return false;

439}

440

441

442

443

447 if (Length < InputBits || Length > InputBits * 2)

448 return false;

449

451 unsigned Matched = 0;

452

453 for (unsigned i = 0; i < Length; i++) {

455 if (Element >= InputBits)

456 continue;

457

458

459

460

461

462 if ((((Mul << Element) & Mask.getZExtValue()) >> Shift) == i)

463 Matched++;

464 }

465

466 return Matched == InputBits;

467}

468

469

470

471

472

473

474

475

476

477

478

479

480

481

482

483

484

485

486

487

488

489

490

491

492

493

494

495

496

497

498

499

500

501

502

503

504

505

506

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521

522

524 LoadInst *LI = dyn_cast(&I);

525 if (!LI)

526 return false;

527

530 return false;

531

533 if ( GEP || GEP ->isInBounds() || GEP->getNumIndices() != 2)

534 return false;

535

536 if ( GEP ->getSourceElementType()->isArrayTy())

537 return false;

538

539 uint64_t ArraySize = GEP->getSourceElementType()->getArrayNumElements();

540 if (ArraySize != 32 && ArraySize != 64)

541 return false;

542

543 GlobalVariable *GVTable = dyn_cast(GEP->getPointerOperand());

545 return false;

546

548 dyn_cast(GVTable->getInitializer());

549 if (!ConstData)

550 return false;

551

553 return false;

554

555 Value *Idx2 = std::next(GEP->idx_begin())->get();

557 uint64_t MulConst, ShiftConst;

558

559

564 return false;

565

567 if (InputBits != 32 && InputBits != 64)

568 return false;

569

570

571 if (InputBits - Log2_32(InputBits) != ShiftConst &&

572 InputBits - Log2_32(InputBits) - 1 != ShiftConst)

573 return false;

574

575 if ( isCTTZTable (*ConstData, MulConst, ShiftConst, InputBits))

576 return false;

577

579 bool DefinedForZero = ZeroTableElem == InputBits;

580

582 ConstantInt *BoolConst = B.getInt1(!DefinedForZero);

584 auto Cttz = B.CreateIntrinsic(Intrinsic::cttz, {XType}, {X1, BoolConst});

585 Value *ZExtOrTrunc = nullptr;

586

587 if (DefinedForZero) {

588 ZExtOrTrunc = B.CreateZExtOrTrunc(Cttz, AccessType);

589 } else {

590

591

592 auto Cmp = B.CreateICmpEQ(X1, ConstantInt::get(XType, 0));

594 B.CreateSelect(Cmp, ConstantInt::get(XType, ZeroTableElem), Cttz);

595

596

597

598

599 ZExtOrTrunc = B.CreateZExtOrTrunc(Select, AccessType);

600 }

601

603

604 return true;

605}

606

607

608

609

618};

619

620

621

622

625 const APInt *ShAmt2 = nullptr;

628

629

637

638 return false;

639 } else

640 return false;

641

642

649 LI1 = dyn_cast(L1);

650 }

651 LoadInst *LI2 = dyn_cast(L2);

652

653

654 if (LI1 == LI2 || !LI1 || !LI2 || !LI1->isSimple() || !LI2->isSimple() ||

656 return false;

657

658

660 return false;

661

662

663 bool IsBigEndian = DL.isBigEndian();

664

665

667 APInt Offset1(DL.getIndexTypeSizeInBits(Load1Ptr->getType()), 0);

668 Load1Ptr =

670 true);

671

673 APInt Offset2(DL.getIndexTypeSizeInBits(Load2Ptr->getType()), 0);

674 Load2Ptr =

676 true);

677

678

681 if (Load1Ptr != Load2Ptr || LoadSize1 != LoadSize2)

682 return false;

683

684

686 return false;

687

688

691 if (!Start->comesBefore(End)) {

696 } else

698 unsigned NumScanned = 0;

700 make_range(Start->getIterator(), End->getIterator())) {

702 return false;

703

704

705

706 if (!isa(Inst) && ++NumScanned > MaxInstrsToScan)

707 return false;

708 }

709

710

712 if (Offset2.slt(Offset1)) {

719 }

720

721

722 if (IsBigEndian)

724

725

726 uint64_t Shift1 = 0, Shift2 = 0;

727 if (ShAmt1)

729 if (ShAmt2)

731

732

733

737 else

739 }

740

741

742

743 uint64_t ShiftDiff = IsBigEndian ? LoadSize2 : LoadSize1;

746 if ((Shift2 - Shift1) != ShiftDiff || (Offset2 - Offset1) != PrevSize)

747 return false;

748

749

755 }

756 LOps.LoadSize = LoadSize1 + LoadSize2;

758

759

761

762 LOps.Root = LI1;

763 LOps.Shift = ShAmt1;

765 return true;

766}

767

768

769

770

774

775 if (isa(I.getType()))

776 return false;

777

780 return false;

781

783 LoadInst *NewLoad = nullptr, *LI1 = LOps.Root;

784

786

788 if (!Allowed)

789 return false;

790

791 unsigned AS = LI1->getPointerAddressSpace();

792 unsigned Fast = 0;

794 AS, LI1->getAlign(), &Fast);

795 if (!Allowed || Fast )

796 return false;

797

798

799 Value *Load1Ptr = LI1->getPointerOperand();

802 APInt Offset1(DL.getIndexTypeSizeInBits(Load1Ptr->getType()), 0);

804 DL, Offset1, true);

806 }

807

808 NewLoad = Builder.CreateAlignedLoad(WiderType, Load1Ptr, LI1->getAlign(),

809 LI1->isVolatile(), "");

811

814

815 Value *NewOp = NewLoad;

816

819

820

821

823 NewOp = Builder.CreateShl(NewOp, ConstantInt::get(I.getContext(), *LOps.Shift));

824 I.replaceAllUsesWith(NewOp);

825

826 return true;

827}

828

829

830

831static std::pair<APInt, APInt>

833 unsigned BW = DL.getIndexTypeSizeInBits(PtrOp->getType());

834 std::optional Stride;

835 APInt ModOffset(BW, 0);

836

837

838 while (auto *GEP = dyn_cast(PtrOp)) {

840 if ( GEP ->collectOffset(DL, BW, VarOffsets, ModOffset))

841 break;

842

843 for (auto [V, Scale] : VarOffsets) {

844

845 if ( GEP ->isInBounds())

847

848 if (!Stride)

849 Stride = Scale;

850 else

852 }

853

854 PtrOp = GEP->getPointerOperand();

855 }

856

857

858

859 if (!isa(PtrOp) || !Stride)

861

862

863

864 ModOffset = ModOffset.srem(*Stride);

866 ModOffset += *Stride;

867

868 return {*Stride, ModOffset};

869}

870

871

872

874 auto *LI = dyn_cast(&I);

875 if (!LI || LI->isVolatile())

876 return false;

877

878

879

880 auto *PtrOp = LI->getPointerOperand();

882 if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer())

883 return false;

884

885

886 Constant *C = GV->getInitializer();

887 uint64_t GVSize = DL.getTypeAllocSize(C->getType());

888 if (!GVSize || 4096 < GVSize)

889 return false;

890

891 Type *LoadTy = LI->getType();

892 unsigned BW = DL.getIndexTypeSizeInBits(PtrOp->getType());

894

895

896

897

898 if (auto LA = LI->getAlign();

899 LA <= GV->getAlign().valueOrOne() && Stride.getZExtValue() < LA.value()) {

900 ConstOffset = APInt(BW, 0);

901 Stride = APInt(BW, LA.value());

902 }

903

905 if (!Ca)

906 return false;

907

908 unsigned E = GVSize - DL.getTypeStoreSize(LoadTy);

909 for (; ConstOffset.getZExtValue() <= E; ConstOffset += Stride)

911 return false;

912

913 I.replaceAllUsesWith(Ca);

914

915 return true;

916}

917

918namespace {

919class StrNCmpInliner {

920public:

924

925 bool optimizeStrNCmp();

926

927private:

929

934};

935

936}

937

938

939

940

941

942

943

944

945

946

947

948

949

950

951

952

953

954

955

956

957

958

959

960

961

962

963

964

965

966bool StrNCmpInliner::optimizeStrNCmp() {

968 return false;

969

971 return false;

972

973 Value *Str1P = CI->getArgOperand(0);

974 Value *Str2P = CI->getArgOperand(1);

975

976 if (Str1P == Str2P)

977 return false;

978

982 if (HasStr1 == HasStr2)

983 return false;

984

985

986 StringRef Str = HasStr1 ? Str1 : Str2;

987 Value *StrP = HasStr1 ? Str2P : Str1P;

988

989 size_t Idx = Str.find('\0');

991 if (Func == LibFunc_strncmp) {

992 if (auto *ConstInt = dyn_cast(CI->getArgOperand(2)))

993 N = std::min(N, ConstInt->getZExtValue());

994 else

995 return false;

996 }

997

999 return false;

1000

1001

1002

1003 bool CanBeNull = false, CanBeFreed = false;

1005 return false;

1006 inlineCompare(StrP, Str, N, HasStr1);

1007 return true;

1008}

1009

1010

1011

1012

1013

1014

1015

1016

1017

1018

1019

1020

1021

1022

1023

1024

1025

1026

1027

1028

1029

1030

1031

1032

1033

1034

1035

1036

1037

1038

1039

1040

1041

1042

1043

1045 bool Swapped) {

1046 auto &Ctx = CI->getContext();

1048

1049

1050

1051

1052

1053

1054 B.SetCurrentDebugLocation(CI->getDebugLoc());

1055

1058 SplitBlock(BBCI, CI, DTU, nullptr, nullptr, BBCI->getName() + ".tail");

1059

1065

1066 cast(BBCI->getTerminator())->setSuccessor(0, BBSubs[0]);

1067

1068 B.SetInsertPoint(BBNE);

1069 PHINode *Phi = B.CreatePHI(CI->getType(), N);

1070 B.CreateBr(BBTail);

1071

1073 for (uint64_t i = 0; i < N; ++i) {

1074 B.SetInsertPoint(BBSubs[i]);

1076 B.CreateZExt(B.CreateLoad(B.getInt8Ty(),

1077 B.CreateInBoundsPtrAdd(Base, B.getInt64(i))),

1078 CI->getType());

1080 ConstantInt::get(CI->getType(), static_cast<unsigned char>(RHS[i]));

1081 Value *Sub = Swapped ? B.CreateSub(VR, VL) : B.CreateSub(VL, VR);

1082 if (i < N - 1)

1083 B.CreateCondBr(B.CreateICmpNE(Sub, ConstantInt::get(CI->getType(), 0)),

1084 BBNE, BBSubs[i + 1]);

1085 else

1086 B.CreateBr(BBNE);

1087

1088 Phi->addIncoming(Sub, BBSubs[i]);

1089 }

1090

1091 CI->replaceAllUsesWith(Phi);

1092 CI->eraseFromParent();

1093

1094 if (DTU) {

1096 Updates.push_back({DominatorTree::Insert, BBCI, BBSubs[0]});

1097 for (uint64_t i = 0; i < N; ++i) {

1098 if (i < N - 1)

1099 Updates.push_back({DominatorTree::Insert, BBSubs[i], BBSubs[i + 1]});

1100 Updates.push_back({DominatorTree::Insert, BBSubs[i], BBNE});

1101 }

1102 Updates.push_back({DominatorTree::Insert, BBNE, BBTail});

1103 Updates.push_back({DominatorTree::Delete, BBCI, BBTail});

1104 DTU->applyUpdates(Updates);

1105 }

1106}

1107

1108

1111 if (isa(Call->getArgOperand(1)))

1112 return false;

1113

1115 Value *Base = Call->getArgOperand(0);

1117 return false;

1118

1120 if (auto *ConstInt = dyn_cast(Call->getArgOperand(2))) {

1121 uint64_t Val = ConstInt->getZExtValue();

1122

1123 if (Val > N)

1124 return false;

1125 N = Val;

1126 } else

1127 return false;

1128

1130 return false;

1131

1138 IRB.CreateTrunc(Call->getArgOperand(1), ByteTy), BBNext, N);

1139 Type *IndexTy = DL.getIndexType(Call->getType());

1141

1143 Call->getContext(), "memchr.success", BB->getParent(), BBNext);

1148 if (DTU)

1149 Updates.push_back({DominatorTree::Insert, BBSuccess, BBNext});

1150

1153 ConstantInt *CaseVal = ConstantInt::get(ByteTy, Str[I]);

1154 if (!Cases.insert(CaseVal).second)

1155 continue;

1156

1159 SI->addCase(CaseVal, BBCase);

1161 IndexPHI->addIncoming(ConstantInt::get(IndexTy, I), BBCase);

1163 if (DTU) {

1164 Updates.push_back({DominatorTree::Insert, BB, BBCase});

1165 Updates.push_back({DominatorTree::Insert, BBCase, BBSuccess});

1166 }

1167 }

1168

1172 PHI->addIncoming(FirstOccursLocation, BBSuccess);

1173

1174 Call->replaceAllUsesWith(PHI);

1175 Call->eraseFromParent();

1176

1177 if (DTU)

1179

1180 return true;

1181}

1182

1186 bool &MadeCFGChange) {

1187

1188 auto *CI = dyn_cast(&I);

1189 if (!CI || CI->isNoBuiltin())

1190 return false;

1191

1192 Function *CalledFunc = CI->getCalledFunction();

1193 if (!CalledFunc)

1194 return false;

1195

1197 if (!TLI.getLibFunc(*CalledFunc, LF) ||

1199 return false;

1200

1201 DomTreeUpdater DTU(&DT, DomTreeUpdater::UpdateStrategy::Lazy);

1202

1203 switch (LF) {

1204 case LibFunc_sqrt:

1205 case LibFunc_sqrtf:

1206 case LibFunc_sqrtl:

1207 return foldSqrt(CI, LF, TTI, TLI, AC, DT);

1208 case LibFunc_strcmp:

1209 case LibFunc_strncmp:

1210 if (StrNCmpInliner(CI, LF, &DTU, DL).optimizeStrNCmp()) {

1211 MadeCFGChange = true;

1212 return true;

1213 }

1214 break;

1215 case LibFunc_memchr:

1217 MadeCFGChange = true;

1218 return true;

1219 }

1220 break;

1221 default:;

1222 }

1223 return false;

1224}

1225

1226

1227

1228

1233 bool MadeChange = false;

1235

1237 continue;

1238

1240

1241

1242

1243

1244

1245

1254

1255

1256

1258 }

1259 }

1260

1261

1262 if (MadeChange)

1265

1266 return MadeChange;

1267}

1268

1269

1270

1274 bool MadeChange = false;

1277 MadeChange |= TIC.run(F);

1279 return MadeChange;

1280}

1281

1289 bool MadeCFGChange = false;

1290 if ( runImpl (F, AC, TTI, TLI, DT, AA, MadeCFGChange)) {

1291

1293 }

1294

1296 if (MadeCFGChange)

1298 else

1300 return PA;

1301}

AMDGPU Register Bank Select

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

static bool tryToRecognizePopCount(Instruction &I)

static bool foldSqrt(CallInst *Call, LibFunc Func, TargetTransformInfo &TTI, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT)

Try to replace a mathlib call to sqrt with the LLVM intrinsic.

static bool foldAnyOrAllBitsSet(Instruction &I)

Match patterns that correspond to "any-bits-set" and "all-bits-set".

static cl::opt< unsigned > MemChrInlineThreshold("memchr-inline-threshold", cl::init(3), cl::Hidden, cl::desc("The maximum length of a constant string to " "inline a memchr call."))

static bool tryToFPToSat(Instruction &I, TargetTransformInfo &TTI)

Fold smin(smax(fptosi(x), C1), C2) to llvm.fptosi.sat(x), providing C1 and C2 saturate the value of t...

static cl::opt< unsigned > StrNCmpInlineThreshold("strncmp-inline-threshold", cl::init(3), cl::Hidden, cl::desc("The maximum length of a constant string for a builtin string cmp " "call eligible for inlining. The default value is 3."))

static bool matchAndOrChain(Value *V, MaskOps &MOps)

This is a recursive helper for foldAnyOrAllBitsSet() that walks through a chain of 'and' or 'or' inst...

static bool foldMemChr(CallInst *Call, DomTreeUpdater *DTU, const DataLayout &DL)

Convert memchr with a small constant string into a switch.

static bool foldConsecutiveLoads(Instruction &I, const DataLayout &DL, TargetTransformInfo &TTI, AliasAnalysis &AA, const DominatorTree &DT)

static bool runImpl(Function &F, AssumptionCache &AC, TargetTransformInfo &TTI, TargetLibraryInfo &TLI, DominatorTree &DT, AliasAnalysis &AA, bool &MadeCFGChange)

This is the entry point for all transforms.

static bool tryToRecognizeTableBasedCttz(Instruction &I)

static bool foldGuardedFunnelShift(Instruction &I, const DominatorTree &DT)

Match a pattern for a bitwise funnel/rotate operation that partially guards against undefined behavio...

static cl::opt< unsigned > MaxInstrsToScan("aggressive-instcombine-max-scan-instrs", cl::init(64), cl::Hidden, cl::desc("Max number of instructions to scan for aggressive instcombine."))

static bool foldLoadsRecursive(Value *V, LoadOps &LOps, const DataLayout &DL, AliasAnalysis &AA)

static std::pair< APInt, APInt > getStrideAndModOffsetOfGEP(Value *PtrOp, const DataLayout &DL)

static bool isCTTZTable(const ConstantDataArray &Table, uint64_t Mul, uint64_t Shift, uint64_t InputBits)

static bool foldPatternedLoads(Instruction &I, const DataLayout &DL)

If C is a constant patterned array and all valid loaded results for given alignment are same to a con...

static bool foldLibCalls(Instruction &I, TargetTransformInfo &TTI, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT, const DataLayout &DL, bool &MadeCFGChange)

static bool foldUnusualPatterns(Function &F, DominatorTree &DT, TargetTransformInfo &TTI, TargetLibraryInfo &TLI, AliasAnalysis &AA, AssumptionCache &AC, bool &MadeCFGChange)

This is the entry point for folds that could be implemented in regular InstCombine,...

AggressiveInstCombiner - Combine expression patterns to form expressions with fewer,...

This is the interface for LLVM's primary stateless and local alias analysis.

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx

static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")

static bool runImpl(Function &F, const TargetLowering &TLI)

This is the interface for a simple mod/ref and alias analysis over globals.

static MaybeAlign getAlign(Value *Ptr)

static Instruction * matchFunnelShift(Instruction &Or, InstCombinerImpl &IC)

Match UB-safe variants of the funnel shift intrinsic.

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

static const MCExpr * MaskShift(const MCExpr *Val, uint32_t Mask, uint32_t Shift, MCContext &Ctx)

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

This pass exposes codegen information to IR-level passes.

A manager for alias analyses.

ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)

Check whether or not an instruction may read or write the optionally specified memory location.

Class for arbitrary precision integers.

uint64_t getZExtValue() const

Get zero extended value.

bool isNegative() const

Determine sign of this APInt.

static APInt getSplat(unsigned NewLen, const APInt &V)

Return a value containing V broadcasted over NewLen bits.

APInt srem(const APInt &RHS) const

Function for signed remainder operation.

bool slt(const APInt &RHS) const

Signed less than comparison.

static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)

Constructs an APInt value that has a contiguous range of bits set.

static APInt getOneBitSet(unsigned numBits, unsigned BitNo)

Return an APInt with exactly one bit set in the result.

bool uge(const APInt &RHS) const

Unsigned greater or equal comparison.

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

A container for analyses that lazily runs them and caches their results.

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

A function analysis which provides an AssumptionCache.

A cache of @llvm.assume calls within a function.

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

const_iterator getFirstInsertionPt() const

Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...

static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)

Creates a new BasicBlock.

const Function * getParent() const

Return the enclosing method, or null if none.

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

Represents analyses that only rely on functions' control flow.

This class represents a function call, abstracting a target machine's calling convention.

An array constant whose element type is a simple 1/2/4/8-byte integer or float/double,...

uint64_t getElementAsInteger(unsigned i) const

If this is a sequential container of integers (of any size), return the specified element in the low ...

unsigned getNumElements() const

Return the number of elements in the array or vector.

This is the shared class of boolean and integer constants.

This is an important base class in LLVM.

static Constant * getNullValue(Type *Ty)

Constructor to create a '0' constant of arbitrary type.

A parsed version of the target data layout string in and methods for querying it.

Analysis pass which computes a DominatorTree.

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

bool isReachableFromEntry(const Use &U) const

Provide an overload for a Use.

bool dominates(const BasicBlock *BB, const Use &U) const

Return true if the (end of the) basic block BB dominates the use U.

void applyUpdates(ArrayRef< UpdateT > Updates)

Submit updates to all available trees.

an instruction for type-safe pointer arithmetic to access elements of arrays and structs

const Constant * getInitializer() const

getInitializer - Return the initializer for this global variable.

bool hasInitializer() const

Definitions have initializers, declarations don't.

bool isConstant() const

If the value is a global constant, its value is immutable throughout the runtime execution of the pro...

LoadInst * CreateAlignedLoad(Type *Ty, Value *Ptr, MaybeAlign Align, const char *Name)

Value * CreateSExt(Value *V, Type *DestTy, const Twine &Name="")

Value * CreateFreeze(Value *V, const Twine &Name="")

Value * CreatePtrAdd(Value *Ptr, Value *Offset, const Twine &Name="", GEPNoWrapFlags NW=GEPNoWrapFlags::none())

CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, FMFSource FMFSource={}, const Twine &Name="")

Create a call to intrinsic ID with Args, mangled using Types.

PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")

SwitchInst * CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases=10, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)

Create a switch instruction with the specified value, default dest, and with a hint for the number of...

Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")

Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)

Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)

Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")

Value * CreateIsNotNull(Value *Arg, const Twine &Name="")

Return a boolean value testing if Arg != 0.

Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)

BranchInst * CreateBr(BasicBlock *Dest)

Create an unconditional 'br label X' instruction.

void SetInsertPoint(BasicBlock *TheBB)

This specifies that created instructions should be appended to the end of the specified block.

Value * CreateInBoundsPtrAdd(Value *Ptr, Value *Offset, const Twine &Name="")

IntegerType * getInt8Ty()

Fetch the type representing an 8-bit integer.

ConstantInt * getInt(const APInt &AI)

Get a constant integer value.

This provides a uniform API for creating instructions and inserting them into a basic block: either a...

void setAAMetadata(const AAMDNodes &N)

Sets the AA metadata on this instruction from the AAMDNodes structure.

InstListType::iterator eraseFromParent()

This method unlinks 'this' from the containing basic block and deletes it.

AAMDNodes getAAMetadata() const

Returns the AA metadata for this instruction.

Class to represent integer types.

static IntegerType * get(LLVMContext &C, unsigned NumBits)

This static method is the primary way of constructing an IntegerType.

An instruction for reading from memory.

unsigned getPointerAddressSpace() const

Returns the address space of the pointer operand.

Value * getPointerOperand()

Representation for a specific memory location.

MemoryLocation getWithNewSize(LocationSize NewSize) const

static MemoryLocation get(const LoadInst *LI)

Return a location with information about the memory reference by the given instruction.

void addIncoming(Value *V, BasicBlock *BB)

Add an incoming value to the end of the PHI list.

static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)

Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

void preserveSet()

Mark an analysis set as preserved.

void preserve()

Mark an analysis as preserved.

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

StringRef - Represent a constant reference to a string, i.e.

static constexpr size_t npos

Analysis pass providing the TargetTransformInfo.

Analysis pass providing the TargetLibraryInfo.

Provides information about what library functions are available for the current target.

bool getLibFunc(StringRef funcName, LibFunc &F) const

Searches for a particular function name.

This pass provides access to the codegen interfaces that are needed for IR-level transformations.

InstructionCost getIntrinsicInstrCost(const IntrinsicCostAttributes &ICA, TTI::TargetCostKind CostKind) const

InstructionCost getCastInstrCost(unsigned Opcode, Type *Dst, Type *Src, TTI::CastContextHint CCH, TTI::TargetCostKind CostKind=TTI::TCK_SizeAndLatency, const Instruction *I=nullptr) const

@ TCK_RecipThroughput

Reciprocal throughput.

bool isTypeLegal(Type *Ty) const

Return true if this type is legal.

bool allowsMisalignedMemoryAccesses(LLVMContext &Context, unsigned BitWidth, unsigned AddressSpace=0, Align Alignment=Align(1), unsigned *Fast=nullptr) const

Determine if the target supports unaligned memory accesses.

bool haveFastSqrt(Type *Ty) const

Return true if the hardware has a fast square-root instruction.

@ None

The cast is not used with a load/store of any kind.

bool run(Function &F)

Perform TruncInst pattern optimization on given function.

Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...

The instances of the Type class are immutable: once they are created, they are never changed.

bool isIntOrIntVectorTy() const

Return true if this is an integer type or a vector of integer types.

unsigned getScalarSizeInBits() const LLVM_READONLY

If this is a vector type, return the getPrimitiveSizeInBits value for the element type.

LLVMContext & getContext() const

Return the LLVMContext in which this type was uniqued.

bool isIntegerTy() const

True if this is an instance of IntegerType.

TypeSize getPrimitiveSizeInBits() const LLVM_READONLY

Return the basic size of this type if it is a primitive type.

LLVM Value Representation.

Type * getType() const

All values are typed, get the type of this value.

const Value * stripAndAccumulateConstantOffsets(const DataLayout &DL, APInt &Offset, bool AllowNonInbounds, bool AllowInvariantGroup=false, function_ref< bool(Value &Value, APInt &Offset)> ExternalAnalysis=nullptr) const

Accumulate the constant offset this value has compared to a base pointer.

void replaceAllUsesWith(Value *V)

Change all uses of this to point to a new Value.

LLVMContext & getContext() const

All values hold a context through their type.

uint64_t getPointerDereferenceableBytes(const DataLayout &DL, bool &CanBeNull, bool &CanBeFreed) const

Returns the number of bytes known to be dereferenceable for the pointer value.

StringRef getName() const

Return a constant reference to the value's name.

void takeName(Value *V)

Transfer the name from V to this value.

const ParentTy * getParent() const

APInt GreatestCommonDivisor(APInt A, APInt B)

Compute GCD of two unsigned APInt values.

constexpr std::underlying_type_t< E > Mask()

Get a bitmask with 1s in all places up to the high-order bit of E's largest value.

@ Fast

Attempts to make calls as fast as possible (e.g.

@ C

The default llvm calling convention, compatible with C.

BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)

BinaryOp_match< LHS, RHS, Instruction::And, true > m_c_And(const LHS &L, const RHS &R)

Matches an And with LHS and RHS in either order.

specific_intval< false > m_SpecificInt(const APInt &V)

Match a specific integer value or vector with all elements equal to the value.

match_combine_or< CastInst_match< OpTy, ZExtInst >, OpTy > m_ZExtOrSelf(const OpTy &Op)

bool match(Val *V, const Pattern &P)

bind_ty< Instruction > m_Instruction(Instruction *&I)

Match an instruction, capturing it if we match.

specificval_ty m_Specific(const Value *V)

Match if we have a specific specified value.

class_match< ConstantInt > m_ConstantInt()

Match an arbitrary ConstantInt and ignore it.

cst_pred_ty< is_one > m_One()

Match an integer 1 or a vector with all elements equal to 1.

MaxMin_match< ICmpInst, LHS, RHS, smin_pred_ty > m_SMin(const LHS &L, const RHS &R)

BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)

deferredval_ty< Value > m_Deferred(Value *const &V)

Like m_Specific(), but works if the specific value to match is determined as part of the same match()...

cst_pred_ty< is_zero_int > m_ZeroInt()

Match an integer 0 or a vector with all elements equal to 0.

OneUse_match< T > m_OneUse(const T &SubPattern)

BinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub > m_Neg(const ValTy &V)

Matches a 'Neg' as 'sub 0, V'.

specific_bbval m_SpecificBB(BasicBlock *BB)

Match a specific basic block value.

SpecificCmpClass_match< LHS, RHS, ICmpInst > m_SpecificICmp(CmpPredicate MatchPred, const LHS &L, const RHS &R)

CastInst_match< OpTy, ZExtInst > m_ZExt(const OpTy &Op)

Matches ZExt.

brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)

BinaryOp_match< LHS, RHS, Instruction::Add, true > m_c_Add(const LHS &L, const RHS &R)

Matches a Add with LHS and RHS in either order.

CastInst_match< OpTy, FPToSIInst > m_FPToSI(const OpTy &Op)

MaxMin_match< ICmpInst, LHS, RHS, smax_pred_ty > m_SMax(const LHS &L, const RHS &R)

apint_match m_APInt(const APInt *&Res)

Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)

BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)

BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)

BinaryOp_match< LHS, RHS, Instruction::Or, true > m_c_Or(const LHS &L, const RHS &R)

Matches an Or with LHS and RHS in either order.

BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)

initializer< Ty > init(const Ty &Val)

NodeAddr< PhiNode * > Phi

NodeAddr< FuncNode * > Func

This is an optimization pass for GlobalISel generic memory operations.

bool isOnlyUsedInZeroComparison(const Instruction *CxtI)

bool getConstantStringInfo(const Value *V, StringRef &Str, bool TrimAtNul=true)

This function computes the length of a null-terminated C string pointed to by V.

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)

This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

bool SimplifyInstructionsInBlock(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr)

Scan the specified basic block and try to simplify any instructions in it and recursively delete dead...

constexpr bool isPowerOf2_64(uint64_t Value)

Return true if the argument is a power of two > 0 (64 bit edition.)

bool isLibFuncEmittable(const Module *M, const TargetLibraryInfo *TLI, LibFunc TheLibFunc)

Check whether the library function is available on target and also that it in the current Module is a...

unsigned Log2_32(uint32_t Value)

Return the floor log base 2 of the specified value, -1 if the value is zero.

auto reverse(ContainerTy &&C)

constexpr bool isPowerOf2_32(uint32_t Value)

Return true if the argument is a power of two > 0.

bool isModSet(const ModRefInfo MRI)

raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

Constant * ConstantFoldLoadFromConst(Constant *C, Type *Ty, const APInt &Offset, const DataLayout &DL)

Extract value of C at the given Offset reinterpreted as Ty.

@ And

Bitwise or logical AND of integers.

constexpr unsigned BitWidth

BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)

Split the specified block at the specified instruction.

bool cannotBeOrderedLessThanZero(const Value *V, unsigned Depth, const SimplifyQuery &SQ)

Return true if we can prove that the specified FP value is either NaN or never less than -0....

bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)

Returns true if V cannot be poison, but may be undef.

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

This is used by foldLoadsRecursive() to capture a Root Load node which is of type or(load,...

A collection of metadata nodes that might be associated with a memory access used by the alias-analys...

AAMDNodes concat(const AAMDNodes &Other) const

Determine the best AAMDNodes after concatenating two different locations together.

A MapVector that performs no allocations if smaller than a certain size.