LLVM: lib/Target/Hexagon/HexagonConstExtenders.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
23#include
24#include
25#include
26#include
27
28#define DEBUG_TYPE "hexagon-cext-opt"
29
30using namespace llvm;
31
34 cl::desc("Minimum number of extenders to trigger replacement"));
35
38 cl::desc("Maximum number of replacements"));
39
42 int32_t U = (V & -A) + O;
43 return U >= V ? U : U+A;
44}
45
48 int32_t U = (V & -A) + O;
49 return U <= V ? U : U-A;
50}
51
52namespace {
53 struct OffsetRange {
54
55
56
57 int32_t Min = INT_MIN, Max = INT_MAX;
58 uint8_t Align = 1;
59 uint8_t Offset = 0;
60
61 OffsetRange() = default;
62 OffsetRange(int32_t L, int32_t H, uint8_t A, uint8_t O = 0)
63 : Min(L), Max(H), Align(A), Offset(O) {}
64 OffsetRange &intersect(OffsetRange A) {
65 if (Align < A.Align)
67
68
69 if (Offset >= A.Offset && (Offset - A.Offset) % A.Align == 0) {
70 Min = adjustUp(std::max(Min, A.Min), Align, Offset);
71 Max = adjustDown(std::min(Max, A.Max), Align, Offset);
72 } else {
73
74 Min = 0;
75 Max = -1;
76 }
77
78 if (Min > Max)
79 std::tie(Min, Max, Align) = std::make_tuple(0, -1, 1);
80 return *this;
81 }
82 OffsetRange &shift(int32_t S) {
83 Min += S;
84 Max += S;
85 Offset = (Offset+S) % Align;
86 return *this;
87 }
88 OffsetRange &extendBy(int32_t D) {
89
91 if (D < 0)
92 Min = (INT_MIN-D < Min) ? Min+D : INT_MIN;
93 else
94 Max = (INT_MAX-D > Max) ? Max+D : INT_MAX;
95 return *this;
96 }
97 bool empty() const {
98 return Min > Max;
99 }
100 bool contains(int32_t V) const {
101 return Min <= V && V <= Max && (V-Offset) % Align == 0;
102 }
103 bool operator==(const OffsetRange &R) const {
104 return Min == R.Min && Max == R.Max && Align == R.Align;
105 }
106 bool operator!=(const OffsetRange &R) const {
108 }
109 bool operator<(const OffsetRange &R) const {
110 return std::tie(Min, Max, Align) < std::tie(R.Min, R.Max, R.Align);
111 }
112 static OffsetRange zero() { return {0, 0, 1}; }
113 };
114
115 struct RangeTree {
116 struct Node {
117 Node(const OffsetRange &R) : MaxEnd(R.Max), Range(R) {}
118 unsigned Height = 1;
119 unsigned Count = 1;
120 int32_t MaxEnd;
121 const OffsetRange &Range;
122 Node *Left = nullptr, *Right = nullptr;
123 };
124
125 Node *Root = nullptr;
126
127 void add(const OffsetRange &R) {
128 Root = add(Root, R);
129 }
130 void erase(const Node *N) {
132 delete N;
133 }
134 void order(SmallVectorImpl<Node*> &Seq) const {
135 order(Root, Seq);
136 }
139 nodesWith(Root, P, CheckAlign, Nodes);
140 return Nodes;
141 }
142 void dump() const;
143 ~RangeTree() {
145 order(Nodes);
146 for (Node *N : Nodes)
147 delete N;
148 }
149
150 private:
151 void dump(const Node *N) const;
152 void order(Node *N, SmallVectorImpl<Node*> &Seq) const;
153 void nodesWith(Node *N, int32_t P, bool CheckA,
154 SmallVectorImpl<Node*> &Seq) const;
155
156 Node *add(Node *N, const OffsetRange &R);
157 Node *remove(Node *N, const Node *D);
158 Node *rotateLeft(Node *Lower, Node *Higher);
159 Node *rotateRight(Node *Lower, Node *Higher);
160 unsigned height(Node *N) {
161 return N != nullptr ? N->Height : 0;
162 }
163 Node *update(Node *N) {
165 N->Height = 1 + std::max(height(N->Left), height(N->Right));
166 if (N->Left)
167 N->MaxEnd = std::max(N->MaxEnd, N->Left->MaxEnd);
168 if (N->Right)
169 N->MaxEnd = std::max(N->MaxEnd, N->Right->MaxEnd);
170 return N;
171 }
172 Node *rebalance(Node *N) {
174 int32_t Balance = height(N->Right) - height(N->Left);
175 if (Balance < -1)
176 return rotateRight(N->Left, N);
177 if (Balance > 1)
178 return rotateLeft(N->Right, N);
179 return N;
180 }
181 };
182
183 struct Loc {
184 MachineBasicBlock *Block = nullptr;
186
188 : Block(B), At(It) {
189 if (B->end() == It) {
190 Pos = -1;
191 } else {
192 assert(It->getParent() == B);
193 Pos = std::distance(B->begin(), It);
194 }
195 }
197 if (Block != A.Block)
198 return Block->getNumber() < A.Block->getNumber();
199 if (A.Pos == -1)
200 return Pos != A.Pos;
201 return Pos != -1 && Pos < A.Pos;
202 }
203 private:
204 int Pos = 0;
205 };
206
208 static char ID;
209 HexagonConstExtenders() : MachineFunctionPass(ID) {}
210
211 void getAnalysisUsage(AnalysisUsage &AU) const override {
212 AU.addRequired();
213 AU.addPreserved();
215 }
216
217 StringRef getPassName() const override {
218 return "Hexagon constant-extender optimization";
219 }
220 bool runOnMachineFunction(MachineFunction &MF) override;
221
222 private:
223 struct Register {
225 Register(llvm::Register R, unsigned S) : Reg(R), Sub(S) {}
227 : Reg(Op.getReg()), Sub(Op.getSubReg()) {}
228 Register &operator=(const MachineOperand &Op) {
229 if (Op.isReg()) {
230 Reg = Op.getReg();
231 Sub = Op.getSubReg();
232 } else if (Op.isFI()) {
234 }
235 return *this;
236 }
237 bool isVReg() const {
238 return Reg != 0 && !Reg.isStack() && Reg.isVirtual();
239 }
240 bool isSlot() const { return Reg != 0 && Reg.isStack(); }
241 operator MachineOperand() const {
242 if (isVReg())
244 false, false, false,
245 false, Sub);
246 if (Reg.isStack()) {
247 int FI = Reg.stackSlotIndex();
249 }
251 }
255
256 return std::tie(Reg, Sub) < std::tie(R.Reg, R.Sub);
257 }
258 llvm::Register Reg;
259 unsigned Sub = 0;
260 };
261
262 struct ExtExpr {
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
285 unsigned S = 0;
286 bool Neg = false;
287
288 ExtExpr() = default;
289 ExtExpr(Register RS, bool NG, unsigned SH) : Rs(RS), S(SH), Neg(NG) {}
290
291 bool trivial() const {
292 return Rs.Reg == 0;
293 }
294 bool operator==(const ExtExpr &Ex) const {
295 return Rs == Ex.Rs && S == Ex.S && Neg == Ex.Neg;
296 }
297 bool operator!=(const ExtExpr &Ex) const {
299 }
300 bool operator<(const ExtExpr &Ex) const {
301 return std::tie(Rs, S, Neg) < std::tie(Ex.Rs, Ex.S, Ex.Neg);
302 }
303 };
304
305 struct ExtDesc {
306 MachineInstr *UseMI = nullptr;
307 unsigned OpNum = -1u;
308
309
310 ExtExpr Expr;
311
313
314
315
316 bool IsDef = false;
317
318 MachineOperand &getOp() {
319 return UseMI->getOperand(OpNum);
320 }
321 const MachineOperand &getOp() const {
322 return UseMI->getOperand(OpNum);
323 }
324 };
325
326 struct ExtRoot {
327 union {
328 const ConstantFP *CFP;
329 const char *SymbolName;
330 const GlobalValue *GV;
332 int64_t ImmVal;
333
334 } V;
335 unsigned Kind;
336 unsigned char TF;
337
338 ExtRoot(const MachineOperand &Op);
339 bool operator==(const ExtRoot &ER) const {
340 return Kind == ER.Kind && V.ImmVal == ER.V.ImmVal;
341 }
342 bool operator!=(const ExtRoot &ER) const {
344 }
345 bool operator<(const ExtRoot &ER) const;
346 };
347
348 struct ExtValue : public ExtRoot {
349 int32_t Offset;
350
351 ExtValue(const MachineOperand &Op);
352 ExtValue(const ExtDesc &ED) : ExtValue(ED.getOp()) {}
353 ExtValue(const ExtRoot &ER, int32_t Off) : ExtRoot(ER), Offset(Off) {}
354 bool operator<(const ExtValue &EV) const;
355 bool operator==(const ExtValue &EV) const {
356 return ExtRoot(*this) == ExtRoot(EV) && Offset == EV.Offset;
357 }
358 bool operator!=(const ExtValue &EV) const {
360 }
361 explicit operator MachineOperand() const;
362 };
363
364 using IndexList = SetVector;
365 using ExtenderInit = std::pair<ExtValue, ExtExpr>;
366 using AssignmentMap = std::map<ExtenderInit, IndexList>;
367 using LocDefList = std::vector<std::pair<Loc, IndexList>>;
368
369 const HexagonSubtarget *HST = nullptr;
370 const HexagonInstrInfo *HII = nullptr;
371 const HexagonRegisterInfo *HRI = nullptr;
372 MachineDominatorTree *MDT = nullptr;
373 MachineRegisterInfo *MRI = nullptr;
374 std::vector Extenders;
375 std::vector NewRegs;
376
377 bool isStoreImmediate(unsigned Opc) const;
378 bool isRegOffOpcode(unsigned ExtOpc) const ;
379 unsigned getRegOffOpcode(unsigned ExtOpc) const;
380 unsigned getDirectRegReplacement(unsigned ExtOpc) const;
381 OffsetRange getOffsetRange(Register R, const MachineInstr &MI) const;
382 OffsetRange getOffsetRange(const ExtDesc &ED) const;
383 OffsetRange getOffsetRange(Register Rd) const;
384
385 void recordExtender(MachineInstr &MI, unsigned OpNum);
386 void collectInstr(MachineInstr &MI);
387 void collect(MachineFunction &MF);
388 void assignInits(const ExtRoot &ER, unsigned Begin, unsigned End,
389 AssignmentMap &IMap);
390 void calculatePlacement(const ExtenderInit &ExtI, const IndexList &Refs,
391 LocDefList &Defs);
392 Register insertInitializer(Loc DefL, const ExtenderInit &ExtI);
393 bool replaceInstrExact(const ExtDesc &ED, Register ExtR);
394 bool replaceInstrExpr(const ExtDesc &ED, const ExtenderInit &ExtI,
395 Register ExtR, int32_t &Diff);
396 bool replaceInstr(unsigned Idx, Register ExtR, const ExtenderInit &ExtI);
397 bool replaceExtenders(const AssignmentMap &IMap);
398
399 unsigned getOperandIndex(const MachineInstr &MI,
400 const MachineOperand &Op) const;
401 const MachineOperand &getPredicateOp(const MachineInstr &MI) const;
402 const MachineOperand &getLoadResultOp(const MachineInstr &MI) const;
403 const MachineOperand &getStoredValueOp(const MachineInstr &MI) const;
404
405 friend struct PrintRegister;
406 friend struct PrintExpr;
407 friend struct PrintInit;
408 friend struct PrintIMap;
409 friend raw_ostream &operator<< (raw_ostream &OS,
410 const struct PrintRegister &P);
411 friend raw_ostream &operator<< (raw_ostream &OS, const struct PrintExpr &P);
412 friend raw_ostream &operator<< (raw_ostream &OS, const struct PrintInit &P);
413 friend raw_ostream &operator<< (raw_ostream &OS, const ExtDesc &ED);
414 friend raw_ostream &operator<< (raw_ostream &OS, const ExtRoot &ER);
415 friend raw_ostream &operator<< (raw_ostream &OS, const ExtValue &EV);
416 friend raw_ostream &operator<< (raw_ostream &OS, const OffsetRange &OR);
417 friend raw_ostream &operator<< (raw_ostream &OS, const struct PrintIMap &P);
418 };
419
420 using HCE = HexagonConstExtenders;
421
422 [[maybe_unused]]
425 OS << '!';
426 OS << '[' << OR.Min << ',' << OR.Max << "]a" << unsigned(OR.Align)
428 return OS;
429 }
430
431 struct PrintRegister {
432 PrintRegister(HCE::Register R, const HexagonRegisterInfo &I)
434 HCE::Register Rs;
435 const HexagonRegisterInfo &HRI;
436 };
437
438 [[maybe_unused]]
440 if (P.Rs.Reg != 0)
441 OS << printReg(P.Rs.Reg, &P.HRI, P.Rs.Sub);
442 else
443 OS << "noreg";
444 return OS;
445 }
446
447 struct PrintExpr {
448 PrintExpr(const HCE::ExtExpr &E, const HexagonRegisterInfo &I)
450 const HCE::ExtExpr &Ex;
451 const HexagonRegisterInfo &HRI;
452 };
453
454 [[maybe_unused]]
456 OS << "## " << (P.Ex.Neg ? "- " : "+ ");
457 if (P.Ex.Rs.Reg != 0)
458 OS << printReg(P.Ex.Rs.Reg, &P.HRI, P.Ex.Rs.Sub);
459 else
460 OS << "__";
461 OS << " << " << P.Ex.S;
462 return OS;
463 }
464
465 struct PrintInit {
466 PrintInit(const HCE::ExtenderInit &EI, const HexagonRegisterInfo &I)
467 : ExtI(EI), HRI(I) {}
468 const HCE::ExtenderInit &ExtI;
469 const HexagonRegisterInfo &HRI;
470 };
471
472 [[maybe_unused]]
474 OS << '[' << P.ExtI.first << ", "
475 << PrintExpr(P.ExtI.second, P.HRI) << ']';
476 return OS;
477 }
478
479 [[maybe_unused]]
481 assert(ED.OpNum != -1u);
485 OS << "bb#" << MBB.getNumber() << ": ";
486 if (ED.Rd.Reg != 0)
487 OS << printReg(ED.Rd.Reg, &HRI, ED.Rd.Sub);
488 else
489 OS << "__";
490 OS << " = " << PrintExpr(ED.Expr, HRI);
491 if (ED.IsDef)
492 OS << ", def";
493 return OS;
494 }
495
496 [[maybe_unused]]
498 switch (ER.Kind) {
500 OS << "imm:" << ER.V.ImmVal;
501 break;
503 OS << "fpi:" << *ER.V.CFP;
504 break;
506 OS << "sym:" << *ER.V.SymbolName;
507 break;
509 OS << "gad:" << ER.V.GV->getName();
510 break;
512 OS << "blk:" << *ER.V.BA;
513 break;
515 OS << "tgi:" << ER.V.ImmVal;
516 break;
518 OS << "cpi:" << ER.V.ImmVal;
519 break;
521 OS << "jti:" << ER.V.ImmVal;
522 break;
523 default:
524 OS << "???:" << ER.V.ImmVal;
525 break;
526 }
527 return OS;
528 }
529
530 [[maybe_unused]]
532 OS << HCE::ExtRoot(EV) << " off:" << EV.Offset;
533 return OS;
534 }
535
536 struct PrintIMap {
537 PrintIMap(const HCE::AssignmentMap &M, const HexagonRegisterInfo &I)
539 const HCE::AssignmentMap &IMap;
540 const HexagonRegisterInfo &HRI;
541 };
542
543 [[maybe_unused]]
545 OS << "{\n";
546 for (const std::pair<const HCE::ExtenderInit, HCE::IndexList> &Q : P.IMap) {
547 OS << " " << PrintInit(Q.first, P.HRI) << " -> {";
548 for (unsigned I : Q.second)
549 OS << ' ' << I;
550 OS << " }\n";
551 }
552 OS << "}\n";
553 return OS;
554 }
555}
556
558 "Hexagon constant-extender optimization", false, false)
561 "Hexagon constant-extender optimization", false, false)
562
564
565char HCE::ID = 0;
566
567#ifndef NDEBUG
569 dbgs() << "Root: " << Root << '\n';
570 if (Root)
572}
573
575 dbgs() << "Node: " << N << '\n';
576 dbgs() << " Height: " << N->Height << '\n';
577 dbgs() << " Count: " << N->Count << '\n';
578 dbgs() << " MaxEnd: " << N->MaxEnd << '\n';
579 dbgs() << " Range: " << N->Range << '\n';
580 dbgs() << " Left: " << N->Left << '\n';
581 dbgs() << " Right: " << N->Right << "\n\n";
582
583 if (N->Left)
585 if (N->Right)
587}
588#endif
589
590void RangeTree::order(Node *N, SmallVectorImpl<Node*> &Seq) const {
591 if (N == nullptr)
592 return;
593 order(N->Left, Seq);
595 order(N->Right, Seq);
596}
597
598void RangeTree::nodesWith(Node *N, int32_t P, bool CheckA,
599 SmallVectorImpl<Node*> &Seq) const {
600 if (N == nullptr || N->MaxEnd < P)
601 return;
602 nodesWith(N->Left, P, CheckA, Seq);
604 if ((CheckA && N->Range.contains(P)) || (!CheckA && P <= N->Range.Max))
606 nodesWith(N->Right, P, CheckA, Seq);
607 }
608}
609
610RangeTree::Node *RangeTree::add(Node *N, const OffsetRange &R) {
611 if (N == nullptr)
612 return new Node(R);
613
614 if (N->Range == R) {
615 N->Count++;
616 return N;
617 }
618
619 if (R < N->Range)
620 N->Left = add(N->Left, R);
621 else
622 N->Right = add(N->Right, R);
623 return rebalance(update(N));
624}
625
626RangeTree::Node *RangeTree::remove(Node *N, const Node *D) {
628
630 assert(N->Range != D->Range && "N and D should not be equal");
633 else
635 return rebalance(update(N));
636 }
637
638
639
640 if (N->Left == nullptr || N->Right == nullptr)
641 return (N->Left == nullptr) ? N->Right : N->Left;
642
643
644
646 while (M->Right)
648 M->Left = remove(N->Left, M);
650 return rebalance(update(M));
651}
652
653RangeTree::Node *RangeTree::rotateLeft(Node *Lower, Node *Higher) {
655
656
657
658 if (height(Lower->Left) > height(Lower->Right))
661 Higher->Right = Lower->Left;
662 update(Higher);
663 Lower->Left = Higher;
666}
667
668RangeTree::Node *RangeTree::rotateRight(Node *Lower, Node *Higher) {
670
671
672
673 if (height(Lower->Left) < height(Lower->Right))
676 Higher->Left = Lower->Right;
677 update(Higher);
678 Lower->Right = Higher;
681}
682
683
684HCE::ExtRoot::ExtRoot(const MachineOperand &Op) {
685
686 V.ImmVal = 0;
687 if (Op.isImm())
688 ;
689 else if (Op.isFPImm())
691 else if (Op.isSymbol())
692 V.SymbolName = Op.getSymbolName();
693 else if (Op.isGlobal())
695 else if (Op.isBlockAddress())
696 V.BA = Op.getBlockAddress();
697 else if (Op.isCPI() || Op.isTargetIndex() || Op.isJTI())
699 else
701
703 TF = Op.getTargetFlags();
704}
705
706bool HCE::ExtRoot::operator< (const HCE::ExtRoot &ER) const {
707 if (Kind != ER.Kind)
708 return Kind < ER.Kind;
709 switch (Kind) {
714 return V.ImmVal < ER.V.ImmVal;
716 const APFloat &ThisF = V.CFP->getValueAPF();
717 const APFloat &OtherF = ER.V.CFP->getValueAPF();
719 }
721 return StringRef(V.SymbolName) < StringRef(ER.V.SymbolName);
723
724
725
726
727 assert(.GV->getName().empty() && !ER.V.GV->getName().empty());
728 return V.GV->getName() < ER.V.GV->getName();
730 const BasicBlock *ThisB = V.BA->getBasicBlock();
731 const BasicBlock *OtherB = ER.V.BA->getBasicBlock();
734 return std::distance(F.begin(), ThisB->getIterator()) <
735 std::distance(F.begin(), OtherB->getIterator());
736 }
737 }
738 return V.ImmVal < ER.V.ImmVal;
739}
740
741HCE::ExtValue::ExtValue(const MachineOperand &Op) : ExtRoot(Op) {
742 if (Op.isImm())
744 else if (Op.isFPImm() || Op.isJTI())
746 else if (Op.isSymbol() || Op.isGlobal() || Op.isBlockAddress() ||
747 Op.isCPI() || Op.isTargetIndex())
749 else
751}
752
753bool HCE::ExtValue::operator< (const HCE::ExtValue &EV) const {
754 const ExtRoot &ER = *this;
755 if (!(ER == ExtRoot(EV)))
756 return ER < EV;
757 return Offset < EV.Offset;
758}
759
761 switch (Kind) {
781 default:
783 }
784}
785
786bool HCE::isStoreImmediate(unsigned Opc) const {
787 switch (Opc) {
788 case Hexagon::S4_storeirbt_io:
789 case Hexagon::S4_storeirbf_io:
790 case Hexagon::S4_storeirht_io:
791 case Hexagon::S4_storeirhf_io:
792 case Hexagon::S4_storeirit_io:
793 case Hexagon::S4_storeirif_io:
794 case Hexagon::S4_storeirb_io:
795 case Hexagon::S4_storeirh_io:
796 case Hexagon::S4_storeiri_io:
797 return true;
798 default:
799 break;
800 }
801 return false;
802}
803
804bool HCE::isRegOffOpcode(unsigned Opc) const {
805 switch (Opc) {
806 case Hexagon::L2_loadrub_io:
807 case Hexagon::L2_loadrb_io:
808 case Hexagon::L2_loadruh_io:
809 case Hexagon::L2_loadrh_io:
810 case Hexagon::L2_loadri_io:
811 case Hexagon::L2_loadrd_io:
812 case Hexagon::L2_loadbzw2_io:
813 case Hexagon::L2_loadbzw4_io:
814 case Hexagon::L2_loadbsw2_io:
815 case Hexagon::L2_loadbsw4_io:
816 case Hexagon::L2_loadalignh_io:
817 case Hexagon::L2_loadalignb_io:
818 case Hexagon::L2_ploadrubt_io:
819 case Hexagon::L2_ploadrubf_io:
820 case Hexagon::L2_ploadrbt_io:
821 case Hexagon::L2_ploadrbf_io:
822 case Hexagon::L2_ploadruht_io:
823 case Hexagon::L2_ploadruhf_io:
824 case Hexagon::L2_ploadrht_io:
825 case Hexagon::L2_ploadrhf_io:
826 case Hexagon::L2_ploadrit_io:
827 case Hexagon::L2_ploadrif_io:
828 case Hexagon::L2_ploadrdt_io:
829 case Hexagon::L2_ploadrdf_io:
830 case Hexagon::S2_storerb_io:
831 case Hexagon::S2_storerh_io:
832 case Hexagon::S2_storerf_io:
833 case Hexagon::S2_storeri_io:
834 case Hexagon::S2_storerd_io:
835 case Hexagon::S2_pstorerbt_io:
836 case Hexagon::S2_pstorerbf_io:
837 case Hexagon::S2_pstorerht_io:
838 case Hexagon::S2_pstorerhf_io:
839 case Hexagon::S2_pstorerft_io:
840 case Hexagon::S2_pstorerff_io:
841 case Hexagon::S2_pstorerit_io:
842 case Hexagon::S2_pstorerif_io:
843 case Hexagon::S2_pstorerdt_io:
844 case Hexagon::S2_pstorerdf_io:
845 case Hexagon::A2_addi:
846 return true;
847 default:
848 break;
849 }
850 return false;
851}
852
853unsigned HCE::getRegOffOpcode(unsigned ExtOpc) const {
854
855
857 switch (ExtOpc) {
858 case A2_tfrsi: return A2_addi;
859 default:
860 break;
861 }
863 if (D.mayLoad() || D.mayStore()) {
866 switch (AM) {
870 switch (ExtOpc) {
871 case PS_loadrubabs:
872 case L4_loadrub_ap:
873 case L4_loadrub_ur: return L2_loadrub_io;
874 case PS_loadrbabs:
875 case L4_loadrb_ap:
876 case L4_loadrb_ur: return L2_loadrb_io;
877 case PS_loadruhabs:
878 case L4_loadruh_ap:
879 case L4_loadruh_ur: return L2_loadruh_io;
880 case PS_loadrhabs:
881 case L4_loadrh_ap:
882 case L4_loadrh_ur: return L2_loadrh_io;
883 case PS_loadriabs:
884 case L4_loadri_ap:
885 case L4_loadri_ur: return L2_loadri_io;
886 case PS_loadrdabs:
887 case L4_loadrd_ap:
888 case L4_loadrd_ur: return L2_loadrd_io;
889 case L4_loadbzw2_ap:
890 case L4_loadbzw2_ur: return L2_loadbzw2_io;
891 case L4_loadbzw4_ap:
892 case L4_loadbzw4_ur: return L2_loadbzw4_io;
893 case L4_loadbsw2_ap:
894 case L4_loadbsw2_ur: return L2_loadbsw2_io;
895 case L4_loadbsw4_ap:
896 case L4_loadbsw4_ur: return L2_loadbsw4_io;
897 case L4_loadalignh_ap:
898 case L4_loadalignh_ur: return L2_loadalignh_io;
899 case L4_loadalignb_ap:
900 case L4_loadalignb_ur: return L2_loadalignb_io;
901 case L4_ploadrubt_abs: return L2_ploadrubt_io;
902 case L4_ploadrubf_abs: return L2_ploadrubf_io;
903 case L4_ploadrbt_abs: return L2_ploadrbt_io;
904 case L4_ploadrbf_abs: return L2_ploadrbf_io;
905 case L4_ploadruht_abs: return L2_ploadruht_io;
906 case L4_ploadruhf_abs: return L2_ploadruhf_io;
907 case L4_ploadrht_abs: return L2_ploadrht_io;
908 case L4_ploadrhf_abs: return L2_ploadrhf_io;
909 case L4_ploadrit_abs: return L2_ploadrit_io;
910 case L4_ploadrif_abs: return L2_ploadrif_io;
911 case L4_ploadrdt_abs: return L2_ploadrdt_io;
912 case L4_ploadrdf_abs: return L2_ploadrdf_io;
913 case PS_storerbabs:
914 case S4_storerb_ap:
915 case S4_storerb_ur: return S2_storerb_io;
916 case PS_storerhabs:
917 case S4_storerh_ap:
918 case S4_storerh_ur: return S2_storerh_io;
919 case PS_storerfabs:
920 case S4_storerf_ap:
921 case S4_storerf_ur: return S2_storerf_io;
922 case PS_storeriabs:
923 case S4_storeri_ap:
924 case S4_storeri_ur: return S2_storeri_io;
925 case PS_storerdabs:
926 case S4_storerd_ap:
927 case S4_storerd_ur: return S2_storerd_io;
928 case S4_pstorerbt_abs: return S2_pstorerbt_io;
929 case S4_pstorerbf_abs: return S2_pstorerbf_io;
930 case S4_pstorerht_abs: return S2_pstorerht_io;
931 case S4_pstorerhf_abs: return S2_pstorerhf_io;
932 case S4_pstorerft_abs: return S2_pstorerft_io;
933 case S4_pstorerff_abs: return S2_pstorerff_io;
934 case S4_pstorerit_abs: return S2_pstorerit_io;
935 case S4_pstorerif_abs: return S2_pstorerif_io;
936 case S4_pstorerdt_abs: return S2_pstorerdt_io;
937 case S4_pstorerdf_abs: return S2_pstorerdf_io;
938 default:
939 break;
940 }
941 break;
943 if (!isStoreImmediate(ExtOpc))
944 return ExtOpc;
945 break;
946 default:
947 break;
948 }
949 }
950 return 0;
951}
952
953unsigned HCE::getDirectRegReplacement(unsigned ExtOpc) const {
954 switch (ExtOpc) {
955 case Hexagon::A2_addi: return Hexagon::A2_add;
956 case Hexagon::A2_andir: return Hexagon::A2_and;
957 case Hexagon::A2_combineii: return Hexagon::A4_combineri;
958 case Hexagon::A2_orir: return Hexagon::A2_or;
959 case Hexagon::A2_paddif: return Hexagon::A2_paddf;
960 case Hexagon::A2_paddit: return Hexagon::A2_paddt;
961 case Hexagon::A2_subri: return Hexagon::A2_sub;
962 case Hexagon::A2_tfrsi: return TargetOpcode::COPY;
963 case Hexagon::A4_cmpbeqi: return Hexagon::A4_cmpbeq;
964 case Hexagon::A4_cmpbgti: return Hexagon::A4_cmpbgt;
965 case Hexagon::A4_cmpbgtui: return Hexagon::A4_cmpbgtu;
966 case Hexagon::A4_cmpheqi: return Hexagon::A4_cmpheq;
967 case Hexagon::A4_cmphgti: return Hexagon::A4_cmphgt;
968 case Hexagon::A4_cmphgtui: return Hexagon::A4_cmphgtu;
969 case Hexagon::A4_combineii: return Hexagon::A4_combineir;
970 case Hexagon::A4_combineir: return TargetOpcode::REG_SEQUENCE;
971 case Hexagon::A4_combineri: return TargetOpcode::REG_SEQUENCE;
972 case Hexagon::A4_rcmpeqi: return Hexagon::A4_rcmpeq;
973 case Hexagon::A4_rcmpneqi: return Hexagon::A4_rcmpneq;
974 case Hexagon::C2_cmoveif: return Hexagon::A2_tfrpf;
975 case Hexagon::C2_cmoveit: return Hexagon::A2_tfrpt;
976 case Hexagon::C2_cmpeqi: return Hexagon::C2_cmpeq;
977 case Hexagon::C2_cmpgti: return Hexagon::C2_cmpgt;
978 case Hexagon::C2_cmpgtui: return Hexagon::C2_cmpgtu;
979 case Hexagon::C2_muxii: return Hexagon::C2_muxir;
980 case Hexagon::C2_muxir: return Hexagon::C2_mux;
981 case Hexagon::C2_muxri: return Hexagon::C2_mux;
982 case Hexagon::C4_cmpltei: return Hexagon::C4_cmplte;
983 case Hexagon::C4_cmplteui: return Hexagon::C4_cmplteu;
984 case Hexagon::C4_cmpneqi: return Hexagon::C4_cmpneq;
985 case Hexagon::M2_accii: return Hexagon::M2_acci;
986
987 case Hexagon::M2_macsip: return Hexagon::M2_maci;
988 case Hexagon::M2_mpysin: return Hexagon::M2_mpyi;
989 case Hexagon::M2_mpysip: return Hexagon::M2_mpyi;
990 case Hexagon::M2_mpysmi: return Hexagon::M2_mpyi;
991 case Hexagon::M2_naccii: return Hexagon::M2_nacci;
992 case Hexagon::M4_mpyri_addi: return Hexagon::M4_mpyri_addr;
993 case Hexagon::M4_mpyri_addr: return Hexagon::M4_mpyrr_addr;
994 case Hexagon::M4_mpyrr_addi: return Hexagon::M4_mpyrr_addr;
995 case Hexagon::S4_addaddi: return Hexagon::M2_acci;
996 case Hexagon::S4_addi_asl_ri: return Hexagon::S2_asl_i_r_acc;
997 case Hexagon::S4_addi_lsr_ri: return Hexagon::S2_lsr_i_r_acc;
998 case Hexagon::S4_andi_asl_ri: return Hexagon::S2_asl_i_r_and;
999 case Hexagon::S4_andi_lsr_ri: return Hexagon::S2_lsr_i_r_and;
1000 case Hexagon::S4_ori_asl_ri: return Hexagon::S2_asl_i_r_or;
1001 case Hexagon::S4_ori_lsr_ri: return Hexagon::S2_lsr_i_r_or;
1002 case Hexagon::S4_subaddi: return Hexagon::M2_subacc;
1003 case Hexagon::S4_subi_asl_ri: return Hexagon::S2_asl_i_r_nac;
1004 case Hexagon::S4_subi_lsr_ri: return Hexagon::S2_lsr_i_r_nac;
1005
1006
1007 case Hexagon::S4_storeirbf_io: return Hexagon::S2_pstorerbf_io;
1008 case Hexagon::S4_storeirb_io: return Hexagon::S2_storerb_io;
1009 case Hexagon::S4_storeirbt_io: return Hexagon::S2_pstorerbt_io;
1010 case Hexagon::S4_storeirhf_io: return Hexagon::S2_pstorerhf_io;
1011 case Hexagon::S4_storeirh_io: return Hexagon::S2_storerh_io;
1012 case Hexagon::S4_storeirht_io: return Hexagon::S2_pstorerht_io;
1013 case Hexagon::S4_storeirif_io: return Hexagon::S2_pstorerif_io;
1014 case Hexagon::S4_storeiri_io: return Hexagon::S2_storeri_io;
1015 case Hexagon::S4_storeirit_io: return Hexagon::S2_pstorerit_io;
1016
1017 default:
1018 break;
1019 }
1020 return 0;
1021}
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1037 unsigned Opc = MI.getOpcode();
1038
1039
1040 if (!isRegOffOpcode(Opc) || HII->isConstExtended(MI))
1041 return OffsetRange::zero();
1042
1043 if (Opc == Hexagon::A2_addi) {
1044 const MachineOperand &Op1 = MI.getOperand(1), &Op2 = MI.getOperand(2);
1045 if (Rb != Register(Op1) || !Op2.isImm())
1046 return OffsetRange::zero();
1047 OffsetRange R = { -(1<<15)+1, (1<<15)-1, 1 };
1048 return R.shift(Op2.getImm());
1049 }
1050
1051
1052 if (HII->isPostIncrement(MI))
1053 return OffsetRange::zero();
1054
1056 assert(D.mayLoad() || D.mayStore());
1057
1058 unsigned BaseP, OffP;
1059 if (!HII->getBaseAndOffsetPosition(MI, BaseP, OffP) ||
1060 Rb != Register(MI.getOperand(BaseP)) ||
1061 .getOperand(OffP).isImm())
1062 return OffsetRange::zero();
1063
1068 unsigned S = 10+L;
1069 int32_t Min = -alignDown((1<<S)-1, A);
1070
1071
1072
1073 int32_t Off = MI.getOperand(OffP).getImm();
1074 int32_t Max = Off >= 0 ? 0 : -Off;
1075
1076 OffsetRange R = { Min, Max, A };
1077 return R.shift(Off);
1078}
1079
1080
1081
1082
1083
1084
1085
1086
1087OffsetRange HCE::getOffsetRange(const ExtDesc &ED) const {
1088
1089
1090
1091 unsigned IdxOpc = getRegOffOpcode(ED.UseMI->getOpcode());
1092 switch (IdxOpc) {
1093 case 0:
1094 return OffsetRange::zero();
1095 case Hexagon::A2_addi:
1096 return { -32767, 32767, 1 };
1097 case Hexagon::A2_subri:
1098 return { -511, 511, 1 };
1099 }
1100
1101 if (!ED.UseMI->mayLoad() && !ED.UseMI->mayStore())
1102 return OffsetRange::zero();
1108 unsigned S = 10+L;
1109 int32_t Min = -alignDown((1<<S)-1, A);
1110 int32_t Max = 0;
1112}
1113
1114
1115
1116OffsetRange HCE::getOffsetRange(Register Rd) const {
1117 OffsetRange Range;
1119
1120
1121
1123 return OffsetRange::zero();
1124 Range.intersect(getOffsetRange(Rd, *Op.getParent()));
1125 }
1127}
1128
1129void HCE::recordExtender(MachineInstr &MI, unsigned OpNum) {
1130 unsigned Opc = MI.getOpcode();
1131 ExtDesc ED;
1132 ED.OpNum = OpNum;
1133
1134 bool IsLoad = MI.mayLoad();
1135 bool IsStore = MI.mayStore();
1136
1137
1138
1139
1141 if (Op.isFI() && Op.getIndex() < 0)
1142 return;
1143
1144 if (IsLoad || IsStore) {
1145 unsigned AM = HII->getAddrMode(MI);
1146 switch (AM) {
1147
1149 break;
1151 ED.Rd = MI.getOperand(OpNum-1);
1152 ED.IsDef = true;
1153 break;
1155
1156
1157
1158 if (!isStoreImmediate(Opc))
1159 ED.Expr.Rs = MI.getOperand(OpNum-1);
1160 break;
1162 ED.Expr.Rs = MI.getOperand(OpNum-2);
1163 ED.Expr.S = MI.getOperand(OpNum-1).getImm();
1164 break;
1165 default:
1167 }
1168 } else {
1169 switch (Opc) {
1170 case Hexagon::A2_tfrsi:
1171 ED.Rd = MI.getOperand(0);
1172 ED.IsDef = true;
1173 break;
1174 case Hexagon::A2_combineii:
1175 case Hexagon::A4_combineir:
1176 ED.Rd = { MI.getOperand(0).getReg(), Hexagon::isub_hi };
1177 ED.IsDef = true;
1178 break;
1179 case Hexagon::A4_combineri:
1180 ED.Rd = { MI.getOperand(0).getReg(), Hexagon::isub_lo };
1181 ED.IsDef = true;
1182 break;
1183 case Hexagon::A2_addi:
1184 ED.Rd = MI.getOperand(0);
1185 ED.Expr.Rs = MI.getOperand(OpNum-1);
1186 break;
1187 case Hexagon::M2_accii:
1188 case Hexagon::M2_naccii:
1189 case Hexagon::S4_addaddi:
1190 ED.Expr.Rs = MI.getOperand(OpNum-1);
1191 break;
1192 case Hexagon::A2_subri:
1193 ED.Rd = MI.getOperand(0);
1194 ED.Expr.Rs = MI.getOperand(OpNum+1);
1195 ED.Expr.Neg = true;
1196 break;
1197 case Hexagon::S4_subaddi:
1198 ED.Expr.Rs = MI.getOperand(OpNum+1);
1199 ED.Expr.Neg = true;
1200 break;
1201 default:
1202 break;
1203 }
1204 }
1205
1206 ED.UseMI = &MI;
1207
1208
1209 ExtRoot ER(ED.getOp());
1211 if (ER.V.GV->getName().empty())
1212 return;
1213
1215 if (ER.V.BA->getFunction() != &(MI.getMF()->getFunction()))
1216 return;
1217 Extenders.push_back(ED);
1218}
1219
1221 if (!HII->isConstExtended(MI))
1222 return;
1223
1224
1225 unsigned Opc = MI.getOpcode();
1226 switch (Opc) {
1227 case Hexagon::M2_macsin:
1228 case Hexagon::C4_addipc:
1229 case Hexagon::S4_or_andi:
1230 case Hexagon::S4_or_andix:
1231 case Hexagon::S4_or_ori:
1232 return;
1233 }
1234 recordExtender(MI, HII->getCExtOpNum(MI));
1235}
1236
1238 Extenders.clear();
1240
1241 if (MBB.getNumber() == -1)
1242 continue;
1244 collectInstr(MI);
1245 }
1246}
1247
1248void HCE::assignInits(const ExtRoot &ER, unsigned Begin, unsigned End,
1249 AssignmentMap &IMap) {
1250
1251
1252 for (unsigned I = Begin; I != End; ++I)
1253 assert(ER == ExtRoot(Extenders[I].getOp()));
1254
1255
1256
1257
1258
1259 std::vector Ranges(End-Begin);
1260
1261
1262
1263
1264
1265 for (unsigned I = Begin; I != End; ++I) {
1266 const ExtDesc &ED = Extenders[I];
1267 if (!ED.IsDef)
1268 continue;
1269 ExtValue EV(ED);
1270 LLVM_DEBUG(dbgs() << " =" << I << ". " << EV << " " << ED << '\n');
1271 assert(ED.Rd.Reg != 0);
1272 Ranges[I-Begin] = getOffsetRange(ED.Rd).shift(EV.Offset);
1273
1274
1275
1276
1277 if (ED.UseMI->getOpcode() == Hexagon::A2_tfrsi) {
1278 int32_t D = alignDown(32767, Ranges[I-Begin].Align);
1279 Ranges[I-Begin].extendBy(-D).extendBy(D);
1280 }
1281 }
1282
1283
1284
1285 for (unsigned I = Begin; I != End; ++I) {
1286 const ExtDesc &ED = Extenders[I];
1287 if (ED.IsDef)
1288 continue;
1289 ExtValue EV(ED);
1290 LLVM_DEBUG(dbgs() << " " << I << ". " << EV << " " << ED << '\n');
1291 OffsetRange Dev = getOffsetRange(ED);
1292 Ranges[I-Begin].intersect(Dev.shift(EV.Offset));
1293 }
1294
1295
1296
1297
1298 std::map<OffsetRange, IndexList> RangeMap;
1299 for (unsigned I = Begin; I != End; ++I)
1300 RangeMap[Ranges[I-Begin]].insert(I);
1301
1303 dbgs() << "Ranges\n";
1304 for (unsigned I = Begin; I != End; ++I)
1305 dbgs() << " " << I << ". " << Ranges[I-Begin] << '\n';
1306 dbgs() << "RangeMap\n";
1307 for (auto &P : RangeMap) {
1308 dbgs() << " " << P.first << " ->";
1309 for (unsigned I : P.second)
1311 dbgs() << '\n';
1312 }
1313 });
1314
1315
1316
1317
1318 RangeTree Tree;
1319 for (const OffsetRange &R : Ranges)
1320 Tree.add(R);
1322 Tree.order(Nodes);
1323
1326 for (RangeTree::Node *N : Nodes) {
1327 if (N->Range.Align <= Align || N->Range.Offset < Offset)
1328 continue;
1329 if ((N->Range.Offset - Offset) % Align != 0)
1330 continue;
1332 Offset = N->Range.Offset;
1333 }
1335 };
1336
1337
1338
1339
1340
1341 std::set<int32_t> CandSet;
1342 for (RangeTree::Node *N : Nodes) {
1343 const OffsetRange &R = N->Range;
1344 auto P0 = MaxAlign(Tree.nodesWith(R.Min, false), R.Align, R.Offset);
1345 CandSet.insert(R.Min);
1347 CandSet.insert(adjustUp(R.Min, P0.first, P0.second));
1348 auto P1 = MaxAlign(Tree.nodesWith(R.Max, false), R.Align, R.Offset);
1349 CandSet.insert(R.Max);
1352 }
1353
1354
1355
1356
1357
1358
1359 while (true) {
1360 using CMap = std::map<int32_t,unsigned>;
1361 CMap Counts;
1362 for (auto It = CandSet.begin(), Et = CandSet.end(); It != Et; ) {
1363 auto &&V = Tree.nodesWith(*It);
1364 unsigned N = std::accumulate(V.begin(), V.end(), 0u,
1365 [](unsigned Acc, const RangeTree::Node *N) {
1366 return Acc + N->Count;
1367 });
1368 if (N != 0)
1369 Counts.insert({*It, N});
1370 It = (N != 0) ? std::next(It) : CandSet.erase(It);
1371 }
1372 if (Counts.empty())
1373 break;
1374
1375
1377 Counts, [](const CMap::value_type &A, const CMap::value_type &B) {
1378 return A.second < B.second || (A.second == B.second && A < B);
1379 });
1380 int32_t Best = BestIt->first;
1381 ExtValue BestV(ER, Best);
1382 for (RangeTree::Node *N : Tree.nodesWith(Best)) {
1383 for (unsigned I : RangeMap[N->Range])
1384 IMap[{BestV,Extenders[I].Expr}].insert(I);
1385 Tree.erase(N);
1386 }
1387 }
1388
1389 LLVM_DEBUG(dbgs() << "IMap (before fixup) = " << PrintIMap(IMap, *HRI));
1390
1391
1392
1393
1394
1395
1396
1397
1398 for (std::pair<const ExtenderInit,IndexList> &P : IMap) {
1399
1400 if (P.first.second.trivial())
1401 continue;
1402
1403
1404 const ExtValue &EV = P.first.first;
1405 AssignmentMap::iterator F = IMap.find({EV, ExtExpr()});
1406 if (F == IMap.end())
1407 continue;
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445 bool IsStack = any_of(F->second, [this](unsigned I) {
1446 return Extenders[I].Expr.Rs.isSlot();
1447 });
1448 auto SameValue = [&EV,this,IsStack](unsigned I) {
1449 const ExtDesc &ED = Extenders[I];
1450 return ED.Expr.Rs.isSlot() == IsStack &&
1451 ExtValue(ED).Offset == EV.Offset;
1452 };
1453 if (all_of(P.second, SameValue)) {
1454 F->second.insert_range(P.second);
1455 P.second.clear();
1456 }
1457 }
1458
1459 LLVM_DEBUG(dbgs() << "IMap (after fixup) = " << PrintIMap(IMap, *HRI));
1460}
1461
1462void HCE::calculatePlacement(const ExtenderInit &ExtI, const IndexList &Refs,
1463 LocDefList &Defs) {
1464 if (Refs.empty())
1465 return;
1466
1467
1468
1469
1470
1471
1474 const ExtDesc &ED0 = Extenders[Refs[0]];
1476 RefMIs.insert(ED0.UseMI);
1477 Blocks.insert(DomB);
1478 for (unsigned i = 1, e = Refs.size(); i != e; ++i) {
1479 const ExtDesc &ED = Extenders[Refs[i]];
1481 RefMIs.insert(ED.UseMI);
1482 DomB = MDT->findNearestCommonDominator(DomB, MBB);
1484 }
1485
1486#ifndef NDEBUG
1487
1488
1489 Register Rs = ExtI.second.Rs;
1490 const MachineInstr *DefI = Rs.isVReg() ? MRI->getVRegDef(Rs.Reg) : nullptr;
1491
1492
1493
1494 assert(!DefI || MDT->dominates(DefI->getParent(), DomB));
1495#endif
1496
1498 if (Blocks.count(DomB)) {
1499
1501 for (It = DomB->begin(); It != End; ++It)
1502 if (RefMIs.count(&*It))
1503 break;
1504 assert(It != End && "Should have found a ref in DomB");
1505 } else {
1506
1508 }
1509 Loc DefLoc(DomB, It);
1510 Defs.emplace_back(DefLoc, Refs);
1511}
1512
1513HCE::Register HCE::insertInitializer(Loc DefL, const ExtenderInit &ExtI) {
1514 llvm::Register DefR = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
1518 const ExtValue &EV = ExtI.first;
1520
1521 const ExtExpr &Ex = ExtI.second;
1523
1524 if (Ex.Rs.isSlot()) {
1525 assert(Ex.S == 0 && "Cannot have a shift of a stack slot");
1526 assert(!Ex.Neg && "Cannot subtract a stack slot");
1527
1528 InitI = BuildMI(MBB, At, dl, HII->get(Hexagon::PS_fi), DefR)
1530 .add(ExtOp);
1531 } else {
1532 assert((Ex.Rs.Reg == 0 || Ex.Rs.isVReg()) && "Expecting virtual register");
1533 if (Ex.trivial()) {
1534
1535 InitI = BuildMI(MBB, At, dl, HII->get(Hexagon::A2_tfrsi), DefR)
1536 .add(ExtOp);
1537 } else if (Ex.S == 0) {
1538 if (Ex.Neg) {
1539
1540 InitI = BuildMI(MBB, At, dl, HII->get(Hexagon::A2_subri), DefR)
1541 .add(ExtOp)
1543 } else {
1544
1545 InitI = BuildMI(MBB, At, dl, HII->get(Hexagon::A2_addi), DefR)
1547 .add(ExtOp);
1548 }
1549 } else {
1550 if (HST->useCompound()) {
1551 unsigned NewOpc = Ex.Neg ? Hexagon::S4_subi_asl_ri
1552 : Hexagon::S4_addi_asl_ri;
1553
1554 InitI = BuildMI(MBB, At, dl, HII->get(NewOpc), DefR)
1555 .add(ExtOp)
1558 } else {
1559
1560
1561
1562 llvm::Register TmpR = MRI->createVirtualRegister(&Hexagon::IntRegsRegClass);
1563 BuildMI(MBB, At, dl, HII->get(Hexagon::S2_asl_i_r), TmpR)
1566 if (Ex.Neg)
1567 InitI = BuildMI(MBB, At, dl, HII->get(Hexagon::A2_subri), DefR)
1568 .add(ExtOp)
1570 else
1571 InitI = BuildMI(MBB, At, dl, HII->get(Hexagon::A2_addi), DefR)
1573 .add(ExtOp);
1574 }
1575 }
1576 }
1577
1579 (void)InitI;
1581 << " for initializer: " << PrintInit(ExtI, *HRI) << "\n "
1582 << *InitI);
1583 return { DefR, 0 };
1584}
1585
1586
1587bool HCE::replaceInstrExact(const ExtDesc &ED, Register ExtR) {
1592 unsigned ExtOpc = MI.getOpcode();
1593
1594
1595
1596
1597 unsigned RegOpc = getDirectRegReplacement(ExtOpc);
1598
1599 if (RegOpc == TargetOpcode::REG_SEQUENCE) {
1600 if (ExtOpc == Hexagon::A4_combineri)
1601 BuildMI(MBB, At, dl, HII->get(RegOpc))
1604 .addImm(Hexagon::isub_hi)
1606 .addImm(Hexagon::isub_lo);
1607 else if (ExtOpc == Hexagon::A4_combineir)
1608 BuildMI(MBB, At, dl, HII->get(RegOpc))
1611 .addImm(Hexagon::isub_hi)
1613 .addImm(Hexagon::isub_lo);
1614 else
1617 return true;
1618 }
1619 if (ExtOpc == Hexagon::C2_cmpgei || ExtOpc == Hexagon::C2_cmpgeui) {
1620 unsigned NewOpc = ExtOpc == Hexagon::C2_cmpgei ? Hexagon::C2_cmplt
1621 : Hexagon::C2_cmpltu;
1622 BuildMI(MBB, At, dl, HII->get(NewOpc))
1627 return true;
1628 }
1629
1630 if (RegOpc != 0) {
1632 unsigned RegN = ED.OpNum;
1633
1634 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
1635 if (i != RegN)
1636 MIB.add(MI.getOperand(i));
1637 else
1639 }
1642 return true;
1643 }
1644
1645 if (MI.mayLoadOrStore() && !isStoreImmediate(ExtOpc)) {
1646
1647
1648
1649
1650
1651
1652
1653 unsigned RegOpc, Shift;
1654 unsigned AM = HII->getAddrMode(MI);
1656 RegOpc = HII->changeAddrMode_io_rr(ExtOpc);
1657 Shift = 0;
1659
1660
1661 RegOpc = HII->changeAddrMode_ur_rr(ExtOpc);
1662 Shift = MI.getOperand(MI.mayLoad() ? 2 : 1).getImm();
1663 } else {
1665 }
1666#ifndef NDEBUG
1667 if (RegOpc == -1u) {
1668 dbgs() << "\nExtOpc: " << HII->getName(ExtOpc) << " has no rr version\n";
1670 }
1671#endif
1672
1673 unsigned BaseP, OffP;
1674 HII->getBaseAndOffsetPosition(MI, BaseP, OffP);
1675
1676
1678
1679 if (MI.mayLoad())
1680 MIB.add(getLoadResultOp(MI));
1681
1682 if (HII->isPredicated(MI))
1683 MIB.add(getPredicateOp(MI));
1684
1686 MIB.add(MI.getOperand(BaseP));
1687 MIB.addImm(Shift);
1688
1689 if (MI.mayStore())
1690 MIB.add(getStoredValueOp(MI));
1693 return true;
1694 }
1695
1696#ifndef NDEBUG
1698#endif
1700 return false;
1701}
1702
1703
1704bool HCE::replaceInstrExpr(const ExtDesc &ED, const ExtenderInit &ExtI,
1705 Register ExtR, int32_t &Diff) {
1710 unsigned ExtOpc = MI.getOpcode();
1711
1712 if (ExtOpc == Hexagon::A2_tfrsi) {
1713
1714
1715
1716
1717
1718
1719
1720
1721 unsigned IdxOpc = getRegOffOpcode(ExtOpc);
1722 assert(IdxOpc == Hexagon::A2_addi);
1723
1724
1725 int32_t D = isInt<16>(Diff) ? Diff : (Diff > 0 ? 32767 : -32768);
1726 if (Diff > 32767) {
1727
1728
1729
1731 OffsetRange R = getOffsetRange(MI.getOperand(0));
1734 }
1735 BuildMI(MBB, At, dl, HII->get(IdxOpc))
1739 Diff -= D;
1740#ifndef NDEBUG
1741
1742
1743
1744 OffsetRange Uses = getOffsetRange(MI.getOperand(0));
1745 if (.contains(-Diff))
1746 dbgs() << "Diff: " << -Diff << " out of range " << Uses
1747 << " for " << MI;
1749#endif
1751 return true;
1752 }
1753
1754 const ExtValue &EV = ExtI.first; (void)EV;
1755 const ExtExpr &Ex = ExtI.second; (void)Ex;
1756
1757 if (ExtOpc == Hexagon::A2_addi || ExtOpc == Hexagon::A2_subri) {
1758
1759
1760
1761#ifndef NDEBUG
1762 bool IsAddi = ExtOpc == Hexagon::A2_addi;
1763 const MachineOperand &RegOp = MI.getOperand(IsAddi ? 1 : 2);
1764 const MachineOperand &ImmOp = MI.getOperand(IsAddi ? 2 : 1);
1765 assert(Ex.Rs == RegOp && EV == ImmOp && Ex.Neg != IsAddi &&
1766 "Initializer mismatch");
1767#endif
1768 BuildMI(MBB, At, dl, HII->get(TargetOpcode::COPY))
1771 Diff = 0;
1773 return true;
1774 }
1775 if (ExtOpc == Hexagon::M2_accii || ExtOpc == Hexagon::M2_naccii ||
1776 ExtOpc == Hexagon::S4_addaddi || ExtOpc == Hexagon::S4_subaddi) {
1777
1778
1779
1780
1781
1782
1783
1784#ifndef NDEBUG
1785 bool IsSub = ExtOpc == Hexagon::S4_subaddi;
1786 Register Rs = MI.getOperand(IsSub ? 3 : 2);
1787 ExtValue V = MI.getOperand(IsSub ? 2 : 3);
1788 assert(EV == V && Rs == Ex.Rs && IsSub == Ex.Neg && "Initializer mismatch");
1789#endif
1790 unsigned NewOpc = ExtOpc == Hexagon::M2_naccii ? Hexagon::A2_sub
1791 : Hexagon::A2_add;
1792 BuildMI(MBB, At, dl, HII->get(NewOpc))
1797 return true;
1798 }
1799
1800 if (MI.mayLoadOrStore()) {
1801 unsigned IdxOpc = getRegOffOpcode(ExtOpc);
1802 assert(IdxOpc && "Expecting indexed opcode");
1804
1805
1806 if (MI.mayLoad())
1807 MIB.add(getLoadResultOp(MI));
1808
1809 if (HII->isPredicated(MI))
1810 MIB.add(getPredicateOp(MI));
1811
1814
1815 if (MI.mayStore())
1816 MIB.add(getStoredValueOp(MI));
1819 return true;
1820 }
1821
1822#ifndef NDEBUG
1823 dbgs() << '\n' << PrintInit(ExtI, *HRI) << " " << MI;
1824#endif
1826 return false;
1827}
1828
1829bool HCE::replaceInstr(unsigned Idx, Register ExtR, const ExtenderInit &ExtI) {
1832 return false;
1834 }
1835 const ExtDesc &ED = Extenders[Idx];
1836 assert((!ED.IsDef || ED.Rd.Reg != 0) && "Missing Rd for def");
1837 const ExtValue &DefV = ExtI.first;
1838 assert(ExtRoot(ExtValue(ED)) == ExtRoot(DefV) && "Extender root mismatch");
1839 const ExtExpr &DefEx = ExtI.second;
1840
1841 ExtValue EV(ED);
1842 int32_t Diff = EV.Offset - DefV.Offset;
1844 LLVM_DEBUG(dbgs() << __func__ << " Idx:" << Idx << " ExtR:"
1845 << PrintRegister(ExtR, *HRI) << " Diff:" << Diff << '\n');
1846
1847
1848
1849 bool IsAbs = false, IsAbsSet = false;
1850 if (MI.mayLoadOrStore()) {
1851 unsigned AM = HII->getAddrMode(MI);
1854 }
1855
1856
1857
1858
1859
1860 std::vector<std::pair<MachineInstr*,unsigned>> RegOps;
1861 if (ED.IsDef && Diff != 0) {
1864 RegOps.push_back({&UI, getOperandIndex(UI, Op)});
1865 }
1866 }
1867
1868
1869 bool Replaced = false;
1870 if (Diff == 0 && DefEx.trivial() && !IsAbs && !IsAbsSet)
1871 Replaced = replaceInstrExact(ED, ExtR);
1872 else
1873 Replaced = replaceInstrExpr(ED, ExtI, ExtR, Diff);
1874
1875 if (Diff != 0 && Replaced && ED.IsDef) {
1876
1877 for (std::pair<MachineInstr*,unsigned> P : RegOps) {
1878 unsigned J = P.second;
1879 assert(P.first->getNumOperands() > J+1 &&
1880 P.first->getOperand(J+1).isImm());
1883 }
1884
1885
1886
1887
1888 if (IsAbsSet) {
1889 assert(ED.Rd.Sub == 0 && ExtR.Sub == 0);
1890 MRI->replaceRegWith(ED.Rd.Reg, ExtR.Reg);
1891 }
1892 }
1893
1894 return Replaced;
1895}
1896
1897bool HCE::replaceExtenders(const AssignmentMap &IMap) {
1898 LocDefList Defs;
1900
1901 for (const std::pair<const ExtenderInit, IndexList> &P : IMap) {
1902 const IndexList &Idxs = P.second;
1904 continue;
1905
1906 Defs.clear();
1907 calculatePlacement(P.first, Idxs, Defs);
1908 for (const std::pair<Loc,IndexList> &Q : Defs) {
1909 Register DefR = insertInitializer(Q.first, P.first);
1910 NewRegs.push_back(DefR.Reg);
1911 for (unsigned I : Q.second)
1912 Changed |= replaceInstr(I, DefR, P.first);
1913 }
1914 }
1916}
1917
1918unsigned HCE::getOperandIndex(const MachineInstr &MI,
1920 for (unsigned i = 0, n = MI.getNumOperands(); i != n; ++i)
1921 if (&MI.getOperand(i) == &Op)
1922 return i;
1924}
1925
1927 assert(HII->isPredicated(MI));
1929 if (.isReg() ||
.isUse() ||
1930 MRI->getRegClass(Op.getReg()) != &Hexagon::PredRegsRegClass)
1931 continue;
1932 assert(Op.getSubReg() == 0 && "Predicate register with a subregister");
1933 return Op;
1934 }
1936}
1937
1940 return MI.getOperand(0);
1941}
1942
1945 return MI.getOperand(MI.getNumExplicitOperands()-1);
1946}
1947
1950 return false;
1953 << " due to exception handling\n");
1954 return false;
1955 }
1956 LLVM_DEBUG(MF.print(dbgs() << "Before " << getPassName() << '\n', nullptr));
1957
1961 MDT = &getAnalysis().getDomTree();
1963 AssignmentMap IMap;
1964
1965 collect(MF);
1966 llvm::sort(Extenders, [this](const ExtDesc &A, const ExtDesc &B) {
1968 if (VA != VB)
1969 return VA < VB;
1972 if (MA == MB) {
1973
1974 return A.OpNum < B.OpNum;
1975 }
1976
1980 if (BA != BB)
1982 return MDT->dominates(MA, MB);
1983 });
1984
1986 LLVM_DEBUG(dbgs() << "Collected " << Extenders.size() << " extenders\n");
1987 for (unsigned I = 0, E = Extenders.size(); I != E; ) {
1989 const ExtRoot &T = Extenders[B].getOp();
1990 while (I != E && ExtRoot(Extenders[I].getOp()) == T)
1991 ++I;
1992
1993 IMap.clear();
1994 assignInits(T, B, I, IMap);
1995 Changed |= replaceExtenders(IMap);
1996 }
1997
2000 MF.print(dbgs() << "After " << getPassName() << '\n', nullptr);
2001 else
2002 dbgs() << "No changes\n";
2003 });
2005}
2006
2008 return new HexagonConstExtenders();
2009}
unsigned const MachineRegisterInfo * MRI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
static cl::opt< unsigned > CountThreshold("hexagon-cext-threshold", cl::init(3), cl::Hidden, cl::desc("Minimum number of extenders to trigger replacement"))
hexagon cext Hexagon constant extender static false unsigned ReplaceCounter
Definition HexagonConstExtenders.cpp:563
static int32_t adjustUp(int32_t V, uint8_t A, uint8_t O)
Definition HexagonConstExtenders.cpp:40
static cl::opt< unsigned > ReplaceLimit("hexagon-cext-limit", cl::init(0), cl::Hidden, cl::desc("Maximum number of replacements"))
static int32_t adjustDown(int32_t V, uint8_t A, uint8_t O)
Definition HexagonConstExtenders.cpp:46
static Interval intersect(const Interval &I1, const Interval &I2)
Promote Memory to Register
static MCRegister getReg(const MCDisassembler *D, unsigned RC, unsigned RegNo)
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Remove Loads Into Fake Uses
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallVector class.
APInt bitcastToAPInt() const
bool ult(const APInt &RHS) const
Unsigned less than comparison.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
const Function * getParent() const
Return the enclosing method, or null if none.
Implements a dense probed hash-table based set.
FunctionPass class - This class is used to implement most global optimizations.
bool hasPersonalityFn() const
Check whether this function has a personality function.
const HexagonRegisterInfo & getRegisterInfo() const
const HexagonInstrInfo * getInstrInfo() const override
Describe properties that are true of each instruction in the target description file.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
LLVM_ABI iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
LLVM_ABI DebugLoc findDebugLoc(instr_iterator MBBI)
Find the next valid DebugLoc starting at MBBI, skipping any debug instructions.
MachineInstrBundleIterator< MachineInstr > iterator
Analysis pass which computes a MachineDominatorTree.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
void print(raw_ostream &OS, const SlotIndexes *=nullptr) const
print - Print out the MachineFunction in a format suitable for debugging to the specified stream.
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
const MachineInstrBuilder & add(const MachineOperand &MO) const
const MachineInstrBuilder & cloneMemRefs(const MachineInstr &OtherMI) const
Representation of each machine instruction.
const MachineBasicBlock * getParent() const
MachineOperand class - Representation of each machine instruction operand.
static MachineOperand CreateES(const char *SymName, unsigned TargetFlags=0)
static MachineOperand CreateFPImm(const ConstantFP *CFP)
void setImm(int64_t immVal)
static MachineOperand CreateImm(int64_t Val)
static MachineOperand CreateJTI(unsigned Idx, unsigned TargetFlags=0)
static MachineOperand CreateGA(const GlobalValue *GV, int64_t Offset, unsigned TargetFlags=0)
static MachineOperand CreateBA(const BlockAddress *BA, int64_t Offset, unsigned TargetFlags=0)
static MachineOperand CreateCPI(unsigned Idx, int Offset, unsigned TargetFlags=0)
@ MO_Immediate
Immediate operand.
@ MO_ConstantPoolIndex
Address of indexed Constant in Constant Pool.
@ MO_GlobalAddress
Address of a global value.
@ MO_BlockAddress
Address of a basic block.
@ MO_ExternalSymbol
Name of external global symbol.
@ MO_JumpTableIndex
Address of indexed Jump Table for switch.
@ MO_TargetIndex
Target-dependent index+offset operand.
@ MO_FPImmediate
Floating-point immediate operand.
static MachineOperand CreateReg(Register Reg, bool isDef, bool isImp=false, bool isKill=false, bool isDead=false, bool isUndef=false, bool isEarlyClobber=false, unsigned SubReg=0, bool isDebug=false, bool isInternalRead=false, bool isRenamable=false)
static MachineOperand CreateTargetIndex(unsigned Idx, int64_t Offset, unsigned TargetFlags=0)
static MachineOperand CreateFI(int Idx)
Wrapper class representing virtual and physical registers.
static Register index2StackSlot(int FI)
Convert a non-negative frame index to a stack slot register value.
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.
std::pair< iterator, bool > insert(const ValueT &V)
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
self_iterator getIterator()
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.
constexpr char SymbolName[]
Key for Kernel::Metadata::mSymbolName.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
static unsigned getMemAccessSizeInBytes(MemAccessSize S)
@ BasicBlock
Various leaf nodes.
initializer< Ty > init(const Ty &Val)
NodeAddr< NodeBase * > Node
LLVM_ABI std::error_code remove(const Twine &path, bool IgnoreNonExisting=true)
Remove path.
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
bool operator<(int64_t V1, const APSInt &V2)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
constexpr bool isInt(int64_t x)
Checks if an integer fits into the given bit width.
bool operator!=(uint64_t V1, const APInt &V2)
constexpr T alignDown(U Value, V Align, W Skew=0)
Returns the largest unsigned integer less than or equal to Value and is Skew mod Align.
FunctionPass * createHexagonConstExtenders()
Definition HexagonConstExtenders.cpp:2007
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
void sort(IteratorTy Start, IteratorTy End)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
DWARFExpression::Operation Op
auto max_element(R &&Range)
Provide wrappers to std::max_element which take ranges instead of having to pass begin/end explicitly...
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
LLVM_ABI Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
This struct is a compact representation of a valid (non-zero power of two) alignment.