LLVM: lib/Target/Hexagon/HexagonLoopIdiomRecognition.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
41#include "llvm/IR/IntrinsicsHexagon.h"
63#include
64#include
65#include
66#include
67#include
68#include
69#include
70#include
71#include
72#include
73#include
74#include
75
76#define DEBUG_TYPE "hexagon-lir"
77
78using namespace llvm;
79
82 cl::desc("Disable generation of memcpy in loop idiom recognition"));
83
86 cl::desc("Disable generation of memmove in loop idiom recognition"));
87
90 "check guarding the memmove."));
91
94 cl::desc("Threshold (in bytes) to perform the transformation, if the "
95 "runtime loop count (mem transfer size) is known at compile-time."));
96
99 cl::desc("Only enable generating memmove in non-nested loops"));
100
103 cl::desc("Enable Hexagon-specific memcpy for volatile destination."));
104
106 cl::Hidden, cl::desc("Maximum number of simplification steps in HLIR"));
107
108namespace {
109
110class HexagonLoopIdiomRecognize {
111public:
115 : AA(AA), DT(DT), LF(LF), TLI(TLI), SE(SE) {}
116
117 bool run(Loop *L);
118
119private:
120 int getSCEVStride(const SCEVAddRecExpr *StoreEv);
121 bool isLegalStore(Loop *CurLoop, StoreInst *SI);
122 void collectStores(Loop *CurLoop, BasicBlock *BB,
123 SmallVectorImpl<StoreInst *> &Stores);
124 bool processCopyingStore(Loop *CurLoop, StoreInst *SI, const SCEV *BECount);
125 bool coverLoop(Loop *L, SmallVectorImpl<Instruction *> &Insts) const;
126 bool runOnLoopBlock(Loop *CurLoop, BasicBlock *BB, const SCEV *BECount,
127 SmallVectorImpl<BasicBlock *> &ExitBlocks);
128 bool runOnCountableLoop(Loop *L);
129
131 const DataLayout *DL;
132 DominatorTree *DT;
133 LoopInfo *LF;
134 const TargetLibraryInfo *TLI;
135 ScalarEvolution *SE;
136 bool HasMemcpy, HasMemmove;
137};
138
139class HexagonLoopIdiomRecognizeLegacyPass : public LoopPass {
140public:
141 static char ID;
142
143 explicit HexagonLoopIdiomRecognizeLegacyPass() : LoopPass(ID) {}
144
145 StringRef getPassName() const override {
146 return "Recognize Hexagon-specific loop idioms";
147 }
148
149 void getAnalysisUsage(AnalysisUsage &AU) const override {
154 AU.addRequired();
155 AU.addRequired();
156 AU.addRequired();
157 AU.addPreserved();
158 }
159
160 bool runOnLoop(Loop *L, LPPassManager &LPM) override;
161};
162
163struct Simplifier {
164 struct Rule {
165 using FuncType = std::function<Value *(Instruction *, LLVMContext &)>;
166 Rule(StringRef N, FuncType F) : Name(N), Fn(F) {}
167 StringRef Name;
168 FuncType Fn;
169 };
170
171 void addRule(StringRef N, const Rule::FuncType &F) {
172 Rules.push_back(Rule(N, F));
173 }
174
175private:
176 struct WorkListType {
177 WorkListType() = default;
178
179 void push_back(Value *V) {
180
181 if (S.insert(V).second)
182 Q.push_back(V);
183 }
184
185 Value *pop_front_val() {
187 Q.pop_front();
188 S.erase(V);
189 return V;
190 }
191
192 bool empty() const { return Q.empty(); }
193
194 private:
195 std::deque<Value *> Q;
196 std::set<Value *> S;
197 };
198
199 using ValueSetType = std::set<Value *>;
200
201 std::vector Rules;
202
203public:
204 struct Context {
205 using ValueMapType = DenseMap<Value *, Value *>;
206
208 ValueSetType Used;
209 ValueSetType Clones;
210 LLVMContext &Ctx;
211
212 Context(Instruction *Exp)
215 }
216
217 ~Context() { cleanup(); }
218
219 void print(raw_ostream &OS, const Value *V) const;
221
222 private:
223 friend struct Simplifier;
224
227
228 template void traverse(Value *V, FuncT F);
229 void record(Value *V);
231 void unuse(Value *V);
232
233 bool equal(const Instruction *I, const Instruction *J) const;
238 };
239
241};
242
243 struct PE {
244 PE(const Simplifier::Context &c, Value *v = nullptr) : C(c), V(v) {}
245
246 const Simplifier::Context &C;
248 };
249
252 P.C.print(OS, P.V ? P.V : P.C.Root);
253 return OS;
254 }
255
256}
257
258char HexagonLoopIdiomRecognizeLegacyPass::ID = 0;
259
261 "Recognize Hexagon-specific loop idioms", false, false)
270 "Recognize Hexagon-specific loop idioms", false, false)
271
272template
273void Simplifier::Context::traverse(Value *V, FuncT F) {
274 WorkListType Q;
275 Q.push_back(V);
276
277 while (!Q.empty()) {
278 Instruction *U = dyn_cast(Q.pop_front_val());
279 if (!U || U->getParent())
280 continue;
281 if (!F(U))
282 continue;
283 for (Value *Op : U->operands())
284 Q.push_back(Op);
285 }
286}
287
288void Simplifier::Context::print(raw_ostream &OS, const Value *V) const {
290 if (!U) {
291 OS << V << '(' << *V << ')';
292 return;
293 }
294
295 if (U->getParent()) {
296 OS << U << '(';
297 U->printAsOperand(OS, true);
298 OS << ')';
299 return;
300 }
301
302 unsigned N = U->getNumOperands();
303 if (N != 0)
304 OS << U << '(';
305 OS << U->getOpcodeName();
306 for (const Value *Op : U->operands()) {
307 OS << ' ';
309 }
310 if (N != 0)
311 OS << ')';
312}
313
314void Simplifier::Context::initialize(Instruction *Exp) {
315
316
317
318 ValueMapType M;
320 WorkListType Q;
321 Q.push_back(Exp);
322
323 while (!Q.empty()) {
324 Value *V = Q.pop_front_val();
325 if (M.contains(V))
326 continue;
329 continue;
330 for (Value *Op : U->operands())
331 Q.push_back(Op);
332 M.insert({U, U->clone()});
333 }
334 }
335
336 for (std::pair<Value*,Value*> P : M) {
338 for (unsigned i = 0, n = U->getNumOperands(); i != n; ++i) {
339 auto F = M.find(U->getOperand(i));
341 U->setOperand(i, F->second);
342 }
343 }
344
347 Root = R->second;
348
349 record(Root);
350 use(Root);
351}
352
353void Simplifier::Context::record(Value *V) {
354 auto Record = [this](Instruction *U) -> bool {
355 Clones.insert(U);
356 return true;
357 };
358 traverse(V, Record);
359}
360
361void Simplifier::Context::use(Value *V) {
363 Used.insert(U);
364 return true;
365 };
366 traverse(V, Use);
367}
368
369void Simplifier::Context::unuse(Value *V) {
371 return;
372
373 auto Unuse = [this](Instruction *U) -> bool {
374 if (->use_empty())
375 return false;
376 Used.erase(U);
377 return true;
378 };
379 traverse(V, Unuse);
380}
381
383 if (Tree == OldV)
384 return NewV;
385 if (OldV == NewV)
386 return Tree;
387
388 WorkListType Q;
389 Q.push_back(Tree);
390 while (!Q.empty()) {
392
393 if (!U || U->getParent())
394 continue;
395 for (unsigned i = 0, n = U->getNumOperands(); i != n; ++i) {
396 Value *Op = U->getOperand(i);
397 if (Op == OldV) {
398 U->setOperand(i, NewV);
399 unuse(OldV);
400 } else {
401 Q.push_back(Op);
402 }
403 }
404 }
405 return Tree;
406}
407
408void Simplifier::Context::replace(Value *OldV, Value *NewV) {
409 if (Root == OldV) {
410 Root = NewV;
411 use(Root);
412 return;
413 }
414
415
416
417
418
419
420
421 WorkListType Q;
422 Q.push_back(NewV);
423 while (!Q.empty()) {
424 Value *V = Q.pop_front_val();
426 if (!U || U->getParent())
427 continue;
428 if (Value *DupV = find(Root, V)) {
429 if (DupV != V)
430 NewV = subst(NewV, V, DupV);
431 } else {
432 for (Value *Op : U->operands())
433 Q.push_back(Op);
434 }
435 }
436
437
438 Root = subst(Root, OldV, NewV);
439 use(Root);
440}
441
442void Simplifier::Context::cleanup() {
443 for (Value *V : Clones) {
445 if (->getParent())
446 U->dropAllReferences();
447 }
448
449 for (Value *V : Clones) {
451 if (->getParent())
452 U->deleteValue();
453 }
454}
455
456bool Simplifier::Context::equal(const Instruction *I,
457 const Instruction *J) const {
458 if (I == J)
459 return true;
460 if (->isSameOperationAs(J))
461 return false;
463 return I->isIdenticalTo(J);
464
465 for (unsigned i = 0, n = I->getNumOperands(); i != n; ++i) {
467 if (OpI == OpJ)
468 continue;
471 if (InI && InJ) {
472 if ((InI, InJ))
473 return false;
474 } else if (InI != InJ || !InI)
475 return false;
476 }
477 return true;
478}
479
482 WorkListType Q;
483 Q.push_back(Tree);
484
485 while (!Q.empty()) {
486 Value *V = Q.pop_front_val();
487 if (V == Sub)
488 return V;
490 if (!U || U->getParent())
491 continue;
492 if (SubI && equal(SubI, U))
493 return U;
495 for (Value *Op : U->operands())
496 Q.push_back(Op);
497 }
498 return nullptr;
499}
500
501void Simplifier::Context::link(Instruction *I, BasicBlock *B,
503 if (I->getParent())
504 return;
505
506 for (Value *Op : I->operands()) {
509 }
510
512}
513
514Value *Simplifier::Context::materialize(BasicBlock *B,
518 return Root;
519}
520
522 WorkListType Q;
523 Q.push_back(C.Root);
524 unsigned Count = 0;
526
527 while (!Q.empty()) {
528 if (Count++ >= Limit)
529 break;
531 if (!U || U->getParent() || .Used.count(U))
532 continue;
534 for (Rule &R : Rules) {
536 if (!W)
537 continue;
539 C.record(W);
540 C.replace(U, W);
541 Q.push_back(C.Root);
542 break;
543 }
545 for (Value *Op : U->operands())
546 Q.push_back(Op);
547 }
548 }
549 return Count < Limit ? C.Root : nullptr;
550}
551
552
553
554
555
556
557
558namespace {
559
560 class PolynomialMultiplyRecognize {
561 public:
562 explicit PolynomialMultiplyRecognize(Loop *loop, const DataLayout &dl,
563 const DominatorTree &dt, const TargetLibraryInfo &tli,
564 ScalarEvolution &se)
565 : CurLoop(loop), DL(dl), DT(dt), TLI(tli), SE(se) {}
566
567 bool recognize();
568
569 private:
570 using ValueSeq = SetVector<Value *>;
571
572 IntegerType *getPmpyType() const {
573 LLVMContext &Ctx = CurLoop->getHeader()->getParent()->getContext();
575 }
576
577 bool isPromotableTo(Value *V, IntegerType *Ty);
578 void promoteTo(Instruction *In, IntegerType *DestTy, BasicBlock *LoopB);
579 bool promoteTypes(BasicBlock *LoopB, BasicBlock *ExitB);
580
581 Value *getCountIV(BasicBlock *BB);
583 void classifyCycle(Instruction *DivI, ValueSeq &Cycle, ValueSeq &Early,
584 ValueSeq &Late);
585 bool classifyInst(Instruction *UseI, ValueSeq &Early, ValueSeq &Late);
586 bool commutesWithShift(Instruction *I);
587 bool highBitsAreZero(Value *V, unsigned IterCount);
588 bool keepsHighBitsZero(Value *V, unsigned IterCount);
589 bool isOperandShifted(Instruction *I, Value *Op);
590 bool convertShiftsToLeft(BasicBlock *LoopB, BasicBlock *ExitB,
591 unsigned IterCount);
592 void cleanupLoopBody(BasicBlock *LoopB);
593
594 struct ParsedValues {
595 ParsedValues() = default;
596
599 Value *Q = nullptr;
603 unsigned IterCount = 0;
604 bool Left = false;
605 bool Inv = false;
606 };
607
608 bool matchLeftShift(SelectInst *SelI, Value *CIV, ParsedValues &PV);
609 bool matchRightShift(SelectInst *SelI, ParsedValues &PV);
610 bool scanSelect(SelectInst *SI, BasicBlock *LoopB, BasicBlock *PrehB,
611 Value *CIV, ParsedValues &PV, bool PreScan);
612 unsigned getInverseMxN(unsigned QP);
614
615 void setupPreSimplifier(Simplifier &S);
616 void setupPostSimplifier(Simplifier &S);
617
618 Loop *CurLoop;
619 const DataLayout &DL;
620 const DominatorTree &DT;
621 const TargetLibraryInfo &TLI;
622 ScalarEvolution &SE;
623 };
624
625}
626
627Value *PolynomialMultiplyRecognize::getCountIV(BasicBlock *BB) {
629 if (std::distance(PI, PE) != 2)
630 return nullptr;
631 BasicBlock *PB = (*PI == BB) ? *std::next(PI) : *PI;
632
635 Value *InitV = PN->getIncomingValueForBlock(PB);
637 continue;
638 Value *IterV = PN->getIncomingValueForBlock(BB);
640 if (!BO)
641 continue;
642 if (BO->getOpcode() != Instruction::Add)
643 continue;
644 Value *IncV = nullptr;
645 if (BO->getOperand(0) == PN)
646 IncV = BO->getOperand(1);
647 else if (BO->getOperand(1) == PN)
648 IncV = BO->getOperand(0);
649 if (IncV == nullptr)
650 continue;
651
653 if (T->isOne())
654 return PN;
655 }
656 return nullptr;
657}
658
660 for (auto UI = I->user_begin(), UE = I->user_end(); UI != UE;) {
661 Use &TheUse = UI.getUse();
662 ++UI;
664 if (BB == II->getParent())
665 II->replaceUsesOfWith(I, J);
666 }
667}
668
669bool PolynomialMultiplyRecognize::matchLeftShift(SelectInst *SelI,
670 Value *CIV, ParsedValues &PV) {
671
672
673
674
675
676
677
681
682 using namespace PatternMatch;
683
684 CmpPredicate P;
685 Value *A = nullptr, *B = nullptr, *C = nullptr;
686
689 return false;
691 return false;
692
693
694
695 Value *X = nullptr, *Sh1 = nullptr;
696
698 Sh1 = A;
701 Sh1 = B;
703 } else {
704
705
706 return false;
707 }
708
709 bool TrueIfZero;
710
711
714 else if (C == Sh1)
716 else
717 return false;
718
719
720
721
722
723 Value *ShouldSameV = nullptr, *ShouldXoredV = nullptr;
724 if (TrueIfZero) {
725 ShouldSameV = TrueV;
726 ShouldXoredV = FalseV;
727 } else {
728 ShouldSameV = FalseV;
729 ShouldXoredV = TrueV;
730 }
731
732 Value *Q = nullptr, *R = nullptr, *Y = nullptr, *Z = nullptr;
735
736
737
738 if (ShouldSameV == Y)
740 else if (ShouldSameV == Z)
742 else
743 return false;
744 R = ShouldSameV;
745
746
747
748
749 } else if (match(ShouldSameV, m_Zero())) {
750
751
753 return false;
754 T = ShouldXoredV;
755
756
757
760 return false;
761
762
763 } else
764 return false;
765
766
767
768
769
772 return false;
773
774
775
776 PV.X = X;
777 PV.Q = Q;
778 PV.R = R;
779 PV.Left = true;
780 return true;
781}
782
783bool PolynomialMultiplyRecognize::matchRightShift(SelectInst *SelI,
784 ParsedValues &PV) {
785
786
787
788
789
790
791
795
796 using namespace PatternMatch;
797
799 CmpPredicate P;
800 bool TrueIfZero;
801
804 return false;
805
806
810 return false;
811
812
814 } else
815 return false;
816
819 return false;
820
821
822
823 Value *R = nullptr, *Q = nullptr;
824 if (TrueIfZero) {
825
826
828 return false;
829
831 return false;
832
833
834 } else {
835
836
838 return false;
839
841 return false;
842
843
844 }
845
846 PV.X = X;
847 PV.Q = Q;
848 PV.R = R;
849 PV.Left = false;
850 return true;
851}
852
853bool PolynomialMultiplyRecognize::scanSelect(SelectInst *SelI,
854 BasicBlock *LoopB, BasicBlock *PrehB, Value *CIV, ParsedValues &PV,
855 bool PreScan) {
856 using namespace PatternMatch;
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895 if (matchLeftShift(SelI, CIV, PV)) {
896
897 if (PreScan)
898 return true;
899
900
902 if (!RPhi)
903 return false;
904 if (SelI != RPhi->getIncomingValueForBlock(LoopB))
905 return false;
906 PV.Res = SelI;
907
908
909
910 if (CurLoop->isLoopInvariant(PV.X)) {
911 PV.P = PV.X;
912 PV.Inv = false;
913 } else {
914
915
916
917
918 PV.Inv = true;
919 if (PV.X != PV.R) {
920 Value *Var = nullptr, *Inv = nullptr, *X1 = nullptr, *X2 = nullptr;
922 return false;
925 if (!I1 || I1->getParent() != LoopB) {
926 Var = X2;
927 Inv = X1;
928 } else if (!I2 || I2->getParent() != LoopB) {
929 Var = X1;
930 Inv = X2;
931 } else
932 return false;
933 if (Var != PV.R)
934 return false;
935 PV.M = Inv;
936 }
937
938
939 Value *EntryP = RPhi->getIncomingValueForBlock(PrehB);
940 PV.P = EntryP;
941 }
942
943 return true;
944 }
945
946 if (matchRightShift(SelI, PV)) {
947
948
950 return false;
951 if (PreScan)
952 return true;
953
954 return false;
955 }
956
957 return false;
958}
959
960bool PolynomialMultiplyRecognize::isPromotableTo(Value *Val,
961 IntegerType *DestTy) {
963 if ( || T->getBitWidth() > DestTy->getBitWidth())
964 return false;
965 if (T->getBitWidth() == DestTy->getBitWidth())
966 return true;
967
968
969
970
971
972
974 if (!In)
975 return true;
976
977
978 switch (In->getOpcode()) {
979 case Instruction::PHI:
980 case Instruction::ZExt:
981 case Instruction::And:
982 case Instruction::Or:
983 case Instruction::Xor:
984 case Instruction::LShr:
985 case Instruction::Select:
986 case Instruction::Trunc:
987 return true;
988 case Instruction::ICmp:
990 return CI->isEquality() || CI->isUnsigned();
992 case Instruction::Add:
993 return In->hasNoSignedWrap() && In->hasNoUnsignedWrap();
994 }
995 return false;
996}
997
998void PolynomialMultiplyRecognize::promoteTo(Instruction *In,
999 IntegerType *DestTy, BasicBlock *LoopB) {
1000 Type *OrigTy = In->getType();
1001 assert(!OrigTy->isVoidTy() && "Invalid instruction to promote");
1002
1003
1004 if (->getType()->isIntegerTy(1))
1005 In->mutateType(DestTy);
1006 unsigned DestBW = DestTy->getBitWidth();
1007
1008
1010 unsigned N = P->getNumIncomingValues();
1011 for (unsigned i = 0; i != N; ++i) {
1012 BasicBlock *InB = P->getIncomingBlock(i);
1013 if (InB == LoopB)
1014 continue;
1015 Value *InV = P->getIncomingValue(i);
1017
1018 if (Ty != P->getType()) {
1019
1020
1023 P->setIncomingValue(i, InV);
1024 }
1025 }
1027 Value *Op = Z->getOperand(0);
1028 if (Op->getType() == Z->getType())
1029 Z->replaceAllUsesWith(Op);
1030 Z->eraseFromParent();
1031 return;
1032 }
1037 T->replaceAllUsesWith(And);
1038 T->eraseFromParent();
1039 return;
1040 }
1041
1042
1043 for (unsigned i = 0, n = In->getNumOperands(); i != n; ++i) {
1045 if (CI->getBitWidth() < DestBW)
1046 In->setOperand(i, ConstantInt::get(DestTy, CI->getZExtValue()));
1047 }
1048}
1049
1050bool PolynomialMultiplyRecognize::promoteTypes(BasicBlock *LoopB,
1051 BasicBlock *ExitB) {
1053
1054
1055
1056
1058 return false;
1059 IntegerType *DestTy = getPmpyType();
1060
1061
1062 unsigned DestBW = DestTy->getBitWidth();
1063 for (PHINode &P : ExitB->phis()) {
1064 if (P.getNumIncomingValues() != 1)
1065 return false;
1066 assert(P.getIncomingBlock(0) == LoopB);
1068 if ( || T->getBitWidth() > DestBW)
1069 return false;
1070 }
1071
1072
1073 for (Instruction &In : *LoopB)
1074 if (.isTerminator() && !isPromotableTo(&In, DestTy))
1075 return false;
1076
1077
1079 for (Instruction *In : LoopIns)
1080 if (->isTerminator())
1081 promoteTo(In, DestTy, LoopB);
1082
1083
1085 for (auto I = ExitB->begin(); I != End; ++I) {
1087 if ()
1088 break;
1089 Type *Ty0 = P->getIncomingValue(0)->getType();
1090 Type *PTy = P->getType();
1091 if (PTy != Ty0) {
1092 assert(Ty0 == DestTy);
1093
1094 P->mutateType(Ty0);
1096
1097 P->mutateType(PTy);
1098 P->replaceAllUsesWith(T);
1099
1100 P->mutateType(Ty0);
1102 }
1103 }
1104
1105 return true;
1106}
1107
1108bool PolynomialMultiplyRecognize::findCycle(Value *Out, Value *In,
1109 ValueSeq &Cycle) {
1110
1111 if (Out == In)
1112 return true;
1113
1115 bool HadPhi = false;
1116
1117 for (auto *U : Out->users()) {
1119 if (I == nullptr || I->getParent() != BB)
1120 continue;
1121
1122
1123
1124
1125
1127 if (IsPhi && HadPhi)
1128 return false;
1129 HadPhi |= IsPhi;
1130 if (.insert(I))
1131 return false;
1132 if (findCycle(I, In, Cycle))
1133 break;
1135 }
1136 return .empty();
1137}
1138
1139void PolynomialMultiplyRecognize::classifyCycle(Instruction *DivI,
1140 ValueSeq &Cycle, ValueSeq &Early, ValueSeq &Late) {
1141
1142
1143
1144
1145 bool IsE = true;
1146 unsigned I, N = Cycle.size();
1147 for (I = 0; I < N; ++I) {
1149 if (DivI == V)
1150 IsE = false;
1152 continue;
1153
1154 break;
1155 }
1156
1157
1158 ValueSeq &First = !IsE ? Early : Late;
1159 for (unsigned J = 0; J < I; ++J)
1161
1162 ValueSeq &Second = IsE ? Early : Late;
1167 break;
1168 Second.insert(V);
1169 }
1170
1173}
1174
1175bool PolynomialMultiplyRecognize::classifyInst(Instruction *UseI,
1176 ValueSeq &Early, ValueSeq &Late) {
1177
1178
1179
1180 if (UseI->getOpcode() == Instruction::Select) {
1182 if (Early.count(TV) || Early.count(FV)) {
1183 if (Late.count(TV) || Late.count(FV))
1184 return false;
1185 Early.insert(UseI);
1186 } else if (Late.count(TV) || Late.count(FV)) {
1187 if (Early.count(TV) || Early.count(FV))
1188 return false;
1189 Late.insert(UseI);
1190 }
1191 return true;
1192 }
1193
1194
1195
1197 return true;
1198
1199 bool AE = true, AL = true;
1200 for (auto &I : UseI->operands()) {
1201 if (Early.count(&*I))
1202 AL = false;
1203 else if (Late.count(&*I))
1204 AE = false;
1205 }
1206
1207
1208
1209 if (AE && AL)
1210 return true;
1211
1212
1213
1214 if (!AE && !AL)
1215 return false;
1216
1217
1219
1220 if (AE)
1221 Early.insert(UseI);
1222 else
1223 Late.insert(UseI);
1224 return true;
1225}
1226
1227bool PolynomialMultiplyRecognize::commutesWithShift(Instruction *I) {
1228 switch (I->getOpcode()) {
1229 case Instruction::And:
1230 case Instruction::Or:
1231 case Instruction::Xor:
1232 case Instruction::LShr:
1233 case Instruction::Shl:
1234 case Instruction::Select:
1235 case Instruction::ICmp:
1236 case Instruction::PHI:
1237 break;
1238 default:
1239 return false;
1240 }
1241 return true;
1242}
1243
1244bool PolynomialMultiplyRecognize::highBitsAreZero(Value *V,
1245 unsigned IterCount) {
1247 if ()
1248 return false;
1249
1250 KnownBits Known(T->getBitWidth());
1252 return Known.countMinLeadingZeros() >= IterCount;
1253}
1254
1255bool PolynomialMultiplyRecognize::keepsHighBitsZero(Value *V,
1256 unsigned IterCount) {
1257
1258
1260 return C->getValue().countl_zero() >= IterCount;
1261
1263 switch (I->getOpcode()) {
1264 case Instruction::And:
1265 case Instruction::Or:
1266 case Instruction::Xor:
1267 case Instruction::LShr:
1268 case Instruction::Select:
1269 case Instruction::ICmp:
1270 case Instruction::PHI:
1271 case Instruction::ZExt:
1272 return true;
1273 }
1274 }
1275
1276 return false;
1277}
1278
1279bool PolynomialMultiplyRecognize::isOperandShifted(Instruction *I, Value *Op) {
1280 unsigned Opc = I->getOpcode();
1281 if (Opc == Instruction::Shl || Opc == Instruction::LShr)
1282 return Op != I->getOperand(1);
1283 return true;
1284}
1285
1286bool PolynomialMultiplyRecognize::convertShiftsToLeft(BasicBlock *LoopB,
1287 BasicBlock *ExitB, unsigned IterCount) {
1288 Value *CIV = getCountIV(LoopB);
1289 if (CIV == nullptr)
1290 return false;
1292 if (CIVTy == nullptr)
1293 return false;
1294
1295 ValueSeq RShifts;
1296 ValueSeq Early, Late, Cycled;
1297
1298
1299 for (Instruction &I : *LoopB) {
1300 using namespace PatternMatch;
1301
1304 continue;
1305 ValueSeq C;
1306 if (!findCycle(&I, V, C))
1307 continue;
1308
1309
1311 classifyCycle(&I, C, Early, Late);
1312 Cycled.insert_range(C);
1313 RShifts.insert(&I);
1314 }
1315
1316
1317
1319 for (unsigned i = 0; i < Users.size(); ++i) {
1322 return false;
1324
1325
1326 if (!commutesWithShift(R))
1327 return false;
1328 for (User *U : R->users()) {
1330
1331
1332
1333 if (T->getParent() != LoopB || RShifts.count(T) || isa(T))
1334 continue;
1335
1337 if (!classifyInst(T, Early, Late))
1338 return false;
1339 }
1340 }
1341
1342 if (Users.empty())
1343 return false;
1344
1345
1347 ValueSeq Inputs;
1348 for (unsigned i = 0; i < Internal.size(); ++i) {
1350 if (!R)
1351 continue;
1352 for (Value *Op : R->operands()) {
1354 if (T && T->getParent() != LoopB)
1355 Inputs.insert(Op);
1356 else
1358 }
1359 }
1360 for (Value *V : Inputs)
1361 if (!highBitsAreZero(V, IterCount))
1362 return false;
1363 for (Value *V : Internal)
1364 if (!keepsHighBitsZero(V, IterCount))
1365 return false;
1366
1367
1369 std::map<Value*,Value*> ShiftMap;
1370
1371 using CastMapType = std::map<std::pair<Value *, Type *>, Value *>;
1372
1373 CastMapType CastMap;
1374
1376 IntegerType *Ty) -> Value * {
1377 auto [H, Inserted] = CM.try_emplace(std::make_pair(V, Ty));
1378 if (Inserted)
1379 H->second = IRB.CreateIntCast(V, Ty, false);
1380 return H->second;
1381 };
1382
1383 for (auto I = LoopB->begin(), E = LoopB->end(); I != E; ++I) {
1384 using namespace PatternMatch;
1385
1387 continue;
1388
1389
1393 continue;
1394 }
1395
1396
1397 for (auto &J : I->operands()) {
1399 if (!isOperandShifted(&*I, Op))
1400 continue;
1402 continue;
1403
1405 continue;
1406
1407 auto F = ShiftMap.find(Op);
1408 Value *W = (F != ShiftMap.end()) ? F->second : nullptr;
1409 if (W == nullptr) {
1410 IRB.SetInsertPoint(&*I);
1411
1412
1413
1414 Value *ShAmt = CIV, *ShVal = Op;
1417 if (Late.count(&*I))
1418 ShVal = IRB.CreateShl(Op, ConstantInt::get(VTy, 1));
1419
1420
1421 if (VTy != ATy) {
1422 if (VTy->getBitWidth() < ATy->getBitWidth())
1423 ShVal = upcast(CastMap, IRB, ShVal, ATy);
1424 else
1425 ShAmt = upcast(CastMap, IRB, ShAmt, VTy);
1426 }
1427
1428 W = IRB.CreateShl(ShVal, ShAmt);
1429 ShiftMap.insert(std::make_pair(Op, W));
1430 }
1431 I->replaceUsesOfWith(Op, W);
1432 }
1433 }
1434
1435
1436
1437
1438
1439
1441 for (auto P = ExitB->begin(), Q = ExitB->end(); P != Q; ++P) {
1443 break;
1445 Value *U = PN->getIncomingValueForBlock(LoopB);
1446 if (.count(U))
1447 continue;
1448 Value *S = IRB.CreateLShr(PN, ConstantInt::get(PN->getType(), IterCount));
1449 PN->replaceAllUsesWith(S);
1450
1451
1452
1453
1454 cast(S)->replaceUsesOfWith(S, PN);
1455 }
1456
1457 return true;
1458}
1459
1460void PolynomialMultiplyRecognize::cleanupLoopBody(BasicBlock *LoopB) {
1461 for (auto &I : *LoopB)
1463 I.replaceAllUsesWith(SV);
1464
1467}
1468
1469unsigned PolynomialMultiplyRecognize::getInverseMxN(unsigned QP) {
1470
1471
1472 std::array<char,32> Q, C;
1473
1474 for (unsigned i = 0; i < 32; ++i) {
1475 Q[i] = QP & 1;
1476 QP >>= 1;
1477 }
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490 C[0] = 1;
1491 for (unsigned i = 1; i < 32; ++i) {
1492
1493
1494
1495
1496
1497
1498 unsigned T = 0;
1499 for (unsigned j = 0; j < i; ++j)
1502 }
1503
1504 unsigned QV = 0;
1505 for (unsigned i = 0; i < 32; ++i)
1506 if (C[i])
1507 QV |= (1 << i);
1508
1509 return QV;
1510}
1511
1513 ParsedValues &PV) {
1515 Module *M = At->getParent()->getParent()->getParent();
1518
1519 Value *P = PV.P, *Q = PV.Q, *P0 = P;
1520 unsigned IC = PV.IterCount;
1521
1522 if (PV.M != nullptr)
1523 P0 = P = B.CreateXor(P, PV.M);
1524
1525
1527
1528 if (PV.IterCount != 32)
1530
1531 if (PV.Inv) {
1533 assert(QI && QI->getBitWidth() <= 32);
1534
1535
1536 unsigned M = (1 << PV.IterCount) - 1;
1537 unsigned Tmp = (QI->getZExtValue() | 1) & M;
1538 unsigned QV = getInverseMxN(Tmp) & M;
1539 auto *QVI = ConstantInt::get(QI->getType(), QV);
1540 P = B.CreateCall(PMF, {P, QVI});
1541 P = B.CreateTrunc(P, QI->getType());
1542 if (IC != 32)
1544 }
1545
1546 Value *R = B.CreateCall(PMF, {P, Q});
1547
1548 if (PV.M != nullptr)
1549 R = B.CreateXor(R, B.CreateIntCast(P0, R->getType(), false));
1550
1551 return R;
1552}
1553
1556 return CI->getValue().isNonNegative();
1558 if ()
1559 return false;
1560 switch (I->getOpcode()) {
1561 case Instruction::LShr:
1563 return SI->getZExtValue() > 0;
1564 return false;
1565 case Instruction::Or:
1566 case Instruction::Xor:
1569 case Instruction::And:
1572 }
1573 return false;
1574}
1575
1576void PolynomialMultiplyRecognize::setupPreSimplifier(Simplifier &S) {
1577 S.addRule("sink-zext",
1578
1579 [](Instruction *I, LLVMContext &Ctx) -> Value* {
1580 if (I->getOpcode() != Instruction::ZExt)
1581 return nullptr;
1583 if ()
1584 return nullptr;
1585 switch (T->getOpcode()) {
1586 case Instruction::And:
1587 case Instruction::Or:
1588 case Instruction::Xor:
1589 break;
1590 default:
1591 return nullptr;
1592 }
1595 B.CreateZExt(T->getOperand(0), I->getType()),
1596 B.CreateZExt(T->getOperand(1), I->getType()));
1597 });
1598 S.addRule("xor/and -> and/xor",
1599
1600 [](Instruction *I, LLVMContext &Ctx) -> Value* {
1601 if (I->getOpcode() != Instruction::Xor)
1602 return nullptr;
1605 if (!And0 || !And1)
1606 return nullptr;
1607 if (And0->getOpcode() != Instruction::And ||
1608 And1->getOpcode() != Instruction::And)
1609 return nullptr;
1611 return nullptr;
1615 });
1616 S.addRule("sink binop into select",
1617
1618
1619 [](Instruction *I, LLVMContext &Ctx) -> Value* {
1621 if (!BO)
1622 return nullptr;
1626 Value *X = Sel->getTrueValue(), *Y = Sel->getFalseValue();
1628 return B.CreateSelect(Sel->getCondition(),
1630 B.CreateBinOp(Op, Y, Z));
1631 }
1635 Value *Y = Sel->getTrueValue(), *Z = Sel->getFalseValue();
1636 return B.CreateSelect(Sel->getCondition(),
1638 B.CreateBinOp(Op, X, Z));
1639 }
1640 return nullptr;
1641 });
1642 S.addRule("fold select-select",
1643
1644
1645 [](Instruction *I, LLVMContext &Ctx) -> Value* {
1647 if (!Sel)
1648 return nullptr;
1652 if (Sel0->getCondition() == C)
1653 return B.CreateSelect(C, Sel0->getTrueValue(), Sel->getFalseValue());
1654 }
1656 if (Sel1->getCondition() == C)
1657 return B.CreateSelect(C, Sel->getTrueValue(), Sel1->getFalseValue());
1658 }
1659 return nullptr;
1660 });
1661 S.addRule("or-signbit -> xor-signbit",
1662
1663 [](Instruction *I, LLVMContext &Ctx) -> Value* {
1664 if (I->getOpcode() != Instruction::Or)
1665 return nullptr;
1668 return nullptr;
1670 return nullptr;
1671 return IRBuilder<>(Ctx).CreateXor(I->getOperand(0), Msb);
1672 });
1673 S.addRule("sink lshr into binop",
1674
1675 [](Instruction *I, LLVMContext &Ctx) -> Value* {
1676 if (I->getOpcode() != Instruction::LShr)
1677 return nullptr;
1679 if (!BitOp)
1680 return nullptr;
1682 case Instruction::And:
1683 case Instruction::Or:
1684 case Instruction::Xor:
1685 break;
1686 default:
1687 return nullptr;
1688 }
1690 Value *S = I->getOperand(1);
1691 return B.CreateBinOp(BitOp->getOpcode(),
1694 });
1695 S.addRule("expose bitop-const",
1696
1697 [](Instruction *I, LLVMContext &Ctx) -> Value* {
1698 auto IsBitOp = [](unsigned Op) -> bool {
1699 switch (Op) {
1700 case Instruction::And:
1701 case Instruction::Or:
1702 case Instruction::Xor:
1703 return true;
1704 }
1705 return false;
1706 };
1708 if (!BitOp1 || !IsBitOp(BitOp1->getOpcode()))
1709 return nullptr;
1711 if (!BitOp2 || !IsBitOp(BitOp2->getOpcode()))
1712 return nullptr;
1715 if (!CA || !CB)
1716 return nullptr;
1719 return B.CreateBinOp(BitOp2->getOpcode(), X,
1720 B.CreateBinOp(BitOp1->getOpcode(), CA, CB));
1721 });
1722}
1723
1724void PolynomialMultiplyRecognize::setupPostSimplifier(Simplifier &S) {
1725 S.addRule("(and (xor (and x a) y) b) -> (and (xor x y) b), if b == b&a",
1726 [](Instruction *I, LLVMContext &Ctx) -> Value* {
1727 if (I->getOpcode() != Instruction::And)
1728 return nullptr;
1731 if ( || !C0)
1732 return nullptr;
1733 if (Xor->getOpcode() != Instruction::Xor)
1734 return nullptr;
1737
1738 if (!And0 || And0->getOpcode() != Instruction::And)
1741 if (!C1)
1742 return nullptr;
1745 if (V0 != (V0 & V1))
1746 return nullptr;
1748 return B.CreateAnd(B.CreateXor(And0->getOperand(0), And1), C0);
1749 });
1750}
1751
1752bool PolynomialMultiplyRecognize::recognize() {
1753 LLVM_DEBUG(dbgs() << "Starting PolynomialMultiplyRecognize on loop\n"
1754 << *CurLoop << '\n');
1755
1756
1757
1758
1759
1760 BasicBlock *LoopB = CurLoop->getHeader();
1762
1763 if (LoopB != CurLoop->getLoopLatch())
1764 return false;
1765 BasicBlock *ExitB = CurLoop->getExitBlock();
1766 if (ExitB == nullptr)
1767 return false;
1768 BasicBlock *EntryB = CurLoop->getLoopPreheader();
1769 if (EntryB == nullptr)
1770 return false;
1771
1772 unsigned IterCount = 0;
1773 const SCEV *CT = SE.getBackedgeTakenCount(CurLoop);
1775 return false;
1777 IterCount = CV->getValue()->getZExtValue() + 1;
1778
1779 Value *CIV = getCountIV(LoopB);
1780 if (CIV == nullptr)
1781 return false;
1782 ParsedValues PV;
1783 Simplifier PreSimp;
1784 PV.IterCount = IterCount;
1785 LLVM_DEBUG(dbgs() << "Loop IV: " << *CIV << "\nIterCount: " << IterCount
1786 << '\n');
1787
1788 setupPreSimplifier(PreSimp);
1789
1790
1791
1792
1793
1794
1795
1796 bool FoundPreScan = false;
1797 auto FeedsPHI = [LoopB](const Value *V) -> bool {
1798 for (const Value *U : V->users()) {
1800 if (P->getParent() == LoopB)
1801 return true;
1802 }
1803 return false;
1804 };
1805 for (Instruction &In : *LoopB) {
1807 if (!SI || !FeedsPHI(SI))
1808 continue;
1809
1810 Simplifier::Context C(SI);
1811 Value *T = PreSimp.simplify(C);
1813 LLVM_DEBUG(dbgs() << "scanSelect(pre-scan): " << PE(C, SelI) << '\n');
1814 if (scanSelect(SelI, LoopB, EntryB, CIV, PV, true)) {
1815 FoundPreScan = true;
1816 if (SelI != SI) {
1817 Value *NewSel = C.materialize(LoopB, SI->getIterator());
1818 SI->replaceAllUsesWith(NewSel);
1820 }
1821 break;
1822 }
1823 }
1824
1825 if (!FoundPreScan) {
1826 LLVM_DEBUG(dbgs() << "Have not found candidates for pmpy\n");
1827 return false;
1828 }
1829
1830 if (!PV.Left) {
1831
1832
1833
1834
1835 if (!promoteTypes(LoopB, ExitB))
1836 return false;
1837
1838 Simplifier PostSimp;
1839 setupPostSimplifier(PostSimp);
1840 for (Instruction &In : *LoopB) {
1842 if (!SI || !FeedsPHI(SI))
1843 continue;
1844 Simplifier::Context C(SI);
1845 Value *T = PostSimp.simplify(C);
1847 if (SelI != SI) {
1848 Value *NewSel = C.materialize(LoopB, SI->getIterator());
1849 SI->replaceAllUsesWith(NewSel);
1851 }
1852 break;
1853 }
1854
1855 if (!convertShiftsToLeft(LoopB, ExitB, IterCount))
1856 return false;
1857 cleanupLoopBody(LoopB);
1858 }
1859
1860
1861 bool FoundScan = false;
1862 for (Instruction &In : *LoopB) {
1864 if (!SelI)
1865 continue;
1866 LLVM_DEBUG(dbgs() << "scanSelect: " << *SelI << '\n');
1867 FoundScan = scanSelect(SelI, LoopB, EntryB, CIV, PV, false);
1868 if (FoundScan)
1869 break;
1870 }
1872
1874 StringRef PP = (PV.M ? "(P+M)" : "P");
1875 if (!PV.Inv)
1876 dbgs() << "Found pmpy idiom: R = " << PP << ".Q\n";
1877 else
1878 dbgs() << "Found inverse pmpy idiom: R = (" << PP << "/Q).Q) + "
1879 << PP << "\n";
1880 dbgs() << " Res:" << *PV.Res << "\n P:" << *PV.P << "\n";
1881 if (PV.M)
1882 dbgs() << " M:" << *PV.M << "\n";
1883 dbgs() << " Q:" << *PV.Q << "\n";
1884 dbgs() << " Iteration count:" << PV.IterCount << "\n";
1885 });
1886
1888 Value *PM = generate(At, PV);
1889 if (PM == nullptr)
1890 return false;
1891
1892 if (PM->getType() != PV.Res->getType())
1893 PM = IRBuilder<>(&*At).CreateIntCast(PM, PV.Res->getType(), false);
1894
1895 PV.Res->replaceAllUsesWith(PM);
1896 PV.Res->eraseFromParent();
1897 return true;
1898}
1899
1900int HexagonLoopIdiomRecognize::getSCEVStride(const SCEVAddRecExpr *S) {
1902 return SC->getAPInt().getSExtValue();
1903 return 0;
1904}
1905
1906bool HexagonLoopIdiomRecognize::isLegalStore(Loop *CurLoop, StoreInst *SI) {
1907
1909 return false;
1910
1911 Value *StoredVal = SI->getValueOperand();
1912 Value *StorePtr = SI->getPointerOperand();
1913
1914
1915 uint64_t SizeInBits = DL->getTypeSizeInBits(StoredVal->getType());
1916 if ((SizeInBits & 7) || (SizeInBits >> 32) != 0)
1917 return false;
1918
1919
1920
1921
1923 if (!StoreEv || StoreEv->getLoop() != CurLoop || !StoreEv->isAffine())
1924 return false;
1925
1926
1927
1928 int Stride = getSCEVStride(StoreEv);
1929 if (Stride == 0)
1930 return false;
1931 unsigned StoreSize = DL->getTypeStoreSize(SI->getValueOperand()->getType());
1932 if (StoreSize != unsigned(std::abs(Stride)))
1933 return false;
1934
1935
1938 return false;
1939
1940
1941
1942
1945 if (!LoadEv || LoadEv->getLoop() != CurLoop || !LoadEv->isAffine())
1946 return false;
1947
1948
1949 if (StoreEv->getOperand(1) != LoadEv->getOperand(1))
1950 return false;
1951
1952
1953 return true;
1954}
1955
1956
1957
1958
1959static bool
1961 const SCEV *BECount, unsigned StoreSize,
1964
1965
1966
1968
1969
1970
1973 StoreSize);
1974
1975
1976
1977
1978
1980
1981 for (auto *B : L->blocks())
1983 if (Ignored.count(&I) == 0 &&
1985 return true;
1986
1987 return false;
1988}
1989
1990void HexagonLoopIdiomRecognize::collectStores(Loop *CurLoop, BasicBlock *BB,
1991 SmallVectorImpl<StoreInst*> &Stores) {
1993 for (Instruction &I : *BB)
1995 if (isLegalStore(CurLoop, SI))
1997}
1998
1999bool HexagonLoopIdiomRecognize::processCopyingStore(Loop *CurLoop,
2000 StoreInst *SI, const SCEV *BECount) {
2002 "Expected only non-volatile stores, or Hexagon-specific memcpy"
2003 "to volatile destination.");
2004
2005 Value *StorePtr = SI->getPointerOperand();
2007 unsigned Stride = getSCEVStride(StoreEv);
2008 unsigned StoreSize = DL->getTypeStoreSize(SI->getValueOperand()->getType());
2009 if (Stride != StoreSize)
2010 return false;
2011
2012
2013
2014
2017
2018
2019
2020
2024 SCEVExpander Expander(*SE, *DL, "hexagon-loop-idiom");
2025
2026 Type *IntPtrTy = Builder.getIntPtrTy(*DL, SI->getPointerAddressSpace());
2027
2028
2029
2030
2031
2032
2033
2034 Value *StoreBasePtr = Expander.expandCodeFor(StoreEv->getStart(),
2035 Builder.getPtrTy(SI->getPointerAddressSpace()), ExpPt);
2036 Value *LoadBasePtr = nullptr;
2037
2038 bool Overlap = false;
2039 bool DestVolatile = SI->isVolatile();
2041
2042 if (DestVolatile) {
2043
2044
2045 if (StoreSize != 4 || DL->getTypeSizeInBits(BECountTy) > 32) {
2046CleanupAndExit:
2047
2048 Expander.clear();
2049 if (StoreBasePtr && (LoadBasePtr != StoreBasePtr)) {
2051 StoreBasePtr = nullptr;
2052 }
2053 if (LoadBasePtr) {
2055 LoadBasePtr = nullptr;
2056 }
2057 return false;
2058 }
2059 }
2060
2061 SmallPtrSet<Instruction*, 2> Ignore1;
2064 StoreSize, *AA, Ignore1)) {
2065
2068 BECount, StoreSize, *AA, Ignore1)) {
2069
2070 goto CleanupAndExit;
2071 }
2072
2073 Overlap = true;
2074 }
2075
2076 if (!Overlap) {
2078 goto CleanupAndExit;
2079 } else {
2080
2081
2083 if (Func->hasFnAttribute(Attribute::AlwaysInline))
2084 goto CleanupAndExit;
2085
2086
2087
2088
2089
2090 SmallVector<Instruction*,2> Insts;
2093 if (!coverLoop(CurLoop, Insts))
2094 goto CleanupAndExit;
2095
2097 goto CleanupAndExit;
2098 bool IsNested = CurLoop->getParentLoop() != nullptr;
2100 goto CleanupAndExit;
2101 }
2102
2103
2104
2105 LoadBasePtr = Expander.expandCodeFor(LoadEv->getStart(),
2107
2108 SmallPtrSet<Instruction*, 2> Ignore2;
2111 StoreSize, *AA, Ignore2))
2112 goto CleanupAndExit;
2113
2114
2115 bool StridePos = getSCEVStride(LoadEv) >= 0;
2116
2117
2118 if (!StridePos && DestVolatile)
2119 goto CleanupAndExit;
2120
2121 bool RuntimeCheck = (Overlap || DestVolatile);
2122
2124 if (RuntimeCheck) {
2125
2126 SmallVector<BasicBlock*, 8> ExitBlocks;
2128 if (ExitBlocks.size() != 1)
2129 goto CleanupAndExit;
2130 ExitB = ExitBlocks[0];
2131 }
2132
2133
2134
2135 LLVMContext &Ctx = SI->getContext();
2136 BECount = SE->getTruncateOrZeroExtend(BECount, IntPtrTy);
2138
2139 const SCEV *NumBytesS =
2140 SE->getAddExpr(BECount, SE->getOne(IntPtrTy), SCEV::FlagNUW);
2141 if (StoreSize != 1)
2142 NumBytesS = SE->getMulExpr(NumBytesS, SE->getConstant(IntPtrTy, StoreSize),
2144 Value *NumBytes = Expander.expandCodeFor(NumBytesS, IntPtrTy, ExpPt);
2147 NumBytes = Simp;
2148
2149 CallInst *NewCall;
2150
2151 if (RuntimeCheck) {
2154 uint64_t C = CI->getZExtValue();
2155 if (Threshold != 0 && C < Threshold)
2156 goto CleanupAndExit;
2158 goto CleanupAndExit;
2159 }
2160
2163 Loop *ParentL = LF->getLoopFor(Preheader);
2164 StringRef HeaderName = Header->getName();
2165
2166
2167
2169 Func, Header);
2170 if (ParentL)
2172 IRBuilder<>(NewPreheader).CreateBr(Header);
2173 for (auto &In : *Header) {
2175 if (!PN)
2176 break;
2178 if (bx >= 0)
2180 }
2181 DT->addNewBlock(NewPreheader, Preheader);
2182 DT->changeImmediateDominator(Header, NewPreheader);
2183
2184
2185
2186
2187
2188
2189
2190 Value *LA = Builder.CreatePtrToInt(LoadBasePtr, IntPtrTy);
2191 Value *SA = Builder.CreatePtrToInt(StoreBasePtr, IntPtrTy);
2192 Value *LowA = StridePos ? SA : LA;
2193 Value *HighA = StridePos ? LA : SA;
2194 Value *CmpA = Builder.CreateICmpULT(LowA, HighA);
2196
2197
2198
2199 Value *Dist = Builder.CreateSub(LowA, HighA);
2200 Value *CmpD = Builder.CreateICmpSLE(NumBytes, Dist);
2201 Value *CmpEither = Builder.CreateOr(Cond, CmpD);
2202 Cond = CmpEither;
2203
2204 if (Threshold != 0) {
2206 Value *Thr = ConstantInt::get(Ty, Threshold);
2207 Value *CmpB = Builder.CreateICmpULT(Thr, NumBytes);
2208 Value *CmpBoth = Builder.CreateAnd(Cond, CmpB);
2209 Cond = CmpBoth;
2210 }
2212 Func, NewPreheader);
2213 if (ParentL)
2216 Builder.CreateCondBr(Cond, MemmoveB, NewPreheader);
2219 DT->addNewBlock(MemmoveB, Preheader);
2220
2223 ExitD = DT->findNearestCommonDominator(ExitD, PB);
2224 if (!ExitD)
2225 break;
2226 }
2227
2228
2229
2230
2231 if (ExitD && DT->dominates(Preheader, ExitD)) {
2235 }
2236
2237
2239 CondBuilder.CreateBr(ExitB);
2240 CondBuilder.SetInsertPoint(MemmoveB->getTerminator());
2241
2242 if (DestVolatile) {
2244 Type *PtrTy = PointerType::get(Ctx, 0);
2245 Type *VoidTy = Type::getVoidTy(Ctx);
2247
2248
2249 StringRef HexagonVolatileMemcpyName =
2251 RTLIB::impl_hexagon_memcpy_forward_vp4cp4n2);
2252 FunctionCallee Fn = M->getOrInsertFunction(
2253 HexagonVolatileMemcpyName, VoidTy, PtrTy, PtrTy, Int32Ty);
2254
2255 const SCEV *OneS = SE->getConstant(Int32Ty, 1);
2256 const SCEV *BECount32 = SE->getTruncateOrZeroExtend(BECount, Int32Ty);
2257 const SCEV *NumWordsS = SE->getAddExpr(BECount32, OneS, SCEV::FlagNUW);
2258 Value *NumWords = Expander.expandCodeFor(NumWordsS, Int32Ty,
2262 NumWords = Simp;
2263
2264 NewCall = CondBuilder.CreateCall(Fn,
2265 {StoreBasePtr, LoadBasePtr, NumWords});
2266 } else {
2267 NewCall = CondBuilder.CreateMemMove(
2268 StoreBasePtr, SI->getAlign(), LoadBasePtr, LI->getAlign(), NumBytes);
2269 }
2270 } else {
2271 NewCall = Builder.CreateMemCpy(StoreBasePtr, SI->getAlign(), LoadBasePtr,
2273
2274
2276 }
2277
2279
2280 LLVM_DEBUG(dbgs() << " Formed " << (Overlap ? "memmove: " : "memcpy: ")
2281 << *NewCall << "\n"
2282 << " from load ptr=" << *LoadEv << " at: " << *LI << "\n"
2283 << " from store ptr=" << *StoreEv << " at: " << *SI
2284 << "\n");
2285
2286 return true;
2287}
2288
2289
2290
2291
2292bool HexagonLoopIdiomRecognize::coverLoop(Loop *L,
2293 SmallVectorImpl<Instruction*> &Insts) const {
2294 SmallPtrSet<BasicBlock *, 8> LoopBlocks;
2296
2298
2299
2300
2301
2302
2303 for (unsigned i = 0; i < Worklist.size(); ++i) {
2305 for (auto I = In->op_begin(), E = In->op_end(); I != E; ++I) {
2307 if (!OpI)
2308 continue;
2310 if (!LoopBlocks.count(PB))
2311 continue;
2312 Worklist.insert(OpI);
2313 }
2314 }
2315
2316
2317
2318
2319
2320 for (auto *B : L->blocks()) {
2321 for (auto &In : *B) {
2323 continue;
2324 if (!Worklist.count(&In) && In.mayHaveSideEffects())
2325 return false;
2326 for (auto *K : In.users()) {
2328 if (!UseI)
2329 continue;
2331 if (LF->getLoopFor(UseB) != L)
2332 return false;
2333 }
2334 }
2335 }
2336
2337 return true;
2338}
2339
2340
2341
2342
2343bool HexagonLoopIdiomRecognize::runOnLoopBlock(Loop *CurLoop, BasicBlock *BB,
2344 const SCEV *BECount, SmallVectorImpl<BasicBlock*> &ExitBlocks) {
2345
2346
2347
2348 auto DominatedByBB = [this,BB] (BasicBlock *EB) -> bool {
2349 return DT->dominates(BB, EB);
2350 };
2351 if ((ExitBlocks, DominatedByBB))
2352 return false;
2353
2354 bool MadeChange = false;
2355
2356 SmallVector<StoreInst*,8> Stores;
2357 collectStores(CurLoop, BB, Stores);
2358
2359
2360 for (auto &SI : Stores)
2361 MadeChange |= processCopyingStore(CurLoop, SI, BECount);
2362
2363 return MadeChange;
2364}
2365
2366bool HexagonLoopIdiomRecognize::runOnCountableLoop(Loop *L) {
2367 PolynomialMultiplyRecognize PMR(L, *DL, *DT, *TLI, *SE);
2368 if (PMR.recognize())
2369 return true;
2370
2371 if (!HasMemcpy && !HasMemmove)
2372 return false;
2373
2374 const SCEV *BECount = SE->getBackedgeTakenCount(L);
2376 "runOnCountableLoop() called on a loop without a predictable"
2377 "backedge-taken count");
2378
2379 SmallVector<BasicBlock *, 8> ExitBlocks;
2380 L->getUniqueExitBlocks(ExitBlocks);
2381
2383
2384
2385 for (auto *BB : L->getBlocks()) {
2386
2387 if (LF->getLoopFor(BB) != L)
2388 continue;
2389 Changed |= runOnLoopBlock(L, BB, BECount, ExitBlocks);
2390 }
2391
2393}
2394
2395bool HexagonLoopIdiomRecognize::run(Loop *L) {
2396 const Module &M = *L->getHeader()->getParent()->getParent();
2398 return false;
2399
2400
2401
2402 if (->getLoopPreheader())
2403 return false;
2404
2405
2406 StringRef Name = L->getHeader()->getParent()->getName();
2407 if (Name == "memset" || Name == "memcpy" || Name == "memmove")
2408 return false;
2409
2410 DL = &L->getHeader()->getDataLayout();
2411
2412 HasMemcpy = TLI->has(LibFunc_memcpy);
2413 HasMemmove = TLI->has(LibFunc_memmove);
2414
2415 if (SE->hasLoopInvariantBackedgeTakenCount(L))
2416 return runOnCountableLoop(L);
2417 return false;
2418}
2419
2420bool HexagonLoopIdiomRecognizeLegacyPass::runOnLoop(Loop *L,
2421 LPPassManager &LPM) {
2422 if (skipLoop(L))
2423 return false;
2424
2425 auto *AA = &getAnalysis().getAAResults();
2426 auto *DT = &getAnalysis().getDomTree();
2427 auto *LF = &getAnalysis().getLoopInfo();
2428 auto *TLI = &getAnalysis().getTLI(
2429 *L->getHeader()->getParent());
2430 auto *SE = &getAnalysis().getSE();
2431 return HexagonLoopIdiomRecognize(AA, DT, LF, TLI, SE).run(L);
2432}
2433
2435 return new HexagonLoopIdiomRecognizeLegacyPass();
2436}
2437
2442 return HexagonLoopIdiomRecognize(&AR.AA, &AR.DT, &AR.LI, &AR.TLI, &AR.SE)
2443 .run(&L)
2446}
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 void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
static void cleanup(BlockFrequencyInfoImplBase &BFI)
Clear all memory not needed downstream.
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_ATTRIBUTE_USED
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file defines the DenseMap class.
static cl::opt< unsigned > SimplifyLimit("hlir-simplify-limit", cl::init(10000), cl::Hidden, cl::desc("Maximum number of simplification steps in HLIR"))
static cl::opt< bool > DisableMemcpyIdiom("disable-memcpy-idiom", cl::Hidden, cl::init(false), cl::desc("Disable generation of memcpy in loop idiom recognition"))
static void replaceAllUsesOfWithIn(Value *I, Value *J, BasicBlock *BB)
Definition HexagonLoopIdiomRecognition.cpp:659
static cl::opt< unsigned > RuntimeMemSizeThreshold("runtime-mem-idiom-threshold", cl::Hidden, cl::init(0), cl::desc("Threshold (in bytes) for the runtime " "check guarding the memmove."))
static cl::opt< bool > HexagonVolatileMemcpy("disable-hexagon-volatile-memcpy", cl::Hidden, cl::init(false), cl::desc("Enable Hexagon-specific memcpy for volatile destination."))
static cl::opt< bool > DisableMemmoveIdiom("disable-memmove-idiom", cl::Hidden, cl::init(false), cl::desc("Disable generation of memmove in loop idiom recognition"))
static cl::opt< unsigned > CompileTimeMemSizeThreshold("compile-time-mem-idiom-threshold", cl::Hidden, cl::init(64), cl::desc("Threshold (in bytes) to perform the transformation, if the " "runtime loop count (mem transfer size) is known at compile-time."))
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...
Definition HexagonLoopIdiomRecognition.cpp:1960
static bool hasZeroSignBit(const Value *V)
Definition HexagonLoopIdiomRecognition.cpp:1554
static cl::opt< bool > OnlyNonNestedMemmove("only-nonnested-memmove-idiom", cl::Hidden, cl::init(true), cl::desc("Only enable generating memmove in non-nested loops"))
Module.h This file contains the declarations for the Module class.
This header defines various interfaces for pass management in LLVM.
iv Induction Variable Users
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Move duplicate certain instructions close to their use
This header provides classes for managing per-loop analyses.
Machine Check Debug Module
This file provides utility analysis objects describing memory locations.
uint64_t IntrinsicInst * II
PassBuilder PB(Machine, PassOpts->PTO, std::nullopt, &PIC)
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
const SmallVectorImpl< MachineOperand > & Cond
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, const llvm::StringTable &StandardNames, VectorLibrary VecLib)
Initialize the set of available library functions based on the specified target triple.
static std::optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
bool isSignMask() const
Check if the APInt's value is returned by getSignMask.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
LLVM_ABI AnalysisUsage & addRequiredID(const void *ID)
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
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.
LLVM_ABI const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
InstListType::iterator iterator
Instruction iterators...
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...
BinaryOps getOpcode() const
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.
void setIDom(DomTreeNodeBase *NewIDom)
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
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.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
unsigned getPointerAddressSpace() const
Returns the address space of the pointer operand.
Value * getPointerOperand()
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).
BlockT * getHeader() const
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
void getUniqueExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
The legacy pass manager's analysis pass to compute loop information.
Represents a single loop in the control flow graph.
Representation for a specific memory location.
void setIncomingBlock(unsigned i, BasicBlock *BB)
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
Pass interface - Implemented by all 'passes'.
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 class represents a constant integer value.
const SCEV * getOperand(unsigned i) const
This class represents an analyzed expression in the program.
LLVM_ABI Type * getType() const
Return the LLVM type of this SCEV expression.
The main scalar evolution driver.
const Value * getFalseValue() const
const Value * getCondition() const
const Value * getTrueValue() const
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
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.
void push_back(const T &Elt)
Provides information about what library functions are available for the current target.
bool isVoidTy() const
Return true if this is 'void'.
A Use represents the edge between a Value definition and its users.
User * getUser() const
Returns the User that contains this Use.
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
user_iterator user_begin()
LLVM_ABI void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
iterator_range< user_iterator > users()
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
const ParentTy * getParent() const
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Abstract Attribute helper functions.
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.
LLVM_ABI Function * getOrInsertDeclaration(Module *M, ID id, ArrayRef< Type * > Tys={})
Look up the Function declaration of the intrinsic id in the Module M.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Xor > m_Xor(const LHS &L, const RHS &R)
bool match(Val *V, const Pattern &P)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
CmpClass_match< LHS, RHS, ICmpInst, true > m_c_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
Matches an ICmp with a predicate over LHS and RHS in either order.
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
BinaryOp_match< LHS, RHS, Instruction::Xor, true > m_c_Xor(const LHS &L, const RHS &R)
Matches an Xor with LHS and RHS in either order.
CastInst_match< OpTy, ZExtInst > m_ZExt(const OpTy &Op)
Matches ZExt.
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)
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
LLVM_ABI void link(std::unique_ptr< LinkGraph > G, std::unique_ptr< JITLinkContext > Ctx)
Link the given graph.
NodeAddr< UseNode * > Use
NodeAddr< FuncNode * > Func
Context & getContext() const
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
FunctionAddr VTableAddr Value
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)
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.
auto pred_end(const MachineBasicBlock *BB)
decltype(auto) dyn_cast(const From &Val)
dyn_cast - Return the argument parameter cast to the specified type.
FunctionAddr VTableAddr uintptr_t uintptr_t Int32Ty
constexpr from_range_t from_range
Pass * createHexagonLoopIdiomPass()
Definition HexagonLoopIdiomRecognition.cpp:2434
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...
LLVM_ABI char & LoopSimplifyID
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
DomTreeNodeBase< BasicBlock > DomTreeNode
AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager
The loop analysis manager.
auto dyn_cast_or_null(const Y &Val)
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
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)
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
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.
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
IRBuilder(LLVMContext &, FolderTy, InserterTy, MDNode *, ArrayRef< OperandBundleDef >) -> IRBuilder< FolderTy, InserterTy >
void replace(R &&Range, const T &OldValue, const T &NewValue)
Provide wrappers to std::replace which take ranges instead of having to pass begin/end explicitly.
@ Xor
Bitwise or logical XOR of integers.
@ And
Bitwise or logical AND of integers.
@ Sub
Subtraction of integers.
DWARFExpression::Operation Op
PredIterator< BasicBlock, Value::user_iterator > pred_iterator
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
auto pred_begin(const MachineBasicBlock *BB)
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.
auto predecessors(const MachineBasicBlock *BB)
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
AAResults AliasAnalysis
Temporary typedef for legacy code that uses a generic AliasAnalysis pointer or reference.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition HexagonLoopIdiomRecognition.cpp:2439
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
static StringRef getLibcallImplName(RTLIB::LibcallImpl CallImpl)
Get the libcall routine name for the specified libcall implementation.