LLVM: lib/Transforms/Scalar/LoopIdiomRecognize.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
89#include
90#include
91#include
92#include
93
94using namespace llvm;
96
97#define DEBUG_TYPE "loop-idiom"
98
99STATISTIC(NumMemSet, "Number of memset's formed from loop stores");
100STATISTIC(NumMemCpy, "Number of memcpy's formed from loop load+stores");
101STATISTIC(NumMemMove, "Number of memmove's formed from loop load+stores");
102STATISTIC(NumStrLen, "Number of strlen's and wcslen's formed from loop loads");
104 NumShiftUntilBitTest,
105 "Number of uncountable loops recognized as 'shift until bitttest' idiom");
107 "Number of uncountable loops recognized as 'shift until zero' idiom");
108
109namespace llvm {
113 cl::desc("Options to disable Loop Idiom Recognize Pass."),
116
120 cl::desc("Proceed with loop idiom recognize pass, but do "
121 "not convert loop(s) to memset."),
124
128 cl::desc("Proceed with loop idiom recognize pass, but do "
129 "not convert loop(s) to memcpy."),
132
136 cl::desc("Proceed with loop idiom recognize pass, but do "
137 "not convert loop(s) to strlen."),
140
144 cl::desc("Proceed with loop idiom recognize pass, "
145 "enable conversion of loop(s) to wcslen."),
148
152 cl::desc("Proceed with loop idiom recognize pass, "
153 "but do not optimize CRC loops."),
156
158 "use-lir-code-size-heurs",
159 cl::desc("Use loop idiom recognition code size heuristics when compiling "
160 "with -Os/-Oz"),
162
164 "loop-idiom-force-memset-pattern-intrinsic",
165 cl::desc("Use memset.pattern intrinsic whenever possible"), cl::init(false),
167
169
170}
171
172namespace {
173
174class LoopIdiomRecognize {
175 Loop *CurLoop = nullptr;
184 bool ApplyCodeSizeHeuristics;
185 std::unique_ptr MSSAU;
186
187public:
194 : AA(AA), DT(DT), LI(LI), SE(SE), TLI(TLI), TTI(TTI), DL(DL), ORE(ORE) {
195 if (MSSA)
196 MSSAU = std::make_unique(MSSA);
197 }
198
199 bool runOnLoop(Loop *L);
200
201private:
202 using StoreList = SmallVector<StoreInst *, 8>;
203 using StoreListMap = MapVector<Value *, StoreList>;
204
205 StoreListMap StoreRefsForMemset;
206 StoreListMap StoreRefsForMemsetPattern;
207 StoreList StoreRefsForMemcpy;
208 bool HasMemset;
209 bool HasMemsetPattern;
210 bool HasMemcpy;
211
212
213 enum LegalStoreKind {
214 None = 0,
215 Memset,
216 MemsetPattern,
217 Memcpy,
218 UnorderedAtomicMemcpy,
219 DontUse
220
221 };
222
223
224
225
226 bool runOnCountableLoop();
227 bool runOnLoopBlock(BasicBlock *BB, const SCEV *BECount,
228 SmallVectorImpl<BasicBlock *> &ExitBlocks);
229
230 void collectStores(BasicBlock *BB);
231 LegalStoreKind isLegalStore(StoreInst *SI);
232 enum class ForMemset { No, Yes };
233 bool processLoopStores(SmallVectorImpl<StoreInst *> &SL, const SCEV *BECount,
234 ForMemset For);
235
236 template
237 bool processLoopMemIntrinsic(
238 BasicBlock *BB,
239 bool (LoopIdiomRecognize::*Processor)(MemInst *, const SCEV *),
240 const SCEV *BECount);
241 bool processLoopMemCpy(MemCpyInst *MCI, const SCEV *BECount);
242 bool processLoopMemSet(MemSetInst *MSI, const SCEV *BECount);
243
244 bool processLoopStridedStore(Value *DestPtr, const SCEV *StoreSizeSCEV,
245 MaybeAlign StoreAlignment, Value *StoredVal,
246 Instruction *TheStore,
247 SmallPtrSetImpl<Instruction *> &Stores,
248 const SCEVAddRecExpr *Ev, const SCEV *BECount,
249 bool IsNegStride, bool IsLoopMemset = false);
250 bool processLoopStoreOfLoopLoad(StoreInst *SI, const SCEV *BECount);
251 bool processLoopStoreOfLoopLoad(Value *DestPtr, Value *SourcePtr,
252 const SCEV *StoreSize, MaybeAlign StoreAlign,
253 MaybeAlign LoadAlign, Instruction *TheStore,
254 Instruction *TheLoad,
255 const SCEVAddRecExpr *StoreEv,
256 const SCEVAddRecExpr *LoadEv,
257 const SCEV *BECount);
258 bool avoidLIRForMultiBlockLoop(bool IsMemset = false,
259 bool IsLoopMemset = false);
260 bool optimizeCRCLoop(const PolynomialInfo &Info);
261
262
263
264
265
266 bool runOnNoncountableLoop();
267
268 bool recognizePopcount();
269 void transformLoopToPopcount(BasicBlock *PreCondBB, Instruction *CntInst,
270 PHINode *CntPhi, Value *Var);
272 bool ZeroCheck, size_t CanonicalSize);
274 Instruction *DefX, PHINode *CntPhi,
275 Instruction *CntInst);
276 bool recognizeAndInsertFFS();
277 bool recognizeShiftUntilLessThan();
278 void transformLoopToCountable(Intrinsic::ID IntrinID, BasicBlock *PreCondBB,
279 Instruction *CntInst, PHINode *CntPhi,
280 Value *Var, Instruction *DefX,
281 const DebugLoc &DL, bool ZeroCheck,
282 bool IsCntPhiUsedOutsideLoop,
283 bool InsertSub = false);
284
285 bool recognizeShiftUntilBitTest();
286 bool recognizeShiftUntilZero();
287 bool recognizeAndInsertStrLen();
288
289
290};
291}
292
298
299 const auto *DL = &L.getHeader()->getDataLayout();
300
301
302
303
305
306 LoopIdiomRecognize LIR(&AR.AA, &AR.DT, &AR.LI, &AR.SE, &AR.TLI, &AR.TTI,
308 if (!LIR.runOnLoop(&L))
310
314 return PA;
315}
316
319 I->eraseFromParent();
320}
321
322
323
324
325
326
327
328bool LoopIdiomRecognize::runOnLoop(Loop *L) {
329 CurLoop = L;
330
331
332 if (->getLoopPreheader())
333 return false;
334
335
336 StringRef Name = L->getHeader()->getParent()->getName();
337 if (Name == "memset" || Name == "memcpy" || Name == "strlen" ||
338 Name == "wcslen")
339 return false;
340
341
342 ApplyCodeSizeHeuristics =
344
345 HasMemset = TLI->has(LibFunc_memset);
346
347
348
349
350
351 HasMemsetPattern = TLI->has(LibFunc_memset_pattern16);
352 HasMemcpy = TLI->has(LibFunc_memcpy);
353
357 return runOnCountableLoop();
358
359 return runOnNoncountableLoop();
360}
361
362bool LoopIdiomRecognize::runOnCountableLoop() {
365 "runOnCountableLoop() called on a loop without a predictable"
366 "backedge-taken count");
367
368
369
370 if (BECount->isZero())
371 return false;
372
375
379 << "\n");
380
381
382
386 return false;
387
388 bool MadeChange = false;
389
390
391 for (auto *BB : CurLoop->getBlocks()) {
392
394 continue;
395
396 MadeChange |= runOnLoopBlock(BB, BECount, ExitBlocks);
397 }
398
399
400
402 if (auto Res = HashRecognize(*CurLoop, *SE).getResult())
403 optimizeCRCLoop(*Res);
404
405 return MadeChange;
406}
407
410 return ConstStride->getAPInt();
411}
412
413
414
415
416
417
418
419
420
422
423
424
425
426
427
430 return nullptr;
431
432
435 return nullptr;
436
437
438 if (DL->isBigEndian())
439 return nullptr;
440
441
443
444
445
446 if (Size > 16)
447 return nullptr;
448
449
452 return nullptr;
453
454 return C;
455}
456
457LoopIdiomRecognize::LegalStoreKind
458LoopIdiomRecognize::isLegalStore(StoreInst *SI) {
459
460 if (SI->isVolatile())
461 return LegalStoreKind::None;
462
463 if (->isUnordered())
464 return LegalStoreKind::None;
465
466
467 if (SI->getMetadata(LLVMContext::MD_nontemporal))
468 return LegalStoreKind::None;
469
470 Value *StoredVal = SI->getValueOperand();
471 Value *StorePtr = SI->getPointerOperand();
472
473
474
476 return LegalStoreKind::None;
477
478
479
480
481 TypeSize SizeInBits = DL->getTypeSizeInBits(StoredVal->getType());
484 return LegalStoreKind::None;
485
486
487
488
489 const SCEV *StoreEv = SE->getSCEV(StorePtr);
493 return LegalStoreKind::None;
494
495
496
497
498
499
500
502
503
504 bool UnorderedAtomic = SI->isUnordered() && ->isSimple();
505
506
507
508 if (!UnorderedAtomic && HasMemset && SplatValue && &&
509
510
512
513 return LegalStoreKind::Memset;
514 }
517
520
521 return LegalStoreKind::MemsetPattern;
522 }
523
524
526
527
528 unsigned StoreSize = DL->getTypeStoreSize(SI->getValueOperand()->getType());
530 if (StoreSize != StrideAP && StoreSize != -StrideAP)
531 return LegalStoreKind::None;
532
533
535
536
538 return LegalStoreKind::None;
539
541 return LegalStoreKind::None;
542
543
544
545
547
548
551 return LegalStoreKind::None;
552
553
554 UnorderedAtomic = UnorderedAtomic || LI->isAtomic();
555 return UnorderedAtomic ? LegalStoreKind::UnorderedAtomicMemcpy
556 : LegalStoreKind::Memcpy;
557 }
558
559 return LegalStoreKind::None;
560}
561
562void LoopIdiomRecognize::collectStores(BasicBlock *BB) {
563 StoreRefsForMemset.clear();
564 StoreRefsForMemsetPattern.clear();
565 StoreRefsForMemcpy.clear();
568 if ()
569 continue;
570
571
572 switch (isLegalStore(SI)) {
573 case LegalStoreKind::None:
574
575 break;
576 case LegalStoreKind::Memset: {
577
579 StoreRefsForMemset[Ptr].push_back(SI);
580 } break;
581 case LegalStoreKind::MemsetPattern: {
582
584 StoreRefsForMemsetPattern[Ptr].push_back(SI);
585 } break;
586 case LegalStoreKind::Memcpy:
587 case LegalStoreKind::UnorderedAtomicMemcpy:
588 StoreRefsForMemcpy.push_back(SI);
589 break;
590 default:
591 assert(false && "unhandled return value");
592 break;
593 }
594 }
595}
596
597
598
599
600bool LoopIdiomRecognize::runOnLoopBlock(
603
604
605
606 for (BasicBlock *ExitBlock : ExitBlocks)
607 if (!DT->dominates(BB, ExitBlock))
608 return false;
609
610 bool MadeChange = false;
611
612 collectStores(BB);
613
614
615
616
617 for (auto &SL : StoreRefsForMemset)
618 MadeChange |= processLoopStores(SL.second, BECount, ForMemset::Yes);
619
620 for (auto &SL : StoreRefsForMemsetPattern)
621 MadeChange |= processLoopStores(SL.second, BECount, ForMemset::No);
622
623
624 for (auto &SI : StoreRefsForMemcpy)
625 MadeChange |= processLoopStoreOfLoopLoad(SI, BECount);
626
627 MadeChange |= processLoopMemIntrinsic(
628 BB, &LoopIdiomRecognize::processLoopMemCpy, BECount);
629 MadeChange |= processLoopMemIntrinsic(
630 BB, &LoopIdiomRecognize::processLoopMemSet, BECount);
631
632 return MadeChange;
633}
634
635
637 const SCEV *BECount, ForMemset For) {
638
641
642
643
645 for (unsigned i = 0, e = SL.size(); i < e; ++i) {
646 assert(SL[i]->isSimple() && "Expected only non-volatile stores.");
647
648 Value *FirstStoredVal = SL[i]->getValueOperand();
649 Value *FirstStorePtr = SL[i]->getPointerOperand();
653 unsigned FirstStoreSize = DL->getTypeStoreSize(SL[i]->getValueOperand()->getType());
654
655
656 if (FirstStride == FirstStoreSize || -FirstStride == FirstStoreSize) {
658 continue;
659 }
660
661 Value *FirstSplatValue = nullptr;
662 Constant *FirstPatternValue = nullptr;
663
664 if (For == ForMemset::Yes)
666 else
668
669 assert((FirstSplatValue || FirstPatternValue) &&
670 "Expected either splat value or pattern value.");
671
672 IndexQueue.clear();
673
674
675
676
677 unsigned j = 0;
678 for (j = i + 1; j < e; ++j)
682
683 for (auto &k : IndexQueue) {
684 assert(SL[k]->isSimple() && "Expected only non-volatile stores.");
685 Value *SecondStorePtr = SL[k]->getPointerOperand();
689
690 if (FirstStride != SecondStride)
691 continue;
692
693 Value *SecondStoredVal = SL[k]->getValueOperand();
694 Value *SecondSplatValue = nullptr;
695 Constant *SecondPatternValue = nullptr;
696
697 if (For == ForMemset::Yes)
699 else
701
702 assert((SecondSplatValue || SecondPatternValue) &&
703 "Expected either splat value or pattern value.");
704
706 if (For == ForMemset::Yes) {
708 FirstSplatValue = SecondSplatValue;
709 if (FirstSplatValue != SecondSplatValue)
710 continue;
711 } else {
713 FirstPatternValue = SecondPatternValue;
714 if (FirstPatternValue != SecondPatternValue)
715 continue;
716 }
719 ConsecutiveChain[SL[i]] = SL[k];
720 break;
721 }
722 }
723 }
724
725
726
729
730
733 continue;
734
735
736
739 unsigned StoreSize = 0;
740
741
742 while (Tails.count(I) || Heads.count(I)) {
743 if (TransformedStores.count(I))
744 break;
746
747 StoreSize += DL->getTypeStoreSize(I->getValueOperand()->getType());
748
750 }
751
756
757
758
759 if (StoreSize != Stride && StoreSize != -Stride)
760 continue;
761
762 bool IsNegStride = StoreSize == -Stride;
763
764 Type *IntIdxTy = DL->getIndexType(StorePtr->getType());
765 const SCEV *StoreSizeSCEV = SE->getConstant(IntIdxTy, StoreSize);
766 if (processLoopStridedStore(StorePtr, StoreSizeSCEV,
768 HeadStore, AdjacentStores, StoreEv, BECount,
769 IsNegStride)) {
770 TransformedStores.insert_range(AdjacentStores);
772 }
773 }
774
776}
777
778
779
780template
781bool LoopIdiomRecognize::processLoopMemIntrinsic(
783 bool (LoopIdiomRecognize::*Processor)(MemInst *, const SCEV *),
784 const SCEV *BECount) {
785 bool MadeChange = false;
788
791 if (!(this->*Processor)(MI, BECount))
792 continue;
793 MadeChange = true;
794
795
796
797 if (!InstPtr)
799 }
800 }
801 return MadeChange;
802}
803
804
805bool LoopIdiomRecognize::processLoopMemCpy(MemCpyInst *MCI,
806 const SCEV *BECount) {
807
809 return false;
810
811
813 return false;
814
817 if (!Dest || !Source)
818 return false;
819
820
821
822
824 const SCEV *LoadEv = SE->getSCEV(Source);
825 const APInt *StoreStrideValue, *LoadStrideValue;
826 if ((StoreEv,
832 return false;
833
834
836 if ((SizeInBytes >> 32) != 0)
837 return false;
838
839
840 if (StoreStrideValue->getBitWidth() > 64 ||
842 return false;
843
844 if (SizeInBytes != *StoreStrideValue && SizeInBytes != -*StoreStrideValue) {
845 ORE.emit([&]() {
847 << ore::NV("Inst", "memcpy") << " in "
849 << " function will not be hoisted: "
850 << ore::NV("Reason", "memcpy size is not equal to stride");
851 });
852 return false;
853 }
854
855 int64_t StoreStrideInt = StoreStrideValue->getSExtValue();
856 int64_t LoadStrideInt = LoadStrideValue->getSExtValue();
857
858 if (StoreStrideInt != LoadStrideInt)
859 return false;
860
861 return processLoopStoreOfLoopLoad(
865}
866
867
868bool LoopIdiomRecognize::processLoopMemSet(MemSetInst *MSI,
869 const SCEV *BECount) {
870
872 return false;
873
874
876 return false;
877
879
880
881
882
884 const SCEV *PointerStrideSCEV;
887 LLVM_DEBUG(dbgs() << " Pointer is not affine, abort\n");
888 return false;
889 }
890
892
893 bool IsNegStride = false;
895
896 if (IsConstantSize) {
897
898
899
902 const APInt *Stride;
904 return false;
905
906 if (SizeInBytes != *Stride && SizeInBytes != -*Stride)
907 return false;
908
909 IsNegStride = SizeInBytes == -*Stride;
910 } else {
911
912
913
914
915
916 LLVM_DEBUG(dbgs() << " memset size is non-constant\n");
917 if (Pointer->getType()->getPointerAddressSpace() != 0) {
918 LLVM_DEBUG(dbgs() << " pointer is not in address space zero, "
919 << "abort\n");
920 return false;
921 }
923 LLVM_DEBUG(dbgs() << " memset size is not a loop-invariant, "
924 << "abort\n");
925 return false;
926 }
927
928
930 const SCEV *PositiveStrideSCEV =
932 : PointerStrideSCEV;
933 LLVM_DEBUG(dbgs() << " MemsetSizeSCEV: " << *MemsetSizeSCEV << "\n"
934 << " PositiveStrideSCEV: " << *PositiveStrideSCEV
935 << "\n");
936
937 if (PositiveStrideSCEV != MemsetSizeSCEV) {
938
939
940 const SCEV *FoldedPositiveStride =
942 const SCEV *FoldedMemsetSize =
944
945 LLVM_DEBUG(dbgs() << " Try to fold SCEV based on loop guard\n"
946 << " FoldedMemsetSize: " << *FoldedMemsetSize << "\n"
947 << " FoldedPositiveStride: " << *FoldedPositiveStride
948 << "\n");
949
950 if (FoldedPositiveStride != FoldedMemsetSize) {
952 return false;
953 }
954 }
955 }
956
957
958
960 if (!SplatValue || !CurLoop->isLoopInvariant(SplatValue))
961 return false;
962
965 return processLoopStridedStore(Pointer, SE->getSCEV(MSI->getLength()),
968 true);
969}
970
971
972
973
974static bool
976 const SCEV *BECount, const SCEV *StoreSizeSCEV,
979
980
981
983
984
985
986 const APInt *BECst, *ConstSize;
989 std::optional<uint64_t> BEInt = BECst->tryZExtValue();
990 std::optional<uint64_t> SizeInt = ConstSize->tryZExtValue();
991
992 if (BEInt && SizeInt)
994 }
995
996
997
998
999
1001
1004 if (!IgnoredInsts.contains(&I) &&
1006 return true;
1007 return false;
1008}
1009
1010
1011
1012
1014 Type *IntPtr, const SCEV *StoreSizeSCEV,
1017 if (!StoreSizeSCEV->isOne()) {
1018
1022 }
1023
1025}
1026
1027
1028
1029
1030
1032 const SCEV *StoreSizeSCEV, Loop *CurLoop,
1034 const SCEV *TripCountSCEV =
1036 return SE->getMulExpr(TripCountSCEV,
1039}
1040
1041
1042
1043bool LoopIdiomRecognize::processLoopStridedStore(
1047 const SCEV *BECount, bool IsNegStride, bool IsLoopMemset) {
1049
1050
1051
1052
1058
1059 Type *DestInt8PtrTy = Builder.getPtrTy(DestAS);
1060 Type *IntIdxTy = DL->getIndexType(DestPtr->getType());
1061
1064
1065 if (IsNegStride)
1067
1068
1069
1070 if (!Expander.isSafeToExpand(Start))
1072
1073
1074
1075
1076
1077
1079 Expander.expandCodeFor(Start, DestInt8PtrTy, Preheader->getTerminator());
1080
1081
1082
1083
1084
1085
1086
1087
1089
1091 StoreSizeSCEV, *AA, Stores))
1093
1094 if (avoidLIRForMultiBlockLoop(true, IsLoopMemset))
1096
1097
1099 Constant *PatternValue = nullptr;
1100 if (!SplatValue)
1102
1103
1104
1105 Value *MemsetArg;
1106 std::optional<int64_t> BytesWritten;
1107
1109 const SCEV *TripCountS =
1111 if (!Expander.isSafeToExpand(TripCountS))
1114 if (!ConstStoreSize)
1116 Value *TripCount = Expander.expandCodeFor(TripCountS, IntIdxTy,
1118 uint64_t PatternRepsPerTrip =
1119 (ConstStoreSize->getValue()->getZExtValue() * 8) /
1120 DL->getTypeSizeInBits(PatternValue->getType());
1121
1122
1123
1124 MemsetArg =
1125 PatternRepsPerTrip == 1
1126 ? TripCount
1127 : Builder.CreateMul(TripCount,
1129 PatternRepsPerTrip));
1131 BytesWritten =
1133
1134 } else {
1135 const SCEV *NumBytesS =
1136 getNumBytes(BECount, IntIdxTy, StoreSizeSCEV, CurLoop, DL, SE);
1137
1138
1139
1140 if (!Expander.isSafeToExpand(NumBytesS))
1142 MemsetArg =
1143 Expander.expandCodeFor(NumBytesS, IntIdxTy, Preheader->getTerminator());
1145 BytesWritten = CI->getZExtValue();
1146 }
1147 assert(MemsetArg && "MemsetArg should have been set");
1148
1151 AATags = AATags.merge(Store->getAAMetadata());
1152 if (BytesWritten)
1153 AATags = AATags.extendTo(BytesWritten.value());
1154 else
1155 AATags = AATags.extendTo(-1);
1156
1158 if (SplatValue) {
1159 NewCall = Builder.CreateMemSet(BasePtr, SplatValue, MemsetArg,
1161 false, AATags);
1165
1166 NewCall = Builder.CreateIntrinsic(
1167 Intrinsic::experimental_memset_pattern,
1168 {DestInt8PtrTy, PatternValue->getType(), IntIdxTy},
1169 {BasePtr, PatternValue, MemsetArg,
1171 if (StoreAlignment)
1174 } else {
1175
1177 }
1178
1180
1181 if (MSSAU) {
1182 MemoryAccess *NewMemAcc = MSSAU->createMemoryAccessInBB(
1185 }
1186
1187 LLVM_DEBUG(dbgs() << " Formed memset: " << *NewCall << "\n"
1188 << " from store to: " << *Ev << " at: " << *TheStore
1189 << "\n");
1190
1191 ORE.emit([&]() {
1194 R << "Transformed loop-strided store in "
1196 << " function into a call to "
1198 << "() intrinsic";
1199 if (!Stores.empty())
1201 for (auto *I : Stores) {
1202 R << ore::NV("FromBlock", I->getParent()->getName())
1204 }
1205 return R;
1206 });
1207
1208
1209
1210 for (auto *I : Stores) {
1211 if (MSSAU)
1212 MSSAU->removeMemoryAccess(I, true);
1214 }
1216 MSSAU->getMemorySSA()->verifyMemorySSA();
1217 ++NumMemSet;
1218 ExpCleaner.markResultUsed();
1219 return true;
1220}
1221
1222
1223
1224
1225bool LoopIdiomRecognize::processLoopStoreOfLoopLoad(StoreInst *SI,
1226 const SCEV *BECount) {
1227 assert(SI->isUnordered() && "Expected only non-volatile non-ordered stores.");
1228
1229 Value *StorePtr = SI->getPointerOperand();
1231 unsigned StoreSize = DL->getTypeStoreSize(SI->getValueOperand()->getType());
1232
1233
1235 assert(LI->isUnordered() && "Expected only non-volatile non-ordered loads.");
1236
1237
1238
1239
1242
1244 return processLoopStoreOfLoopLoad(StorePtr, LoadPtr, StoreSizeSCEV,
1246 StoreEv, LoadEv, BECount);
1247}
1248
1249namespace {
1250class MemmoveVerifier {
1251public:
1252 explicit MemmoveVerifier(const Value &LoadBasePtr, const Value &StoreBasePtr,
1253 const DataLayout &DL)
1255 LoadBasePtr.stripPointerCasts(), LoadOff, DL)),
1257 StoreBasePtr.stripPointerCasts(), StoreOff, DL)),
1258 IsSameObject(BP1 == BP2) {}
1259
1260 bool loadAndStoreMayFormMemmove(unsigned StoreSize, bool IsNegStride,
1261 const Instruction &TheLoad,
1262 bool IsMemCpy) const {
1263 if (IsMemCpy) {
1264
1265
1266 if ((!IsNegStride && LoadOff <= StoreOff) ||
1267 (IsNegStride && LoadOff >= StoreOff))
1268 return false;
1269 } else {
1270
1271
1272 int64_t LoadSize =
1273 DL.getTypeSizeInBits(TheLoad.getType()).getFixedValue() / 8;
1274 if (BP1 != BP2 || LoadSize != int64_t(StoreSize))
1275 return false;
1276 if ((!IsNegStride && LoadOff < StoreOff + int64_t(StoreSize)) ||
1277 (IsNegStride && LoadOff + LoadSize > StoreOff))
1278 return false;
1279 }
1280 return true;
1281 }
1282
1283private:
1284 const DataLayout &DL;
1285 int64_t LoadOff = 0;
1286 int64_t StoreOff = 0;
1287 const Value *BP1;
1288 const Value *BP2;
1289
1290public:
1291 const bool IsSameObject;
1292};
1293}
1294
1295bool LoopIdiomRecognize::processLoopStoreOfLoopLoad(
1296 Value *DestPtr, Value *SourcePtr, const SCEV *StoreSizeSCEV,
1300
1301
1302
1303
1305 return false;
1306
1307
1308
1309
1313
1315
1319 Type *IntIdxTy = Builder.getIntNTy(DL->getIndexSizeInBits(StrAS));
1320
1323
1324
1325 assert(ConstStoreSize && "store size is expected to be a constant");
1326
1328 bool IsNegStride = StoreSize == -Stride;
1329
1330
1331 if (IsNegStride)
1332 StrStart =
1334
1335
1336
1337
1338
1339
1340
1341 Value *StoreBasePtr = Expander.expandCodeFor(
1342 StrStart, Builder.getPtrTy(StrAS), Preheader->getTerminator());
1343
1344
1345
1346
1347
1348
1349
1350
1352
1354 IgnoredInsts.insert(TheStore);
1355
1357 const StringRef InstRemark = IsMemCpy ? "memcpy" : "load and store";
1358
1359 bool LoopAccessStore =
1361 StoreSizeSCEV, *AA, IgnoredInsts);
1362 if (LoopAccessStore) {
1363
1364
1365
1368 IgnoredInsts.insert(TheLoad);
1370 BECount, StoreSizeSCEV, *AA, IgnoredInsts)) {
1371 ORE.emit([&]() {
1373 TheStore)
1374 << ore::NV("Inst", InstRemark) << " in "
1376 << " function will not be hoisted: "
1377 << ore::NV("Reason", "The loop may access store location");
1378 });
1380 }
1381 IgnoredInsts.erase(TheLoad);
1382 }
1383
1386
1387
1388 if (IsNegStride)
1389 LdStart =
1391
1392
1393
1394 Value *LoadBasePtr = Expander.expandCodeFor(LdStart, Builder.getPtrTy(LdAS),
1396
1397
1398
1399 MemmoveVerifier Verifier(*LoadBasePtr, *StoreBasePtr, *DL);
1400 if (IsMemCpy && .IsSameObject)
1401 IgnoredInsts.erase(TheStore);
1403 StoreSizeSCEV, *AA, IgnoredInsts)) {
1404 ORE.emit([&]() {
1406 << ore::NV("Inst", InstRemark) << " in "
1408 << " function will not be hoisted: "
1409 << ore::NV("Reason", "The loop may access load location");
1410 });
1412 }
1413
1414 bool IsAtomic = TheStore->isAtomic() || TheLoad->isAtomic();
1415 bool UseMemMove = IsMemCpy ? Verifier.IsSameObject : LoopAccessStore;
1416
1417 if (IsAtomic) {
1418
1419 if (UseMemMove)
1421
1422
1423
1424 assert((StoreAlign && LoadAlign) &&
1425 "Expect unordered load/store to have align.");
1426 if (*StoreAlign < StoreSize || *LoadAlign < StoreSize)
1428
1429
1430
1431
1432
1433 if (StoreSize > TTI->getAtomicMemIntrinsicMaxElementSize())
1435 }
1436
1437 if (UseMemMove)
1438 if (.loadAndStoreMayFormMemmove(StoreSize, IsNegStride, *TheLoad,
1439 IsMemCpy))
1441
1442 if (avoidLIRForMultiBlockLoop())
1444
1445
1446
1447 const SCEV *NumBytesS =
1448 getNumBytes(BECount, IntIdxTy, StoreSizeSCEV, CurLoop, DL, SE);
1449
1450 Value *NumBytes =
1451 Expander.expandCodeFor(NumBytesS, IntIdxTy, Preheader->getTerminator());
1452
1455 AATags = AATags.merge(StoreAATags);
1457 AATags = AATags.extendTo(CI->getZExtValue());
1458 else
1459 AATags = AATags.extendTo(-1);
1460
1461 CallInst *NewCall = nullptr;
1462
1463
1464
1465 if (!IsAtomic) {
1466 if (UseMemMove)
1467 NewCall = Builder.CreateMemMove(StoreBasePtr, StoreAlign, LoadBasePtr,
1468 LoadAlign, NumBytes,
1469 false, AATags);
1470 else
1471 NewCall =
1472 Builder.CreateMemCpy(StoreBasePtr, StoreAlign, LoadBasePtr, LoadAlign,
1473 NumBytes, false, AATags);
1474 } else {
1475
1476
1477
1478 NewCall = Builder.CreateElementUnorderedAtomicMemCpy(
1479 StoreBasePtr, *StoreAlign, LoadBasePtr, *LoadAlign, NumBytes, StoreSize,
1480 AATags);
1481 }
1483
1484 if (MSSAU) {
1485 MemoryAccess *NewMemAcc = MSSAU->createMemoryAccessInBB(
1488 }
1489
1490 LLVM_DEBUG(dbgs() << " Formed new call: " << *NewCall << "\n"
1491 << " from load ptr=" << *LoadEv << " at: " << *TheLoad
1492 << "\n"
1493 << " from store ptr=" << *StoreEv << " at: " << *TheStore
1494 << "\n");
1495
1496 ORE.emit([&]() {
1499 << "Formed a call to "
1501 << "() intrinsic from " << ore::NV("Inst", InstRemark)
1502 << " instruction in " << ore::NV("Function", TheStore->getFunction())
1503 << " function"
1507 });
1508
1509
1510
1511 if (MSSAU)
1512 MSSAU->removeMemoryAccess(TheStore, true);
1515 MSSAU->getMemorySSA()->verifyMemorySSA();
1516 if (UseMemMove)
1517 ++NumMemMove;
1518 else
1519 ++NumMemCpy;
1520 ExpCleaner.markResultUsed();
1521 return true;
1522}
1523
1524
1525
1526
1527bool LoopIdiomRecognize::avoidLIRForMultiBlockLoop(bool IsMemset,
1528 bool IsLoopMemset) {
1529 if (ApplyCodeSizeHeuristics && CurLoop->getNumBlocks() > 1) {
1530 if (CurLoop->isOutermost() && (!IsMemset || !IsLoopMemset)) {
1532 << " : LIR " << (IsMemset ? "Memset" : "Memcpy")
1533 << " avoided: multi-block top-level loop\n");
1534 return true;
1535 }
1536 }
1537
1538 return false;
1539}
1540
1541bool LoopIdiomRecognize::optimizeCRCLoop(const PolynomialInfo &Info) {
1542
1543
1544
1545
1546
1550 return false;
1551
1552
1553
1554 Type *CRCTy = Info.LHS->getType();
1556 std::array<Constant *, 256> CRCConstants;
1558 CRCConstants.begin(),
1559 [CRCTy](const APInt &E) { return ConstantInt::get(CRCTy, E); });
1565
1568
1569
1570 {
1572 if (&PN == IV)
1573 continue;
1576 }
1577 }
1578
1579
1580 {
1581 unsigned NewBTC = (Info.TripCount / 8) - 1;
1588 Value *ExitLimit = ConstantInt::get(IV->getType(), NewBTC);
1590 Value *NewExitCond =
1591 Builder.CreateICmp(ExitPred, IV, ExitLimit, "exit.cond");
1594 }
1595
1596
1597
1598
1599
1600
1601
1602
1603 {
1607 };
1610 Type *OpTy = Op->getType();
1611
1612
1613
1614 return LoByte(Builder,
1615 CRCBW > 8 ? Builder.CreateLShr(
1616 Op, ConstantInt::get(OpTy, CRCBW - 8), Name)
1617 : Op,
1618 Name + ".lo.byte");
1619 };
1620
1623
1624
1625
1626 PHINode *CRCPhi = Builder.CreatePHI(CRCTy, 2, "crc");
1628
1629
1630 Value *CRC = CRCPhi;
1631
1632
1633
1634 Value *Indexer = CRC;
1636 Type *DataTy = Data->getType();
1637
1638
1639
1640
1641
1642 Value *IVBits = Builder.CreateZExtOrTrunc(
1643 Builder.CreateShl(IV, 3, "iv.bits"), DataTy, "iv.indexer");
1644 Value *DataIndexer =
1645 Info.ByteOrderSwapped
1646 ? Builder.CreateShl(Data, IVBits, "data.indexer")
1647 : Builder.CreateLShr(Data, IVBits, "data.indexer");
1648 Indexer = Builder.CreateXor(
1649 DataIndexer,
1650 Builder.CreateZExtOrTrunc(Indexer, DataTy, "crc.indexer.cast"),
1651 "crc.data.indexer");
1652 }
1653
1654 Indexer = Info.ByteOrderSwapped ? HiIdx(Builder, Indexer, "indexer.hi")
1655 : LoByte(Builder, Indexer, "indexer.lo");
1656
1657
1658 Indexer = Builder.CreateZExt(
1660 "indexer.ext");
1661
1662
1663 Value *CRCTableGEP =
1664 Builder.CreateInBoundsGEP(CRCTy, GV, Indexer, "tbl.ptradd");
1665 Value *CRCTableLd = Builder.CreateLoad(CRCTy, CRCTableGEP, "tbl.ld");
1666
1667
1668
1669 Value *CRCNext = CRCTableLd;
1670 if (CRCBW > 8) {
1671 Value *CRCShift = Info.ByteOrderSwapped
1672 ? Builder.CreateShl(CRC, 8, "crc.be.shift")
1673 : Builder.CreateLShr(CRC, 8, "crc.le.shift");
1674 CRCNext = Builder.CreateXor(CRCShift, CRCTableLd, "crc.next");
1675 }
1676
1677
1679 Info.ComputedValue->replaceUsesOutsideBlock(CRCNext,
1681 }
1682
1683
1684 {
1688 }
1689 return true;
1690}
1691
1692bool LoopIdiomRecognize::runOnNoncountableLoop() {
1695 << "] Noncountable Loop %"
1697
1698 return recognizePopcount() || recognizeAndInsertFFS() ||
1699 recognizeShiftUntilBitTest() || recognizeShiftUntilZero() ||
1700 recognizeShiftUntilLessThan() || recognizeAndInsertStrLen();
1701}
1702
1703
1704
1705
1706
1707
1708
1710 bool JmpOnZero = false) {
1712 return nullptr;
1713
1716 return nullptr;
1717
1719 if (!CmpZero || !CmpZero->isZero())
1720 return nullptr;
1721
1724 if (JmpOnZero)
1726
1730 return Cond->getOperand(0);
1731
1732 return nullptr;
1733}
1734
1735namespace {
1736
1737class StrlenVerifier {
1738public:
1739 explicit StrlenVerifier(const Loop *CurLoop, ScalarEvolution *SE,
1740 const TargetLibraryInfo *TLI)
1741 : CurLoop(CurLoop), SE(SE), TLI(TLI) {}
1742
1743 bool isValidStrlenIdiom() {
1744
1745
1748 return false;
1749
1750
1752 if (!Preheader)
1753 return false;
1754
1756 if (!EntryBI)
1757 return false;
1758
1759
1760
1761
1763
1764
1765 if (!LoopBody || LoopBody->size() >= 15)
1766 return false;
1767
1770 if (!LoopCond)
1771 return false;
1772
1775 return false;
1776
1778 if (!OperandType || ->isIntegerTy())
1779 return false;
1780
1781
1782
1784 const SCEV *LoadEv = SE->getSCEV(IncPtr);
1785 const APInt *Step;
1786 if ((LoadEv,
1788 return false;
1789
1790 LLVM_DEBUG(dbgs() << "pointer load scev: " << *LoadEv << "\n");
1791
1793
1794
1795 OpWidth = OperandType->getIntegerBitWidth();
1797 if (OpWidth != StepSize * 8)
1798 return false;
1799 if (OpWidth != 8 && OpWidth != 16 && OpWidth != 32)
1800 return false;
1801 if (OpWidth >= 16)
1802 if (OpWidth != WcharSize * 8)
1803 return false;
1804
1805
1806 for (Instruction &I : *LoopBody)
1807 if (I.mayHaveSideEffects())
1808 return false;
1809
1811 if (!LoopExitBB)
1812 return false;
1813
1814 for (PHINode &PN : LoopExitBB->phis()) {
1816 return false;
1817
1818 const SCEV *Ev = SE->getSCEV(&PN);
1819 if (!Ev)
1820 return false;
1821
1822 LLVM_DEBUG(dbgs() << "loop exit phi scev: " << *Ev << "\n");
1823
1824
1825
1826
1828 if (!AddRecEv || !AddRecEv->isAffine())
1829 return false;
1830
1831
1832
1833
1835 return false;
1836 }
1837
1838 return true;
1839 }
1840
1841public:
1842 const Loop *CurLoop;
1843 ScalarEvolution *SE;
1844 const TargetLibraryInfo *TLI;
1845
1846 unsigned OpWidth;
1847 ConstantInt *StepSizeCI;
1848 const SCEV *LoadBaseEv;
1850};
1851
1852}
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913bool LoopIdiomRecognize::recognizeAndInsertStrLen() {
1915 return false;
1916
1917 StrlenVerifier Verifier(CurLoop, SE, TLI);
1918
1919 if (.isValidStrlenIdiom())
1920 return false;
1921
1926 assert(Preheader && LoopBody && LoopExitBB && LoopTerm &&
1927 "Should be verified to be valid by StrlenVerifier");
1928
1929 if (Verifier.OpWidth == 8) {
1931 return false;
1933 return false;
1934 } else {
1936 return false;
1938 return false;
1939 }
1940
1942 Builder.SetCurrentDebugLocation(CurLoop->getStartLoc());
1944 "strlen_idiom");
1945 Value *MaterialzedBase = Expander.expandCodeFor(
1947 Builder.GetInsertPoint());
1948
1949 Value *StrLenFunc = nullptr;
1950 if (Verifier.OpWidth == 8) {
1951 StrLenFunc = emitStrLen(MaterialzedBase, Builder, *DL, TLI);
1952 } else {
1953 StrLenFunc = emitWcsLen(MaterialzedBase, Builder, *DL, TLI);
1954 }
1955 assert(StrLenFunc && "Failed to emit strlen function.");
1956
1957 const SCEV *StrlenEv = SE->getSCEV(StrLenFunc);
1959 for (PHINode &PN : LoopExitBB->phis()) {
1960
1961
1962
1963
1969
1970
1971
1974 StrlenEv, Base->getType())));
1975
1976 Value *MaterializedPHI = Expander.expandCodeFor(NewEv, NewEv->getType(),
1977 Builder.GetInsertPoint());
1978 Expander.clear();
1981 }
1982
1983
1984
1987
1988
1989
1993 "loop body must have a successor that is it self");
1995 ? Builder.getFalse()
1996 : Builder.getTrue();
1999
2000 ++NumStrLen;
2001 LLVM_DEBUG(dbgs() << " Formed strlen idiom: " << *StrLenFunc << "\n");
2002 ORE.emit([&]() {
2005 << "Transformed " << StrLenFunc->getName() << " loop idiom";
2006 });
2007
2008 return true;
2009}
2010
2011
2012
2013
2014
2016 APInt &Threshold) {
2018 return nullptr;
2019
2022 return nullptr;
2023
2025 if (!CmpConst)
2026 return nullptr;
2027
2030
2032 Threshold = CmpConst->getValue();
2033 return Cond->getOperand(0);
2034 }
2035
2036 return nullptr;
2037}
2038
2039
2040
2044 if (PhiX && PhiX->getParent() == LoopEntry &&
2045 (PhiX->getOperand(0) == DefX || PhiX->getOperand(1) == DefX))
2046 return PhiX;
2047 return nullptr;
2048}
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2081 APInt &Threshold) {
2083
2084 DefX = nullptr;
2085 CntInst = nullptr;
2086 CntPhi = nullptr;
2088
2089
2092 Threshold))
2094 else
2095 return false;
2096
2097
2099 return false;
2100
2103 if (Idx == -1)
2104 return false;
2105
2108 return false;
2109
2110
2111 if (DefX->getOpcode() != Instruction::LShr)
2112 return false;
2113
2114 IntrinID = Intrinsic::ctlz;
2116 if (!Shft || !Shft->isOne())
2117 return false;
2118
2120
2121
2122
2123
2124
2125
2126
2127
2130 if (Inst.getOpcode() != Instruction::Add)
2131 continue;
2132
2135 continue;
2136
2138 if (!Phi)
2139 continue;
2140
2141 CntInst = &Inst;
2142 CntPhi = Phi;
2143 break;
2144 }
2145 if (!CntInst)
2146 return false;
2147
2148 return true;
2149}
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2178
2179
2182 Value *VarX1, *VarX0;
2183 PHINode *PhiX, *CountPhi;
2184
2185 DefX2 = CountInst = nullptr;
2186 VarX1 = VarX0 = nullptr;
2187 PhiX = CountPhi = nullptr;
2189
2190
2191 {
2195 else
2196 return false;
2197 }
2198
2199
2200 {
2201 if (!DefX2 || DefX2->getOpcode() != Instruction::And)
2202 return false;
2203
2205
2208 else {
2211 }
2212 if (!SubOneOp || SubOneOp->getOperand(0) != VarX1)
2213 return false;
2214
2216 if (!Dec ||
2217 !((SubOneOp->getOpcode() == Instruction::Sub && Dec->isOne()) ||
2218 (SubOneOp->getOpcode() == Instruction::Add &&
2220 return false;
2221 }
2222 }
2223
2224
2226 if (!PhiX)
2227 return false;
2228
2229
2230 {
2231 CountInst = nullptr;
2234 if (Inst.getOpcode() != Instruction::Add)
2235 continue;
2236
2238 if (!Inc || !Inc->isOne())
2239 continue;
2240
2242 if (!Phi)
2243 continue;
2244
2245
2246 bool LiveOutLoop = false;
2249 LiveOutLoop = true;
2250 break;
2251 }
2252 }
2253
2254 if (LiveOutLoop) {
2255 CountInst = &Inst;
2256 CountPhi = Phi;
2257 break;
2258 }
2259 }
2260
2261 if (!CountInst)
2262 return false;
2263 }
2264
2265
2266
2267 {
2271 return false;
2272
2273 CntInst = CountInst;
2274 CntPhi = CountPhi;
2275 Var = T;
2276 }
2277
2278 return true;
2279}
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2313 Value *VarX = nullptr;
2314
2315 DefX = nullptr;
2316 CntInst = nullptr;
2317 CntPhi = nullptr;
2319
2320
2324 else
2325 return false;
2326
2327
2328 if (!DefX || !DefX->isShift())
2329 return false;
2330 IntrinID = DefX->getOpcode() == Instruction::Shl ? Intrinsic::cttz :
2331 Intrinsic::ctlz;
2333 if (!Shft || !Shft->isOne())
2334 return false;
2336
2337
2339 if (!PhiX)
2340 return false;
2341
2343
2344
2345
2347 return false;
2348
2349
2350
2351
2352
2353
2354
2355
2358 if (Inst.getOpcode() != Instruction::Add)
2359 continue;
2360
2363 continue;
2364
2366 if (!Phi)
2367 continue;
2368
2369 CntInst = &Inst;
2370 CntPhi = Phi;
2371 break;
2372 }
2373 if (!CntInst)
2374 return false;
2375
2376 return true;
2377}
2378
2379
2380
2381bool LoopIdiomRecognize::isProfitableToInsertFFS(Intrinsic::ID IntrinID,
2382 Value *InitX, bool ZeroCheck,
2383 size_t CanonicalSize) {
2386
2387
2390 std::distance(InstWithoutDebugIt.begin(), InstWithoutDebugIt.end());
2391
2396 return false;
2397
2398 return true;
2399}
2400
2401
2402
2403
2404bool LoopIdiomRecognize::insertFFSIfProfitable(Intrinsic::ID IntrinID,
2408 bool IsCntPhiUsedOutsideLoop = false;
2411 IsCntPhiUsedOutsideLoop = true;
2412 break;
2413 }
2414 bool IsCntInstUsedOutsideLoop = false;
2415 for (User *U : CntInst->users())
2417 IsCntInstUsedOutsideLoop = true;
2418 break;
2419 }
2420
2421
2422 if (IsCntInstUsedOutsideLoop && IsCntPhiUsedOutsideLoop)
2423 return false;
2424
2425
2426
2427
2428 bool ZeroCheck = false;
2429
2430
2432
2433
2434
2435
2436
2437 if (!IsCntPhiUsedOutsideLoop) {
2439 if (!PreCondBB)
2440 return false;
2442 if (!PreCondBI)
2443 return false;
2445 return false;
2446 ZeroCheck = true;
2447 }
2448
2449
2450
2451
2452
2453
2454
2455
2456 size_t IdiomCanonicalSize = 6;
2457 if (!isProfitableToInsertFFS(IntrinID, InitX, ZeroCheck, IdiomCanonicalSize))
2458 return false;
2459
2460 transformLoopToCountable(IntrinID, PH, CntInst, CntPhi, InitX, DefX,
2462 IsCntPhiUsedOutsideLoop);
2463 return true;
2464}
2465
2466
2467
2468
2469bool LoopIdiomRecognize::recognizeAndInsertFFS() {
2470
2472 return false;
2473
2477 PHINode *CntPhi = nullptr;
2479
2481 DefX))
2482 return false;
2483
2484 return insertFFSIfProfitable(IntrinID, InitX, DefX, CntPhi, CntInst);
2485}
2486
2487bool LoopIdiomRecognize::recognizeShiftUntilLessThan() {
2488
2490 return false;
2491
2495 PHINode *CntPhi = nullptr;
2497
2498 APInt LoopThreshold;
2500 CntPhi, DefX, LoopThreshold))
2501 return false;
2502
2503 if (LoopThreshold == 2) {
2504
2505 return insertFFSIfProfitable(IntrinID, InitX, DefX, CntPhi, CntInst);
2506 }
2507
2508
2509 if (LoopThreshold != 4)
2510 return false;
2511
2512
2515 return false;
2516
2517
2518
2521 if (!PreCondBB)
2522 return false;
2524 if (!PreCondBI)
2525 return false;
2526
2527 APInt PreLoopThreshold;
2529 PreLoopThreshold != 2)
2530 return false;
2531
2532 bool ZeroCheck = true;
2533
2534
2535
2536
2537
2538
2539
2540
2541 size_t IdiomCanonicalSize = 6;
2542 if (!isProfitableToInsertFFS(IntrinID, InitX, ZeroCheck, IdiomCanonicalSize))
2543 return false;
2544
2545
2546 transformLoopToCountable(IntrinID, PH, CntInst, CntPhi, InitX, DefX,
2548 false,
2549 true);
2550 return true;
2551}
2552
2553
2554
2555
2556
2557bool LoopIdiomRecognize::recognizePopcount() {
2559 return false;
2560
2561
2562
2563
2564
2565
2566
2568 return false;
2569
2571 if (LoopBody->size() >= 20) {
2572
2573 return false;
2574 }
2575
2576
2579 return false;
2582 return false;
2583
2584
2585
2587 if (!PreCondBB)
2588 return false;
2590 if (!PreCondBI || PreCondBI->isUnconditional())
2591 return false;
2592
2597 return false;
2598
2599 transformLoopToPopcount(PreCondBB, CntInst, CntPhi, Val);
2600 return true;
2601}
2602
2607
2610
2611 return CI;
2612}
2613
2619
2622
2623 return CI;
2624}
2625
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635
2636
2637
2638
2639
2640
2641
2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657void LoopIdiomRecognize::transformLoopToCountable(
2660 bool ZeroCheck, bool IsCntPhiUsedOutsideLoop, bool InsertSub) {
2662
2663
2665 Builder.SetCurrentDebugLocation(DL);
2666
2667
2668
2669
2670
2671
2672
2673 Value *InitXNext;
2674 if (IsCntPhiUsedOutsideLoop) {
2675 if (DefX->getOpcode() == Instruction::AShr)
2676 InitXNext = Builder.CreateAShr(InitX, 1);
2677 else if (DefX->getOpcode() == Instruction::LShr)
2678 InitXNext = Builder.CreateLShr(InitX, 1);
2679 else if (DefX->getOpcode() == Instruction::Shl)
2680 InitXNext = Builder.CreateShl(InitX, 1);
2681 else
2683 } else
2684 InitXNext = InitX;
2687 Type *CountTy = Count->getType();
2688 Count = Builder.CreateSub(
2690 if (InsertSub)
2691 Count = Builder.CreateSub(Count, ConstantInt::get(CountTy, 1));
2693 if (IsCntPhiUsedOutsideLoop)
2694 Count = Builder.CreateAdd(Count, ConstantInt::get(CountTy, 1));
2695
2696 NewCount = Builder.CreateZExtOrTrunc(NewCount, CntInst->getType());
2697
2700
2701
2703 if (!InitConst || !InitConst->isZero())
2704 NewCount = Builder.CreateAdd(NewCount, CntInitVal);
2705 } else {
2706
2707
2708 NewCount = Builder.CreateSub(CntInitVal, NewCount);
2709 }
2710
2711
2712
2713
2714
2715
2716
2717
2718
2722
2725
2726 Builder.SetInsertPoint(LbCond);
2728 TcPhi, ConstantInt::get(CountTy, 1), "tcdec", false, true));
2729
2732
2737 LbCond->setOperand(1, ConstantInt::get(CountTy, 0));
2738
2739
2740
2741 if (IsCntPhiUsedOutsideLoop)
2743 else
2745
2746
2747
2749}
2750
2751void LoopIdiomRecognize::transformLoopToPopcount(BasicBlock *PreCondBB,
2757
2758
2759
2760
2761
2762
2764 Value *PopCnt, *PopCntZext, *NewCount, *TripCnt;
2765 {
2767 NewCount = PopCntZext =
2769
2770 if (NewCount != PopCnt)
2772
2773
2774 TripCnt = NewCount;
2775
2776
2779 if (!InitConst || !InitConst->isZero()) {
2780 NewCount = Builder.CreateAdd(NewCount, CntInitVal);
2782 }
2783 }
2784
2785
2786
2787
2788
2789 {
2791
2792 Value *Opnd0 = PopCntZext;
2793 Value *Opnd1 = ConstantInt::get(PopCntZext->getType(), 0);
2796
2798 Builder.CreateICmp(PreCond->getPredicate(), Opnd0, Opnd1));
2799 PreCondBr->setCondition(NewPreCond);
2800
2802 }
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2825 {
2829
2832
2833 Builder.SetInsertPoint(LbCond);
2835 Builder.CreateSub(TcPhi, ConstantInt::get(Ty, 1),
2836 "tcdec", false, true));
2837
2840
2845 LbCond->setOperand(1, ConstantInt::get(Ty, 0));
2846 }
2847
2848
2849
2850
2852
2853
2854
2856}
2857
2858
2862
2865
2866 template bool match(ITy *V) const {
2867 return L->isLoopInvariant(V) && SubPattern.match(V);
2868 }
2869};
2870
2871
2872template
2876
2877
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
2889
2890
2891
2892
2893
2894
2895
2896
2897
2898
2903 " Performing shift-until-bittest idiom detection.\n");
2904
2905
2908 return false;
2909 }
2910
2913 assert(LoopPreheaderBB && "There is always a loop preheader.");
2914
2916
2917
2918
2920 Value *CmpLHS, *CmpRHS;
2926 return false;
2927 }
2928
2929
2930
2931 auto MatchVariableBitMask = [&]() {
2938 CurLoop))));
2939 };
2940
2941 auto MatchDecomposableConstantBitMask = [&]() {
2943 CmpLHS, CmpRHS, Pred, true,
2944 false, true);
2945 if (Res && Res->Mask.isPowerOf2()) {
2947 Pred = Res->Pred;
2948 CurrX = Res->X;
2949 BitMask = ConstantInt::get(CurrX->getType(), Res->Mask);
2950 BitPos = ConstantInt::get(CurrX->getType(), Res->Mask.logBase2());
2951 return true;
2952 }
2953 return false;
2954 };
2955
2956 if (!MatchVariableBitMask() && !MatchDecomposableConstantBitMask()) {
2958 return false;
2959 }
2960
2961
2963 if (!CurrXPN || CurrXPN->getParent() != LoopHeaderBB) {
2965 return false;
2966 }
2967
2968 BaseX = CurrXPN->getIncomingValueForBlock(LoopPreheaderBB);
2969 NextX =
2971
2973 "Expected BaseX to be available in the preheader!");
2974
2976
2978 return false;
2979 }
2980
2981
2982
2984 "Should only get equality predicates here.");
2985
2986
2990 }
2991
2992
2993
2994 if (TrueBB != LoopHeaderBB) {
2996 return false;
2997 }
2998
2999
3000 return true;
3001}
3002
3003
3004
3005
3006
3007
3008
3009
3010
3011
3012
3013
3014
3015
3016
3017
3018
3019
3020
3021
3022
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032
3033
3034
3035
3036
3037
3038
3039
3040
3041
3042
3043
3044
3045
3046
3047
3048
3049
3050
3051
3052
3053bool LoopIdiomRecognize::recognizeShiftUntilBitTest() {
3054 bool MadeChange = false;
3055
3056 Value *X, *BitMask, *BitPos, *XCurr;
3059 XNext)) {
3061 " shift-until-bittest idiom detection failed.\n");
3062 return MadeChange;
3063 }
3065
3066
3067
3068
3071 assert(LoopPreheaderBB && "There is always a loop preheader.");
3072
3074 assert(SuccessorBB && "There is only a single successor.");
3075
3078
3082
3085
3086
3087
3088
3090 IntrID, Ty, {PoisonValue::get(Ty), Builder.getTrue()});
3094 " Intrinsic is too costly, not beneficial\n");
3095 return MadeChange;
3096 }
3097 if (TTI->getArithmeticInstrCost(Instruction::Shl, Ty, CostKind) >
3100 return MadeChange;
3101 }
3102
3103
3104 MadeChange = true;
3105
3107
3108
3109 std::optionalBasicBlock::iterator InsertPt = std::nullopt;
3111 InsertPt = BitPosI->getInsertionPointAfterDef();
3112 else
3114 if (!InsertPt)
3115 return false;
3119 return U.getUser() != BitPosFrozen;
3120 });
3121 BitPos = BitPosFrozen;
3122 }
3123
3124
3125
3127 BitPos->getName() + ".lowbitmask");
3129 Builder.CreateOr(LowBitMask, BitMask, BitPos->getName() + ".mask");
3130 Value *XMasked = Builder.CreateAnd(X, Mask, X->getName() + ".masked");
3131 CallInst *XMaskedNumLeadingZeros = Builder.CreateIntrinsic(
3132 IntrID, Ty, {XMasked, Builder.getTrue()},
3133 nullptr, XMasked->getName() + ".numleadingzeros");
3134 Value *XMaskedNumActiveBits = Builder.CreateSub(
3135 ConstantInt::get(Ty, Ty->getScalarSizeInBits()), XMaskedNumLeadingZeros,
3136 XMasked->getName() + ".numactivebits", true,
3137 Bitwidth != 2);
3138 Value *XMaskedLeadingOnePos =
3140 XMasked->getName() + ".leadingonepos", false,
3141 Bitwidth > 2);
3142
3143 Value *LoopBackedgeTakenCount = Builder.CreateSub(
3144 BitPos, XMaskedLeadingOnePos, CurLoop->getName() + ".backedgetakencount",
3145 true, true);
3146
3147
3148 Value *LoopTripCount =
3149 Builder.CreateAdd(LoopBackedgeTakenCount, ConstantInt::get(Ty, 1),
3150 CurLoop->getName() + ".tripcount", true,
3151 Bitwidth != 2);
3152
3153
3154
3155
3156
3157 Value *NewX = Builder.CreateShl(X, LoopBackedgeTakenCount);
3160 I->copyIRFlags(XNext, true);
3161
3162 Value *NewXNext;
3163
3164
3165
3166
3172 NewXNext = Builder.CreateShl(X, LoopTripCount);
3173 else {
3174
3175
3176
3177 NewXNext = Builder.CreateShl(NewX, ConstantInt::get(Ty, 1));
3178 }
3179
3182 I->copyIRFlags(XNext, true);
3183
3184
3185
3186
3189
3190
3191
3192
3193 Builder.SetInsertPoint(LoopHeaderBB, LoopHeaderBB->begin());
3194 auto *IV = Builder.CreatePHI(Ty, 2, CurLoop->getName() + ".iv");
3195
3196
3197
3198 Builder.SetInsertPoint(LoopHeaderBB->getTerminator());
3199 auto *IVNext =
3200 Builder.CreateAdd(IV, ConstantInt::get(Ty, 1), IV->getName() + ".next",
3201 true, Bitwidth != 2);
3202
3203
3204 auto *IVCheck = Builder.CreateICmpEQ(IVNext, LoopTripCount,
3205 CurLoop->getName() + ".ivcheck");
3207 const bool HasBranchWeights =
3210
3211 auto *BI = Builder.CreateCondBr(IVCheck, SuccessorBB, LoopHeaderBB);
3212 if (HasBranchWeights) {
3214 std::swap(BranchWeights[0], BranchWeights[1]);
3215
3216
3218 false);
3219 }
3220
3222
3223
3224 IV->addIncoming(ConstantInt::get(Ty, 0), LoopPreheaderBB);
3225 IV->addIncoming(IVNext, LoopHeaderBB);
3226
3227
3228
3229
3231
3232
3233
3235
3236 ++NumShiftUntilBitTest;
3237 return MadeChange;
3238}
3239
3240
3241
3242
3243
3244
3245
3246
3247
3248
3249
3250
3251
3252
3253
3254
3255
3256
3257
3258
3259
3260
3261
3262
3263
3264
3265
3266
3267
3272 const SCEV *&ExtraOffsetExpr,
3273 bool &InvertedCond) {
3275 " Performing shift-until-zero idiom detection.\n");
3276
3277
3280 return false;
3281 }
3282
3283 Instruction *ValShifted, *NBits, *IVNext;
3284 Value *ExtraOffset;
3285
3288 assert(LoopPreheaderBB && "There is always a loop preheader.");
3289
3291
3292
3293
3299 (ValShiftedIsZero,
3303 return false;
3304 }
3305
3306
3307
3311 return false;
3312 }
3313 IntrinID = ValShifted->getOpcode() == Instruction::Shl ? Intrinsic::cttz
3314 : Intrinsic::ctlz;
3315
3316
3317
3322 else if (match(NBits,
3326 ExtraOffsetExpr = SE->getSCEV(ExtraOffset);
3327 else {
3328 IV = NBits;
3330 }
3331
3332
3334 if (!IVPN || IVPN->getParent() != LoopHeaderBB) {
3336 return false;
3337 }
3338
3339 Start = IVPN->getIncomingValueForBlock(LoopPreheaderBB);
3341
3344 return false;
3345 }
3346
3347
3348
3350 "Should only get equality predicates here.");
3351
3352
3354 if (InvertedCond) {
3357 }
3358
3359
3360
3361 if (FalseBB != LoopHeaderBB) {
3363 return false;
3364 }
3365
3366
3367
3368
3369
3370
3371
3372 if (ValShifted->getOpcode() == Instruction::AShr &&
3375 return false;
3376 }
3377
3378
3379 return true;
3380}
3381
3382
3383
3384
3385
3386
3387
3388
3389
3390
3391
3392
3393
3394
3395
3396
3397
3398
3399
3400
3401
3402
3403
3404
3405
3406
3407
3408
3409
3410
3411
3412
3413
3414
3415
3416
3417
3418
3419
3420
3421
3422
3423
3424
3425
3426
3427
3428
3429
3430
3431
3432
3433
3434
3435
3436bool LoopIdiomRecognize::recognizeShiftUntilZero() {
3437 bool MadeChange = false;
3438
3443 const SCEV *ExtraOffsetExpr;
3444 bool InvertedCond;
3446 Start, Val, ExtraOffsetExpr, InvertedCond)) {
3448 " shift-until-zero idiom detection failed.\n");
3449 return MadeChange;
3450 }
3452
3453
3454
3455
3458 assert(LoopPreheaderBB && "There is always a loop preheader.");
3459
3461 assert(SuccessorBB && "There is only a single successor.");
3462
3464 Builder.SetCurrentDebugLocation(IV->getDebugLoc());
3465
3468
3471
3472
3473
3474
3476 IntrID, Ty, {PoisonValue::get(Ty), Builder.getFalse()});
3480 " Intrinsic is too costly, not beneficial\n");
3481 return MadeChange;
3482 }
3483
3484
3485 MadeChange = true;
3486
3487 bool OffsetIsZero = ExtraOffsetExpr->isZero();
3488
3489
3490
3491 CallInst *ValNumLeadingZeros = Builder.CreateIntrinsic(
3492 IntrID, Ty, {Val, Builder.getFalse()},
3493 nullptr, Val->getName() + ".numleadingzeros");
3494 Value *ValNumActiveBits = Builder.CreateSub(
3496 Val->getName() + ".numactivebits", true,
3497 Bitwidth != 2);
3498
3500 Expander.setInsertPoint(&*Builder.GetInsertPoint());
3501 Value *ExtraOffset = Expander.expandCodeFor(ExtraOffsetExpr);
3502
3503 Value *ValNumActiveBitsOffset = Builder.CreateAdd(
3504 ValNumActiveBits, ExtraOffset, ValNumActiveBits->getName() + ".offset",
3505 OffsetIsZero, true);
3506 Value *IVFinal = Builder.CreateIntrinsic(Intrinsic::smax, {Ty},
3507 {ValNumActiveBitsOffset, Start},
3508 nullptr, "iv.final");
3509
3510 auto *LoopBackedgeTakenCount = cast(Builder.CreateSub(
3511 IVFinal, Start, CurLoop->getName() + ".backedgetakencount",
3512 OffsetIsZero, true));
3513
3514
3515
3516 Value *LoopTripCount =
3517 Builder.CreateAdd(LoopBackedgeTakenCount, ConstantInt::get(Ty, 1),
3518 CurLoop->getName() + ".tripcount", true,
3519 Bitwidth != 2);
3520
3521
3522
3523
3524 IV->replaceUsesOutsideBlock(IVFinal, LoopHeaderBB);
3525
3526
3527
3528
3529 Builder.SetInsertPoint(LoopHeaderBB, LoopHeaderBB->begin());
3530 auto *CIV = Builder.CreatePHI(Ty, 2, CurLoop->getName() + ".iv");
3531
3532
3533 Builder.SetInsertPoint(LoopHeaderBB, LoopHeaderBB->getFirstNonPHIIt());
3534 auto *CIVNext =
3535 Builder.CreateAdd(CIV, ConstantInt::get(Ty, 1), CIV->getName() + ".next",
3536 true, Bitwidth != 2);
3537
3538
3539 auto *CIVCheck = Builder.CreateICmpEQ(CIVNext, LoopTripCount,
3540 CurLoop->getName() + ".ivcheck");
3541 auto *NewIVCheck = CIVCheck;
3542 if (InvertedCond) {
3543 NewIVCheck = Builder.CreateNot(CIVCheck);
3544 NewIVCheck->takeName(ValShiftedIsZero);
3545 }
3546
3547
3548 auto *IVDePHId = Builder.CreateAdd(CIV, Start, "", false,
3549 true);
3550 IVDePHId->takeName(IV);
3551
3552
3553 Builder.SetInsertPoint(LoopHeaderBB->getTerminator());
3555 const bool HasBranchWeights =
3558
3559 auto *BI = Builder.CreateCondBr(CIVCheck, SuccessorBB, LoopHeaderBB);
3560 if (HasBranchWeights) {
3561 if (InvertedCond)
3562 std::swap(BranchWeights[0], BranchWeights[1]);
3563
3564
3566 }
3568
3569
3570 CIV->addIncoming(ConstantInt::get(Ty, 0), LoopPreheaderBB);
3571 CIV->addIncoming(CIVNext, LoopHeaderBB);
3572
3573
3574
3575
3577
3578
3579 IV->replaceAllUsesWith(IVDePHId);
3580 IV->eraseFromParent();
3581
3584
3585
3586
3588
3589 ++NumShiftUntilZero;
3590 return MadeChange;
3591}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static const Function * getParent(const Value *V)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Analysis containing CSE Info
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static cl::opt< OutputCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(OutputCostKind::RecipThroughput), cl::values(clEnumValN(OutputCostKind::RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(OutputCostKind::Latency, "latency", "Instruction latency"), clEnumValN(OutputCostKind::CodeSize, "code-size", "Code size"), clEnumValN(OutputCostKind::SizeAndLatency, "size-latency", "Code size and latency"), clEnumValN(OutputCostKind::All, "all", "Print all cost kinds")))
This file defines the DenseMap class.
static const HTTPClientCleanup Cleanup
static bool mayLoopAccessLocation(Value *Ptr, ModRefInfo Access, Loop *L, const SCEV *BECount, unsigned StoreSize, AliasAnalysis &AA, SmallPtrSetImpl< Instruction * > &Ignored)
mayLoopAccessLocation - Return true if the specified loop might access the specified pointer location...
Module.h This file contains the declarations for the Module class.
This header defines various interfaces for pass management in LLVM.
This file defines an InstructionCost class that is used when calculating the cost of an instruction,...
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
static Value * matchCondition(BranchInst *BI, BasicBlock *LoopEntry, bool JmpOnZero=false)
Check if the given conditional branch is based on the comparison between a variable and zero,...
Definition LoopIdiomRecognize.cpp:1709
static PHINode * getRecurrenceVar(Value *VarX, Instruction *DefX, BasicBlock *LoopEntry)
Definition LoopIdiomRecognize.cpp:2041
static CallInst * createFFSIntrinsic(IRBuilder<> &IRBuilder, Value *Val, const DebugLoc &DL, bool ZeroCheck, Intrinsic::ID IID)
Definition LoopIdiomRecognize.cpp:2614
static bool detectShiftUntilLessThanIdiom(Loop *CurLoop, const DataLayout &DL, Intrinsic::ID &IntrinID, Value *&InitX, Instruction *&CntInst, PHINode *&CntPhi, Instruction *&DefX, APInt &Threshold)
Return true if the idiom is detected in the loop.
Definition LoopIdiomRecognize.cpp:2077
static bool detectShiftUntilBitTestIdiom(Loop *CurLoop, Value *&BaseX, Value *&BitMask, Value *&BitPos, Value *&CurrX, Instruction *&NextX)
Return true if the idiom is detected in the loop.
Definition LoopIdiomRecognize.cpp:2899
static bool detectPopcountIdiom(Loop *CurLoop, BasicBlock *PreCondBB, Instruction *&CntInst, PHINode *&CntPhi, Value *&Var)
Return true iff the idiom is detected in the loop.
Definition LoopIdiomRecognize.cpp:2175
static Constant * getMemSetPatternValue(Value *V, const DataLayout *DL)
getMemSetPatternValue - If a strided store of the specified value is safe to turn into a memset....
Definition LoopIdiomRecognize.cpp:421
static CallInst * createPopcntIntrinsic(IRBuilder<> &IRBuilder, Value *Val, const DebugLoc &DL)
Definition LoopIdiomRecognize.cpp:2603
static const SCEV * getNumBytes(const SCEV *BECount, Type *IntPtr, const SCEV *StoreSizeSCEV, Loop *CurLoop, const DataLayout *DL, ScalarEvolution *SE)
Compute the number of bytes as a SCEV from the backedge taken count.
Definition LoopIdiomRecognize.cpp:1031
static bool detectShiftUntilZeroIdiom(Loop *CurLoop, const DataLayout &DL, Intrinsic::ID &IntrinID, Value *&InitX, Instruction *&CntInst, PHINode *&CntPhi, Instruction *&DefX)
Return true if the idiom is detected in the loop.
Definition LoopIdiomRecognize.cpp:2308
static const SCEV * getStartForNegStride(const SCEV *Start, const SCEV *BECount, Type *IntPtr, const SCEV *StoreSizeSCEV, ScalarEvolution *SE)
Definition LoopIdiomRecognize.cpp:1013
static APInt getStoreStride(const SCEVAddRecExpr *StoreEv)
Definition LoopIdiomRecognize.cpp:408
static Value * matchShiftULTCondition(BranchInst *BI, BasicBlock *LoopEntry, APInt &Threshold)
Check if the given conditional branch is based on an unsigned less-than comparison between a variable...
Definition LoopIdiomRecognize.cpp:2015
match_LoopInvariant< Ty > m_LoopInvariant(const Ty &M, const Loop *L)
Matches if the value is loop-invariant.
Definition LoopIdiomRecognize.cpp:2873
static void deleteDeadInstruction(Instruction *I)
Definition LoopIdiomRecognize.cpp:317
static DebugLoc getDebugLoc(MachineBasicBlock::instr_iterator FirstMI, MachineBasicBlock::instr_iterator LastMI)
Return the first DebugLoc that has line number information, given a range of instructions.
This file implements a map that provides insertion order iteration.
This file provides utility analysis objects describing memory locations.
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
Contains a collection of routines for determining if a given instruction is guaranteed to execute if ...
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
static bool isSimple(Instruction *I)
verify safepoint Safepoint IR Verifier
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
static SymbolRef::Type getType(const Symbol *Sym)
This pass exposes codegen information to IR-level passes.
static const uint32_t IV[8]
Class for arbitrary precision integers.
std::optional< uint64_t > tryZExtValue() const
Get zero extended value if possible.
uint64_t getZExtValue() const
Get zero extended value.
unsigned getBitWidth() const
Return the number of bits in the APInt.
int64_t getSExtValue() const
Get sign extended value.
static LLVM_ABI ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_ABI iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction & front() const
InstListType::iterator iterator
Instruction iterators...
LLVM_ABI const_iterator getFirstNonPHIOrDbgOrAlloca() const
Returns an iterator to the first instruction in this block that is not a PHINode, a debug intrinsic,...
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...
LLVM_ABI const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
BinaryOps getOpcode() const
Conditional or Unconditional Branch instruction.
void setCondition(Value *V)
bool isConditional() const
unsigned getNumSuccessors() const
BasicBlock * getSuccessor(unsigned i) const
Value * getCondition() const
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
This class represents a function call, abstracting a target machine's calling convention.
void setPredicate(Predicate P)
Set the predicate for this instruction to the specified value.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLE
signed less or equal
@ ICMP_UGT
unsigned greater than
@ ICMP_ULT
unsigned less than
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Predicate getPredicate() const
Return the predicate for this instruction.
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
static LLVM_ABI Constant * get(ArrayType *T, ArrayRef< Constant * > V)
This is the shared class of boolean and integer constants.
bool isMinusOne() const
This function will return true iff every bit in this constant is set to true.
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
static LLVM_ABI ConstantInt * getBool(LLVMContext &Context, bool V)
This is an important base class in LLVM.
static LLVM_ABI Constant * getAllOnesValue(Type *Ty)
A parsed version of the target data layout string in and methods for querying it.
LLVM_ABI IntegerType * getIndexType(LLVMContext &C, unsigned AddressSpace) const
Returns the type of a GEP index in AddressSpace.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
This class represents a freeze function that returns random concrete value if an operand is either a ...
PointerType * getType() const
Global values are always pointers.
@ PrivateLinkage
Like Internal, but omit from symbol table.
static CRCTable genSarwateTable(const APInt &GenPoly, bool ByteOrderSwapped)
Generate a lookup table of 256 entries by interleaving the generating polynomial.
This instruction compares its operands according to the predicate given to the constructor.
bool isEquality() const
Return true if this predicate is either EQ or NE.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Common base class shared among various IRBuilders.
ConstantInt * getInt1(bool V)
Get a constant value representing either true or false.
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
LLVM_ABI 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.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
LLVM_ABI bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
LLVM_ABI bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_ABI const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
LLVM_ABI void setAAMetadata(const AAMDNodes &N)
Sets the AA metadata on this instruction from the AAMDNodes structure.
LLVM_ABI bool isAtomic() const LLVM_READONLY
Return true if this instruction has an AtomicOrdering of unordered or higher.
LLVM_ABI void insertBefore(InstListType::iterator InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified position.
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
LLVM_ABI const Function * getFunction() const
Return the function this instruction belongs to.
LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
LLVM_ABI AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
An instruction for reading from memory.
unsigned getPointerAddressSpace() const
Returns the address space of the pointer operand.
Value * getPointerOperand()
bool isVolatile() const
Return true if this is a load from a volatile memory location.
Align getAlign() const
Return the alignment of the access that is being performed.
static LocationSize precise(uint64_t Value)
static constexpr LocationSize afterPointer()
Any location after the base pointer (but still within the underlying object).
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
bool isOutermost() const
Return true if the loop does not have a parent (natural) loop.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
unsigned getNumBlocks() const
Get the number of blocks in this loop in constant time.
unsigned getNumBackEdges() const
Calculate the number of back edges to the loop header.
BlockT * getHeader() const
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
void getUniqueExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop.
block_iterator block_begin() const
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition LoopIdiomRecognize.cpp:293
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Represents a single loop in the control flow graph.
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
ICmpInst * getLatchCmpInst() const
Get the latch condition instruction.
StringRef getName() const
PHINode * getCanonicalInductionVariable() const
Check to see if the loop has a canonical induction variable: an integer recurrence that starts at 0 a...
This class wraps the llvm.memcpy intrinsic.
Value * getLength() const
Value * getDest() const
This is just like getRawDest, but it strips off any cast instructions (including addrspacecast) that ...
MaybeAlign getDestAlign() const
bool isForceInlined() const
This class wraps the llvm.memset and llvm.memset.inline intrinsics.
MaybeAlign getSourceAlign() const
Value * getSource() const
This is just like getRawSource, but it strips off any cast instructions that feed it,...
Representation for a specific memory location.
An analysis that produces MemorySSA for a function.
Encapsulates MemorySSA, including all data associated with memory accesses.
A Module instance is used to store all the information related to an LLVM module.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
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...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
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.
This node represents a polynomial recurrence on the trip count of the specified loop.
const SCEV * getStart() const
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
This class represents a constant integer value.
ConstantInt * getValue() const
const APInt & getAPInt() const
Helper to remove instructions inserted during SCEV expansion, unless they are marked as used.
This class uses information about analyze scalars to rewrite expressions in canonical form.
const SCEV * getOperand(unsigned i) const
This class represents an analyzed expression in the program.
LLVM_ABI bool isOne() const
Return true if the expression is a constant one.
LLVM_ABI bool isZero() const
Return true if the expression is a constant zero.
LLVM_ABI bool isNonConstantNegative() const
Return true if the specified scev is negated, but not a constant.
LLVM_ABI Type * getType() const
Return the LLVM type of this SCEV expression.
The main scalar evolution driver.
const DataLayout & getDataLayout() const
Return the DataLayout associated with the module this SCEV instance is operating on.
LLVM_ABI bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
LLVM_ABI const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
LLVM_ABI const SCEV * getConstant(ConstantInt *V)
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
LLVM_ABI const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)
A version of getTripCountFromExitCount below which always picks an evaluation type which can not resu...
LLVM_ABI void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
LLVM_ABI bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
LLVM_ABI bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
LLVM_ABI const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
LLVM_ABI bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
LLVM_ABI const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
LLVM_ABI const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
LLVM_ABI const SCEV * getTruncateOrZeroExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
LLVM_ABI const SCEV * getTruncateOrSignExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
A vector that has set insertion semantics.
size_type count(const_arg_type key) const
Count the number of elements of a given key in the SetVector.
bool insert(const value_type &X)
Insert a new element into the SetVector.
Simple and conservative implementation of LoopSafetyInfo that can give false-positive answers to its ...
void computeLoopSafetyInfo(const Loop *CurLoop) override
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
bool anyBlockMayThrow() const override
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
void insert_range(Range &&R)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Value * getValueOperand()
Value * getPointerOperand()
StringRef - Represent a constant reference to a string, i.e.
Provides information about what library functions are available for the current target.
unsigned getWCharSize(const Module &M) const
Returns the size of the wchar_t type in bytes or 0 if the size is unknown.
bool has(LibFunc F) const
Tests whether a library function is available.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
TargetCostKind
The kind of cost model.
@ TCK_SizeAndLatency
The weighted sum of size and latency.
@ TCC_Basic
The cost of a typical 'add' instruction.
Triple - Helper class for working with autoconf configuration names.
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.
LLVM_ABI unsigned getIntegerBitWidth() const
LLVM_ABI unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
static LLVM_ABI IntegerType * getInt8Ty(LLVMContext &C)
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
LLVM_ABI unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
bool isFloatingPointTy() const
Return true if this is one of the floating-point types.
bool isIntOrPtrTy() const
Return true if this is an integer type or a pointer type.
static LLVM_ABI IntegerType * getIntNTy(LLVMContext &C, unsigned N)
A Use represents the edge between a Value definition and its users.
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
LLVM_ABI void replaceUsesWithIf(Value *New, llvm::function_ref< bool(Use &U)> ShouldReplace)
Go through the uses list for this definition and make each use point to "V" if the callback ShouldRep...
LLVM_ABI void replaceUsesOutsideBlock(Value *V, BasicBlock *BB)
replaceUsesOutsideBlock - Go through the uses list for this definition and make each use point to "V"...
LLVM_ABI LLVMContext & getContext() const
All values hold a context through their type.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
LLVM_ABI void takeName(Value *V)
Transfer the name from V to this value.
Value handle that is nullable, but tries to track the Value.
constexpr ScalarTy getFixedValue() const
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
const ParentTy * getParent() const
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Abstract Attribute helper functions.
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
constexpr char Attrs[]
Key for Kernel::Metadata::mAttrs.
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.
@ C
The default llvm calling convention, compatible with C.
@ BasicBlock
Various leaf nodes.
OperandType
Operands are tagged with one of the values of this enum.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(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.
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.
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)
Combine two pattern matchers matching L && R.
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.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
BinOpPred_match< LHS, RHS, is_shift_op > m_Shift(const LHS &L, const RHS &R)
Matches shift operations.
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
cst_pred_ty< icmp_pred_with_threshold > m_SpecificInt_ICMP(ICmpInst::Predicate Predicate, const APInt &Threshold)
Match an integer or vector with every element comparing 'pred' (eg/ne/...) to Threshold.
bind_cst_ty m_scev_APInt(const APInt *&C)
Match an SCEV constant and bind it to an APInt.
class_match< const SCEVConstant > m_SCEVConstant()
specificloop_ty m_SpecificLoop(const Loop *L)
SCEVAffineAddRec_match< Op0_t, Op1_t, class_match< const Loop > > m_scev_AffineAddRec(const Op0_t &Op0, const Op1_t &Op1)
bool match(const SCEV *S, const Pattern &P)
specificscev_ty m_scev_Specific(const SCEV *S)
Match if we have a specific specified SCEV.
class_match< const SCEV > m_SCEV()
initializer< Ty > init(const Ty &Val)
LocationClass< Ty > location(Ty &L)
DiagnosticInfoOptimizationBase::Argument NV
DiagnosticInfoOptimizationBase::setExtraArgs setExtraArgs
This is an optimization pass for GlobalISel generic memory operations.
FunctionAddr VTableAddr Value
LLVM_ABI bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
static cl::opt< bool, true > EnableLIRPWcslen("disable-loop-idiom-wcslen", cl::desc("Proceed with loop idiom recognize pass, " "enable conversion of loop(s) to wcslen."), cl::location(DisableLIRP::Wcslen), cl::init(false), cl::ReallyHidden)
static cl::opt< bool, true > DisableLIRPMemcpy("disable-" DEBUG_TYPE "-memcpy", cl::desc("Proceed with loop idiom recognize pass, but do " "not convert loop(s) to memcpy."), cl::location(DisableLIRP::Memcpy), cl::init(false), cl::ReallyHidden)
decltype(auto) dyn_cast(const From &Val)
dyn_cast - Return the argument parameter cast to the specified type.
static cl::opt< bool, true > DisableLIRPStrlen("disable-loop-idiom-strlen", cl::desc("Proceed with loop idiom recognize pass, but do " "not convert loop(s) to strlen."), cl::location(DisableLIRP::Strlen), cl::init(false), cl::ReallyHidden)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Value * GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, const DataLayout &DL, bool AllowNonInbounds=true)
Analyze the specified pointer to see if it can be expressed as a base pointer plus a constant offset.
static cl::opt< bool > ForceMemsetPatternIntrinsic("loop-idiom-force-memset-pattern-intrinsic", cl::desc("Use memset.pattern intrinsic whenever possible"), cl::init(false), cl::Hidden)
LLVM_ABI 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...
LLVM_ABI void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected, bool ElideAllZero=false)
Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...
AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager
The loop analysis manager.
OutputIt transform(R &&Range, OutputIt d_first, UnaryFunction F)
Wrapper function around std::transform to apply a function to a range and store the result elsewhere.
LLVM_ABI bool isMustProgress(const Loop *L)
Return true if this loop can be assumed to make progress.
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
FunctionAddr VTableAddr Count
bool isModOrRefSet(const ModRefInfo MRI)
LLVM_ABI Value * emitStrLen(Value *Ptr, IRBuilderBase &B, const DataLayout &DL, const TargetLibraryInfo *TLI)
Emit a call to the strlen function to the builder, for the specified pointer.
bool isa(const From &Val)
isa - Return true if the parameter to the template is an instance of one of the template type argu...
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
@ ModRef
The access may reference and may modify the value stored in memory.
@ Mod
The access may modify the value stored in memory.
static cl::opt< bool, true > DisableLIRPHashRecognize("disable-" DEBUG_TYPE "-hashrecognize", cl::desc("Proceed with loop idiom recognize pass, " "but do not optimize CRC loops."), cl::location(DisableLIRP::HashRecognize), cl::init(false), cl::ReallyHidden)
FunctionAddr VTableAddr uintptr_t uintptr_t Data
LLVM_ABI bool VerifyMemorySSA
Enables verification of MemorySSA.
LLVM_ABI bool isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL, ScalarEvolution &SE, bool CheckType=true)
Returns true if the memory operations A and B are consecutive.
DWARFExpression::Operation Op
LLVM_ABI bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
LLVM_ABI Value * emitWcsLen(Value *Ptr, IRBuilderBase &B, const DataLayout &DL, const TargetLibraryInfo *TLI)
Emit a call to the wcslen function to the builder, for the specified pointer.
LLVM_ABI bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
decltype(auto) cast(const From &Val)
cast - Return the argument parameter cast to the specified type.
LLVM_ABI PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
LLVM_ABI Value * isBytewiseValue(Value *V, const DataLayout &DL)
If the specified value can be set by repeating the same byte in memory, return the i8 value that it i...
static cl::opt< bool > UseLIRCodeSizeHeurs("use-lir-code-size-heurs", cl::desc("Use loop idiom recognition code size heuristics when compiling " "with -Os/-Oz"), cl::init(true), cl::Hidden)
LLVM_ABI bool RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
If the specified value is an effectively dead PHI node, due to being a def-use chain of single-use no...
cl::opt< bool > ProfcheckDisableMetadataFixes("profcheck-disable-metadata-fixes", cl::Hidden, cl::init(false), cl::desc("Disable metadata propagation fixes discovered through Issue #147390"))
static cl::opt< bool, true > DisableLIRPMemset("disable-" DEBUG_TYPE "-memset", cl::desc("Proceed with loop idiom recognize pass, but do " "not convert loop(s) to memset."), cl::location(DisableLIRP::Memset), cl::init(false), cl::ReallyHidden)
static cl::opt< bool, true > DisableLIRPAll("disable-" DEBUG_TYPE "-all", cl::desc("Options to disable Loop Idiom Recognize Pass."), cl::location(DisableLIRP::All), cl::init(false), cl::ReallyHidden)
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
AAResults AliasAnalysis
Temporary typedef for legacy code that uses a generic AliasAnalysis pointer or reference.
LLVM_ABI bool isKnownNonNegative(const Value *V, const SimplifyQuery &SQ, unsigned Depth=0)
Returns true if the give value is known to be non-negative.
std::optional< DecomposedBitTest > decomposeBitTestICmp(Value *LHS, Value *RHS, CmpInst::Predicate Pred, bool LookThroughTrunc=true, bool AllowNonZeroC=false, bool DecomposeAnd=false)
Decompose an icmp into the form ((X & Mask) pred C) if possible.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
LLVM_ABI AAMDNodes merge(const AAMDNodes &Other) const
Given two sets of AAMDNodes applying to potentially different locations, determine the best AAMDNodes...
AAMDNodes extendTo(ssize_t Len) const
Create a new AAMDNode that describes this AAMDNode after extending it to apply to a series of bytes o...
static bool Memcpy
When true, Memcpy is disabled.
static bool Wcslen
When true, Wcslen is disabled.
static bool Strlen
When true, Strlen is disabled.
static bool HashRecognize
When true, HashRecognize is disabled.
static bool Memset
When true, Memset is disabled.
static bool All
When true, the entire pass is disabled.
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
TargetTransformInfo & TTI
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
The structure that is returned when a polynomial algorithm was recognized by the analysis.
Match loop-invariant value.
Definition LoopIdiomRecognize.cpp:2859
bool match(ITy *V) const
Definition LoopIdiomRecognize.cpp:2866
match_LoopInvariant(const SubPattern_t &SP, const Loop *L)
Definition LoopIdiomRecognize.cpp:2863
const Loop * L
Definition LoopIdiomRecognize.cpp:2861
SubPattern_t SubPattern
Definition LoopIdiomRecognize.cpp:2860