LLVM: lib/Target/ARM/ARMConstantIslandPass.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
40#include "llvm/Config/llvm-config.h"
51#include
52#include
53#include
54#include
55#include
56#include
57
58using namespace llvm;
59
60#define DEBUG_TYPE "arm-cp-islands"
61
62#define ARM_CP_ISLANDS_OPT_NAME \
63 "ARM constant island placement and branch shortening pass"
64STATISTIC(NumCPEs, "Number of constpool entries");
65STATISTIC(NumSplit, "Number of uncond branches inserted");
66STATISTIC(NumCBrFixed, "Number of cond branches fixed");
67STATISTIC(NumUBrFixed, "Number of uncond branches fixed");
68STATISTIC(NumTBs, "Number of table branches generated");
69STATISTIC(NumT2CPShrunk, "Number of Thumb2 constantpool instructions shrunk");
70STATISTIC(NumT2BrShrunk, "Number of Thumb2 immediate branches shrunk");
71STATISTIC(NumCBZ, "Number of CBZ / CBNZ formed");
72STATISTIC(NumJTMoved, "Number of jump table destination blocks moved");
73STATISTIC(NumJTInserted, "Number of jump table intermediate blocks inserted");
74STATISTIC(NumLEInserted, "Number of LE backwards branches inserted");
75
78 cl::desc("Adjust basic block layout to better use TB[BH]"));
79
82 cl::desc("The max number of iteration for converge"));
83
86 cl::desc("Use compressed jump tables in Thumb-1 by synthesizing an "
87 "equivalent to the TBB/TBH instructions"));
88
89namespace {
90
91
92
93
94
95
96
97
98
99
100
101
103 std::unique_ptr BBUtils = nullptr;
104
105
106
107
108 std::vector<MachineBasicBlock*> WaterList;
109
110
111
113
114 using water_iterator = std::vector<MachineBasicBlock *>::iterator;
115
116
117
118
119
120
121
122
123
124
125
126
127
128 struct CPUser {
132 unsigned MaxDisp;
133 bool NegOk;
134 bool IsSoImm;
135 bool KnownAlignment = false;
136
138 bool neg, bool soimm)
139 : MI(mi), CPEMI(cpemi), MaxDisp(maxdisp), NegOk(neg), IsSoImm(soimm) {
140 HighWaterMark = CPEMI->getParent();
141 }
142
143
144
145
146 unsigned getMaxDisp() const {
147 return (KnownAlignment ? MaxDisp : MaxDisp - 2) - 2;
148 }
149 };
150
151
152
153 std::vector CPUsers;
154
155
156
157
158 struct CPEntry {
160 unsigned CPI;
161 unsigned RefCount;
162
163 CPEntry(MachineInstr *cpemi, unsigned cpi, unsigned rc = 0)
164 : CPEMI(cpemi), CPI(cpi), RefCount(rc) {}
165 };
166
167
168
169
170
171
172
173
174
175
176 std::vector<std::vector> CPEntries;
177
178
179
181
182
183
185
186
188
189
190
191
192
193 struct ImmBranch {
195 unsigned MaxDisp : 31;
196 bool isCond : 1;
197 unsigned UncondBr;
198
199 ImmBranch(MachineInstr *mi, unsigned maxdisp, bool cond, unsigned ubr)
200 : MI(mi), MaxDisp(maxdisp), isCond(cond), UncondBr(ubr) {}
201 };
202
203
204 std::vector ImmBranches;
205
206
208
209
211
219 bool isThumb1;
220 bool isThumb2;
221 bool isPositionIndependentOrROPI;
222
223 public:
224 static char ID;
225
227
229
233 }
234
237 MachineFunctionProperties::Property::NoVRegs);
238 }
239
242 }
243
244 private:
245 void doInitialConstPlacement(std::vector<MachineInstr *> &CPEMIs);
246 void doInitialJumpTablePlacement(std::vector<MachineInstr *> &CPEMIs);
248 CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI);
250 void scanFunctionJumpTables();
251 void initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs);
254 bool decrementCPEReferenceCount(unsigned CPI, MachineInstr* CPEMI);
255 unsigned getCombinedIndex(const MachineInstr *CPEMI);
256 int findInRangeCPEntry(CPUser& U, unsigned UserOffset);
257 bool findAvailableWater(CPUser&U, unsigned UserOffset,
258 water_iterator &WaterIter, bool CloserWater);
259 void createNewWater(unsigned CPUserIndex, unsigned UserOffset,
261 bool handleConstantPoolUser(unsigned CPUserIndex, bool CloserWater);
263 bool removeUnusedCPEntries();
264 bool isCPEntryInRange(MachineInstr *MI, unsigned UserOffset,
265 MachineInstr *CPEMI, unsigned Disp, bool NegOk,
266 bool DoDump = false);
267 bool isWaterInRange(unsigned UserOffset, MachineBasicBlock *Water,
268 CPUser &U, unsigned &Growth);
269 bool fixupImmediateBr(ImmBranch &Br);
270 bool fixupConditionalBr(ImmBranch &Br);
271 bool fixupUnconditionalBr(ImmBranch &Br);
272 bool optimizeThumb2Instructions();
273 bool optimizeThumb2Branches();
274 bool reorderThumb2JumpTables();
276 unsigned &DeadSize, bool &CanDeleteLEA,
277 bool &BaseRegKill);
278 bool optimizeThumb2JumpTables();
282
283 unsigned getUserOffset(CPUser&) const;
284 void dumpBBs();
286
287 bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset,
288 unsigned Disp, bool NegativeOK, bool IsSoImm = false);
289 bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset,
290 const CPUser &U) {
291 return isOffsetInRange(UserOffset, TrialOffset,
292 U.getMaxDisp(), U.NegOk, U.IsSoImm);
293 }
294 };
295
296}
297
298char ARMConstantIslands::ID = 0;
299
300
301void ARMConstantIslands::verify() {
302#ifndef NDEBUG
306 return BBInfo[LHS.getNumber()].postOffset() <
307 BBInfo[RHS.getNumber()].postOffset();
308 }));
309 LLVM_DEBUG(dbgs() << "Verifying " << CPUsers.size() << " CP users.\n");
310 for (CPUser &U : CPUsers) {
311 unsigned UserOffset = getUserOffset(U);
312
313
314 if (isCPEntryInRange(U.MI, UserOffset, U.CPEMI, U.getMaxDisp()+2, U.NegOk,
315 true)) {
317 continue;
318 }
320 dumpBBs();
323 }
324#endif
325}
326
327#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
328
332 for (unsigned J = 0, E = BBInfo.size(); J !=E; ++J) {
333 const BasicBlockInfo &BBI = BBInfo[J];
334 dbgs() << format("%08x %bb.%u\t", BBI.Offset, J)
335 << " kb=" << unsigned(BBI.KnownBits)
336 << " ua=" << unsigned(BBI.Unalign) << " pa=" << Log2(BBI.PostAlign)
337 << format(" size=%#x\n", BBInfo[J].Size);
338 }
339 });
340}
341#endif
342
343
344
345
349 return false;
350
352 const Align Alignment = TLI->getPrefLoopAlignment();
353 if (Alignment < 4)
354 return false;
355
356 bool Changed = false;
357 bool PrevCanFallthough = true;
358 for (auto &MBB : *MF) {
359 if (!PrevCanFallthough) {
360 Changed = true;
362 }
363
365
366
367
368 if (STI->hasLOB()) {
370 if (MI.getOpcode() == ARM::t2B &&
372 continue;
373 if (isLoopStart(MI) || MI.getOpcode() == ARM::t2LoopEnd ||
374 MI.getOpcode() == ARM::t2LoopEndDec) {
375 PrevCanFallthough = true;
376 break;
377 }
378
379 break;
380 }
381 }
382 }
383
384 return Changed;
385}
386
387bool ARMConstantIslands::runOnMachineFunction(MachineFunction &mf) {
388 MF = &mf;
390 BBUtils = std::make_unique(mf);
391
393 << MCP->getConstants().size() << " CP entries, aligned to "
394 << MCP->getConstantPoolAlign().value() << " bytes *****\n");
395
397 TII = STI->getInstrInfo();
398 isPositionIndependentOrROPI =
399 STI->getTargetLowering()->isPositionIndependent() || STI->isROPI();
401 DT = &getAnalysis().getDomTree();
402
403 isThumb = AFI->isThumbFunction();
404 isThumb1 = AFI->isThumb1OnlyFunction();
405 isThumb2 = AFI->isThumb2Function();
406
408
409
410 if (STI->hardenSlsRetBr())
411 GenerateTBB = false;
412
413
414
415 MF->RenumberBlocks();
417
418
419
420 bool MadeChange = false;
422 scanFunctionJumpTables();
423 MadeChange |= reorderThumb2JumpTables();
424
425 T2JumpTables.clear();
426
427 MF->RenumberBlocks();
429 }
430
431
433
434
435
436 std::vector<MachineInstr*> CPEMIs;
437 if (!MCP->isEmpty())
438 doInitialConstPlacement(CPEMIs);
439
440 if (MF->getJumpTableInfo())
441 doInitialJumpTablePlacement(CPEMIs);
442
443
444 AFI->initPICLabelUId(CPEMIs.size());
445
446
447
448
449 initializeFunctionInfo(CPEMIs);
450 CPEMIs.clear();
452
453
454
455 if (!T2JumpTables.empty())
456 MF->ensureAlignment(Align(4));
457
458
459 MadeChange |= removeUnusedCPEntries();
460
461
462
463 unsigned NoCPIters = 0, NoBRIters = 0;
464 while (true) {
465 LLVM_DEBUG(dbgs() << "Beginning CP iteration #" << NoCPIters << '\n');
466 bool CPChange = false;
467 for (unsigned i = 0, e = CPUsers.size(); i != e; ++i)
468
469
470
471 CPChange |= handleConstantPoolUser(i, NoCPIters >= CPMaxIteration / 2);
475
476
477
478 NewWaterList.clear();
479
480 LLVM_DEBUG(dbgs() << "Beginning BR iteration #" << NoBRIters << '\n');
481 bool BRChange = false;
482 for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i)
483 BRChange |= fixupImmediateBr(ImmBranches[i]);
484 if (BRChange && ++NoBRIters > 30)
487
488 if (!CPChange && !BRChange)
489 break;
490 MadeChange = true;
491 }
492
493
494 if (isThumb2 && !STI->prefers32BitThumb())
495 MadeChange |= optimizeThumb2Instructions();
496
497
498 if (isThumb && STI->hasV8MBaselineOps())
499 MadeChange |= optimizeThumb2Branches();
500
501
502 if (GenerateTBB && !STI->genExecuteOnly())
503 MadeChange |= optimizeThumb2JumpTables();
504
505
507
508
509 for (unsigned i = 0, e = CPEntries.size(); i != e; ++i) {
510 for (unsigned j = 0, je = CPEntries[i].size(); j != je; ++j) {
511 const CPEntry & CPE = CPEntries[i][j];
512 if (CPE.CPEMI && CPE.CPEMI->getOperand(1).isCPI())
513 AFI->recordCPEClone(i, CPE.CPI);
514 }
515 }
516
518
519 BBUtils->clear();
520 WaterList.clear();
521 CPUsers.clear();
522 CPEntries.clear();
523 JumpTableEntryIndices.clear();
524 JumpTableUserIndices.clear();
525 BlockJumpTableRefCount.clear();
526 ImmBranches.clear();
527 PushPopMIs.clear();
528 T2JumpTables.clear();
529
530 return MadeChange;
531}
532
533
534
535void
536ARMConstantIslands::doInitialConstPlacement(std::vector<MachineInstr*> &CPEMIs) {
537
540
541
542 const Align MaxAlign = MCP->getConstantPoolAlign();
543 const unsigned MaxLogAlign = Log2(MaxAlign);
544
545
547
548
549
550
551 Align FuncAlign = MaxAlign;
552 if (MaxAlign == 2)
553 FuncAlign = Align(4);
554 MF->ensureAlignment(FuncAlign);
555
556
557
558
559
561 BB->end());
562
563
564
565 const std::vector &CPs = MCP->getConstants();
566
567 const DataLayout &TD = MF->getDataLayout();
568 for (unsigned i = 0, e = CPs.size(); i != e; ++i) {
569 unsigned Size = CPs[i].getSizeInBytes(TD);
570 Align Alignment = CPs[i].getAlign();
571
572
573 assert(isAligned(Alignment, Size) && "CP Entry not multiple of 4 bytes!");
574
575
576 unsigned LogAlign = Log2(Alignment);
581 CPEMIs.push_back(CPEMI);
582
583
584
585 for (unsigned a = LogAlign + 1; a <= MaxLogAlign; ++a)
586 if (InsPoint[a] == InsAt)
587 InsPoint[a] = CPEMI;
588
589
590 CPEntries.emplace_back(1, CPEntry(CPEMI, i));
591 ++NumCPEs;
592 LLVM_DEBUG(dbgs() << "Moved CPI#" << i << " to end of function, size = "
593 << Size << ", align = " << Alignment.value() << '\n');
594 }
596}
597
598
599
600
601
602
603void ARMConstantIslands::doInitialJumpTablePlacement(
604 std::vector<MachineInstr *> &CPEMIs) {
605 unsigned i = CPEntries.size();
606 auto MJTI = MF->getJumpTableInfo();
607 const std::vector &JT = MJTI->getJumpTables();
608
609
611 return;
612
616
619 MI->isDebugInstr()))
620 --MI;
621
623 continue;
624
625 unsigned JTOpcode;
626 switch (MI->getOpcode()) {
627 default:
628 continue;
629 case ARM::BR_JTadd:
630 case ARM::BR_JTr:
631 case ARM::tBR_JTr:
632 case ARM::BR_JTm_i12:
633 case ARM::BR_JTm_rs:
634
635
636
638 "Branch protection must not be enabled for Arm or Thumb1 modes");
639 JTOpcode = ARM::JUMPTABLE_ADDRS;
640 break;
641 case ARM::t2BR_JT:
642 JTOpcode = ARM::JUMPTABLE_INSTS;
643 break;
644 case ARM::tTBB_JT:
645 case ARM::t2TBB_JT:
646 JTOpcode = ARM::JUMPTABLE_TBB;
647 break;
648 case ARM::tTBH_JT:
649 case ARM::t2TBH_JT:
650 JTOpcode = ARM::JUMPTABLE_TBH;
651 break;
652 }
653
654 unsigned NumOps = MI->getDesc().getNumOperands();
656 MI->getOperand(NumOps - (MI->isPredicable() ? 2 : 1));
657 unsigned JTI = JTOp.getIndex();
658 unsigned Size = JT[JTI].MBBs.size() * sizeof(uint32_t);
666 CPEMIs.push_back(CPEMI);
667 CPEntries.emplace_back(1, CPEntry(CPEMI, JTI));
668 JumpTableEntryIndices.insert(std::make_pair(JTI, CPEntries.size() - 1));
669 if (!LastCorrectlyNumberedBB)
670 LastCorrectlyNumberedBB = &MBB;
671 }
672
673
674 if (LastCorrectlyNumberedBB) {
675 MF->RenumberBlocks(LastCorrectlyNumberedBB);
677 }
678}
679
680
681
683
685
687 return false;
688
691 return false;
692
693
694
698 return TooDifficult || FBB == nullptr;
699}
700
701
702
703ARMConstantIslands::CPEntry *
704ARMConstantIslands::findConstPoolEntry(unsigned CPI,
706 std::vector &CPEs = CPEntries[CPI];
707
708
709 for (CPEntry &CPE : CPEs)
710 if (CPE.CPEMI == CPEMI)
711 return &CPE;
712 return nullptr;
713}
714
715
716
717Align ARMConstantIslands::getCPEAlign(const MachineInstr *CPEMI) {
719 case ARM::CONSTPOOL_ENTRY:
720 break;
721 case ARM::JUMPTABLE_TBB:
722 return isThumb1 ? Align(4) : Align(1);
723 case ARM::JUMPTABLE_TBH:
724 return isThumb1 ? Align(4) : Align(2);
725 case ARM::JUMPTABLE_INSTS:
727 case ARM::JUMPTABLE_ADDRS:
729 default:
731 }
732
733 unsigned CPI = getCombinedIndex(CPEMI);
734 assert(CPI < MCP->getConstants().size() && "Invalid constant pool index.");
735 return MCP->getConstants()[CPI].getAlign();
736}
737
738
739
740
744}
745
746
747
748
749void ARMConstantIslands::scanFunctionJumpTables() {
752 if (I.isBranch() &&
753 (I.getOpcode() == ARM::t2BR_JT || I.getOpcode() == ARM::tBR_JTr))
755 }
756
758 return;
759
764
765
766 BlockJumpTableRefCount[MBB] = std::numeric_limits::max();
767 else
768 ++BlockJumpTableRefCount[MBB];
769 }
770}
771
772
773
774
775void ARMConstantIslands::
776initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs) {
777
778 BBUtils->computeAllBlockSizes();
780
781
782 BBInfo.front().KnownBits = Log2(MF->getAlignment());
783
784
785 BBUtils->adjustBBOffsetsAfter(&MF->front());
786
787
789 bool InlineJumpTables =
791
792
794
795
797 WaterList.push_back(&MBB);
798
800 if (I.isDebugInstr())
801 continue;
802
803 unsigned Opc = I.getOpcode();
804 if (I.isBranch()) {
805 bool isCond = false;
806 unsigned Bits = 0;
807 unsigned Scale = 1;
808 int UOpc = Opc;
809 switch (Opc) {
810 default:
811 continue;
812 case ARM::t2BR_JT:
813 case ARM::tBR_JTr:
814 if (InlineJumpTables)
815 T2JumpTables.push_back(&I);
816 continue;
817 case ARM::Bcc:
818 isCond = true;
819 UOpc = ARM::B;
820 [[fallthrough]];
821 case ARM::B:
823 Scale = 4;
824 break;
825 case ARM::tBcc:
826 isCond = true;
827 UOpc = ARM::tB;
829 Scale = 2;
830 break;
831 case ARM::tB:
833 Scale = 2;
834 break;
835 case ARM::t2Bcc:
836 isCond = true;
837 UOpc = ARM::t2B;
839 Scale = 2;
840 break;
841 case ARM::t2B:
843 Scale = 2;
844 break;
845 }
846
847
848 unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale;
849 ImmBranches.push_back(ImmBranch(&I, MaxOffs, isCond, UOpc));
850 }
851
852 if (Opc == ARM::tPUSH || Opc == ARM::tPOP_RET)
853 PushPopMIs.push_back(&I);
854
855 if (Opc == ARM::CONSTPOOL_ENTRY || Opc == ARM::JUMPTABLE_ADDRS ||
856 Opc == ARM::JUMPTABLE_INSTS || Opc == ARM::JUMPTABLE_TBB ||
857 Opc == ARM::JUMPTABLE_TBH)
858 continue;
859
860
861 for (unsigned op = 0, e = I.getNumOperands(); op != e; ++op)
862 if (I.getOperand(op).isCPI() ||
863 (I.getOperand(op).isJTI() && InlineJumpTables)) {
864
865
866
867
868 unsigned Bits = 0;
869 unsigned Scale = 1;
870 bool NegOk = false;
871 bool IsSoImm = false;
872
873 switch (Opc) {
874 default:
875 llvm_unreachable("Unknown addressing mode for CP reference!");
876
877
878 case ARM::LEApcrel:
879 case ARM::LEApcrelJT: {
880
881
882
883
885 NegOk = true;
886 IsSoImm = true;
887 unsigned CPI = I.getOperand(op).getIndex();
888 assert(CPI < CPEMIs.size());
890 const Align CPEAlign = getCPEAlign(CPEMI);
891 const unsigned LogCPEAlign = Log2(CPEAlign);
892 if (LogCPEAlign >= 2)
893 Scale = 4;
894 else
895
896
897 Scale = 1;
898 }
899 break;
900 case ARM::t2LEApcrel:
901 case ARM::t2LEApcrelJT:
903 NegOk = true;
904 break;
905 case ARM::tLEApcrel:
906 case ARM::tLEApcrelJT:
908 Scale = 4;
909 break;
910
911 case ARM::LDRBi12:
912 case ARM::LDRi12:
913 case ARM::LDRcp:
914 case ARM::t2LDRpci:
915 case ARM::t2LDRHpci:
916 case ARM::t2LDRSHpci:
917 case ARM::t2LDRBpci:
918 case ARM::t2LDRSBpci:
919 Bits = 12;
920 NegOk = true;
921 break;
922
923 case ARM::tLDRpci:
925 Scale = 4;
926 break;
927
928 case ARM::VLDRD:
929 case ARM::VLDRS:
931 Scale = 4;
932 NegOk = true;
933 break;
934 case ARM::VLDRH:
936 Scale = 2;
937 NegOk = true;
938 break;
939 }
940
941
942 unsigned CPI = I.getOperand(op).getIndex();
943 if (I.getOperand(op).isJTI()) {
944 JumpTableUserIndices.insert(std::make_pair(CPI, CPUsers.size()));
945 CPI = JumpTableEntryIndices[CPI];
946 }
947
949 unsigned MaxOffs = ((1 << Bits)-1) * Scale;
950 CPUsers.push_back(CPUser(&I, CPEMI, MaxOffs, NegOk, IsSoImm));
951
952
953 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
954 assert(CPE && "Cannot find a corresponding CPEntry!");
955 CPE->RefCount++;
956
957
958
959 break;
960 }
961 }
962 }
963}
964
965
966
969 return LHS->getNumber() < RHS->getNumber();
970}
971
972
973
974
975void ARMConstantIslands::updateForInsertedWaterBlock(MachineBasicBlock *NewBB) {
976
979
980
981
983
984
985
987 WaterList.insert(IP, NewBB);
988}
989
990
991
992
995
996
997 LivePhysRegs LRs(*MF->getSubtarget().getRegisterInfo());
998 LRs.addLiveOuts(*OrigBB);
1001 LRs.stepBackward(LiveMI);
1002
1003
1005 MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
1007 MF->insert(MBBI, NewBB);
1008
1009
1010 NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end());
1011
1012
1013
1014
1015
1016 unsigned Opc = isThumb ? (isThumb2 ? ARM::t2B : ARM::tB) : ARM::B;
1019 else
1023 ++NumSplit;
1024
1025
1027
1028
1030
1031
1034 if (.isReserved(L))
1036
1037
1038
1039
1040 MF->RenumberBlocks(NewBB);
1042
1043
1044
1046
1047
1048
1049
1050
1053 if (WaterBB == OrigBB)
1054 WaterList.insert(std::next(IP), NewBB);
1055 else
1056 WaterList.insert(IP, OrigBB);
1057 NewWaterList.insert(OrigBB);
1058
1059
1060
1061
1062
1063
1064 BBUtils->computeBlockSize(OrigBB);
1065
1066
1067
1068 BBUtils->computeBlockSize(NewBB);
1069
1070
1071 BBUtils->adjustBBOffsetsAfter(OrigBB);
1072
1073 return NewBB;
1074}
1075
1076
1077
1078
1079unsigned ARMConstantIslands::getUserOffset(CPUser &U) const {
1080 unsigned UserOffset = BBUtils->getOffsetOf(U.MI);
1081
1083 const BasicBlockInfo &BBI = BBInfo[U.MI->getParent()->getNumber()];
1085
1086
1087 UserOffset += (isThumb ? 4 : 8);
1088
1089
1090
1091 U.KnownAlignment = (KnownBits >= 2);
1092
1093
1094
1095
1096 if (isThumb && U.KnownAlignment)
1097 UserOffset &= ~3u;
1098
1099 return UserOffset;
1100}
1101
1102
1103
1104
1105
1106
1107
1108bool ARMConstantIslands::isOffsetInRange(unsigned UserOffset,
1109 unsigned TrialOffset, unsigned MaxDisp,
1110 bool NegativeOK, bool IsSoImm) {
1111 if (UserOffset <= TrialOffset) {
1112
1113 if (TrialOffset - UserOffset <= MaxDisp)
1114 return true;
1115
1116 } else if (NegativeOK) {
1117 if (UserOffset - TrialOffset <= MaxDisp)
1118 return true;
1119
1120 }
1121 return false;
1122}
1123
1124
1125
1126
1127
1128bool ARMConstantIslands::isWaterInRange(unsigned UserOffset,
1130 unsigned &Growth) {
1131 BBInfoVector &BBInfo = BBUtils->getBBInfo();
1132 const Align CPEAlign = getCPEAlign(U.CPEMI);
1133 const unsigned CPEOffset = BBInfo[Water->getNumber()].postOffset(CPEAlign);
1134 unsigned NextBlockOffset;
1135 Align NextBlockAlignment;
1137 if (++NextBlock == MF->end()) {
1138 NextBlockOffset = BBInfo[Water->getNumber()].postOffset();
1139 } else {
1140 NextBlockOffset = BBInfo[NextBlock->getNumber()].Offset;
1141 NextBlockAlignment = NextBlock->getAlignment();
1142 }
1143 unsigned Size = U.CPEMI->getOperand(2).getImm();
1144 unsigned CPEEnd = CPEOffset + Size;
1145
1146
1147
1148
1149 if (CPEEnd > NextBlockOffset) {
1150 Growth = CPEEnd - NextBlockOffset;
1151
1152
1154
1155
1156
1157
1158 if (CPEOffset < UserOffset)
1159 UserOffset += Growth + UnknownPadding(MF->getAlignment(), Log2(CPEAlign));
1160 } else
1161
1162 Growth = 0;
1163
1164 return isOffsetInRange(UserOffset, CPEOffset, U);
1165}
1166
1167
1168
1169bool ARMConstantIslands::isCPEntryInRange(MachineInstr *MI, unsigned UserOffset,
1171 bool NegOk, bool DoDump) {
1172 unsigned CPEOffset = BBUtils->getOffsetOf(CPEMI);
1173
1174 if (DoDump) {
1176 BBInfoVector &BBInfo = BBUtils->getBBInfo();
1177 unsigned Block = MI->getParent()->getNumber();
1180 << " max delta=" << MaxDisp
1181 << format(" insn address=%#x", UserOffset) << " in "
1184 << format("CPE address=%#x offset=%+d: ", CPEOffset,
1185 int(CPEOffset - UserOffset));
1186 });
1187 }
1188
1189 return isOffsetInRange(UserOffset, CPEOffset, MaxDisp, NegOk);
1190}
1191
1192#ifndef NDEBUG
1193
1194
1197 return false;
1198
1203 || PredMI->getOpcode() == ARM::t2B)
1205 return false;
1206}
1207#endif
1208
1209
1210
1211
1212
1213bool ARMConstantIslands::decrementCPEReferenceCount(unsigned CPI,
1215
1216 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
1217 assert(CPE && "Unexpected!");
1218 if (--CPE->RefCount == 0) {
1219 removeDeadCPEMI(CPEMI);
1220 CPE->CPEMI = nullptr;
1221 --NumCPEs;
1222 return true;
1223 }
1224 return false;
1225}
1226
1227unsigned ARMConstantIslands::getCombinedIndex(const MachineInstr *CPEMI) {
1230
1232}
1233
1234
1235
1236
1237
1238
1239
1240int ARMConstantIslands::findInRangeCPEntry(CPUser& U, unsigned UserOffset) {
1243
1244
1245 if (isCPEntryInRange(UserMI, UserOffset, CPEMI, U.getMaxDisp(), U.NegOk,
1246 true)) {
1248 return 1;
1249 }
1250
1251
1252 unsigned CPI = getCombinedIndex(CPEMI);
1253 std::vector &CPEs = CPEntries[CPI];
1254 for (CPEntry &CPE : CPEs) {
1255
1256 if (CPE.CPEMI == CPEMI)
1257 continue;
1258
1259 if (CPE.CPEMI == nullptr)
1260 continue;
1261 if (isCPEntryInRange(UserMI, UserOffset, CPE.CPEMI, U.getMaxDisp(),
1262 U.NegOk)) {
1263 LLVM_DEBUG(dbgs() << "Replacing CPE#" << CPI << " with CPE#" << CPE.CPI
1264 << "\n");
1265
1266 U.CPEMI = CPE.CPEMI;
1267
1269 if (MO.isCPI()) {
1270 MO.setIndex(CPE.CPI);
1271 break;
1272 }
1273
1274 CPE.RefCount++;
1275
1276
1277 return decrementCPEReferenceCount(CPI, CPEMI) ? 2 : 1;
1278 }
1279 }
1280 return 0;
1281}
1282
1283
1284
1286 switch (Opc) {
1287 case ARM::tB:
1288 return ((1<<10)-1)*2;
1289 case ARM::t2B:
1290 return ((1<<23)-1)*2;
1291 default:
1292 break;
1293 }
1294
1295 return ((1<<23)-1)*4;
1296}
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306bool ARMConstantIslands::findAvailableWater(CPUser &U, unsigned UserOffset,
1307 water_iterator &WaterIter,
1308 bool CloserWater) {
1309 if (WaterList.empty())
1310 return false;
1311
1312 unsigned BestGrowth = ~0u;
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1324 BBInfoVector &BBInfo = BBUtils->getBBInfo();
1325 const Align CPEAlign = getCPEAlign(U.CPEMI);
1326 unsigned MinNoSplitDisp =
1327 BBInfo[UserBB->getNumber()].postOffset(CPEAlign) - UserOffset;
1328 if (CloserWater && MinNoSplitDisp > U.getMaxDisp() / 2)
1329 return false;
1330 for (water_iterator IP = std::prev(WaterList.end()), B = WaterList.begin();;
1331 --IP) {
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343 unsigned Growth;
1344 if (isWaterInRange(UserOffset, WaterBB, U, Growth) &&
1345 (WaterBB->getNumber() < U.HighWaterMark->getNumber() ||
1346 NewWaterList.count(WaterBB) || WaterBB == U.MI->getParent()) &&
1347 Growth < BestGrowth) {
1348
1349 BestGrowth = Growth;
1350 WaterIter = IP;
1352 << " Growth=" << Growth << '\n');
1353
1354 if (CloserWater && WaterBB == U.MI->getParent())
1355 return true;
1356
1357
1358 if (!CloserWater && BestGrowth == 0)
1359 return true;
1360 }
1361 if (IP == B)
1362 break;
1363 }
1364 return BestGrowth != ~0u;
1365}
1366
1367
1368
1369
1370
1371
1372
1373
1374void ARMConstantIslands::createNewWater(unsigned CPUserIndex,
1375 unsigned UserOffset,
1377 CPUser &U = CPUsers[CPUserIndex];
1380 const Align CPEAlign = getCPEAlign(CPEMI);
1382 BBInfoVector &BBInfo = BBUtils->getBBInfo();
1384
1385
1386
1387
1388
1390
1391 unsigned Delta = isThumb1 ? 2 : 4;
1392
1393 unsigned CPEOffset = UserBBI.postOffset(CPEAlign) + Delta;
1394
1395 if (isOffsetInRange(UserOffset, CPEOffset, U)) {
1397 << format(", expected CPE offset %#x\n", CPEOffset));
1399
1400
1401
1402
1403
1404 int UncondBr = isThumb ? ((isThumb2) ? ARM::t2B : ARM::tB) : ARM::B;
1407 else
1412 ImmBranches.push_back(ImmBranch(&UserMBB->back(),
1413 MaxDisp, false, UncondBr));
1414 BBUtils->computeBlockSize(UserMBB);
1415 BBUtils->adjustBBOffsetsAfter(UserMBB);
1416 return;
1417 }
1418 }
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435 const Align Align = MF->getAlignment();
1436 assert(Align >= CPEAlign && "Over-aligned constant pool entry");
1439 unsigned BaseInsertOffset = UserOffset + U.getMaxDisp() - UPad;
1441 BaseInsertOffset));
1442
1443
1444
1445
1446 BaseInsertOffset -= 4;
1447
1450 << " up=" << UPad << '\n');
1451
1452
1453
1454
1455
1456 if (BaseInsertOffset + 8 >= UserBBI.postOffset()) {
1457
1458
1459
1460 BaseInsertOffset =
1461 std::max(UserBBI.postOffset() - UPad - 8,
1462 UserOffset + TII->getInstSizeInBytes(*UserMI) + 1);
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1475 ++I;
1477 for (unsigned Offset = UserOffset + TII->getInstSizeInBytes(*UserMI);
1478 I->getOpcode() != ARM::t2IT &&
1480 Offset += TII->getInstSizeInBytes(*I), I = std::next(I)) {
1481 BaseInsertOffset =
1482 std::max(BaseInsertOffset, Offset + TII->getInstSizeInBytes(*I) + 1);
1483 assert(I != UserMBB->end() && "Fell off end of block");
1484 }
1486 }
1487 unsigned EndInsertOffset = BaseInsertOffset + 4 + UPad +
1490 ++MI;
1491 unsigned CPUIndex = CPUserIndex+1;
1492 unsigned NumCPUsers = CPUsers.size();
1494 for (unsigned Offset = UserOffset + TII->getInstSizeInBytes(*UserMI);
1495 Offset < BaseInsertOffset;
1496 Offset += TII->getInstSizeInBytes(*MI), MI = std::next(MI)) {
1497 assert(MI != UserMBB->end() && "Fell off end of block");
1498 if (CPUIndex < NumCPUsers && CPUsers[CPUIndex].MI == &*MI) {
1499 CPUser &U = CPUsers[CPUIndex];
1500 if (!isOffsetInRange(Offset, EndInsertOffset, U)) {
1501
1504 }
1505
1506
1507
1508
1509 EndInsertOffset += U.CPEMI->getOperand(2).getImm();
1510 CPUIndex++;
1511 }
1512
1513
1514 if (MI->getOpcode() == ARM::t2IT)
1515 LastIT = &*MI;
1516 }
1517
1518 --MI;
1519
1520
1521 if (LastIT) {
1525 MI = LastIT;
1526 }
1527
1528
1529
1530
1531
1532
1533
1534
1535 if (STI->isTargetWindows() && isThumb && MI->getOpcode() == ARM::t2MOVTi16 &&
1538 --MI;
1539 assert(MI->getOpcode() == ARM::t2MOVi16 &&
1542 }
1543
1544
1545#ifndef NDEBUG
1548#endif
1549 NewMBB = splitBlockBeforeInstr(&*MI);
1550}
1551
1552
1553
1554
1555
1556bool ARMConstantIslands::handleConstantPoolUser(unsigned CPUserIndex,
1557 bool CloserWater) {
1558 CPUser &U = CPUsers[CPUserIndex];
1561 unsigned CPI = getCombinedIndex(CPEMI);
1563
1564 unsigned UserOffset = getUserOffset(U);
1565
1566
1567
1568 int result = findInRangeCPEntry(U, UserOffset);
1569 if (result==1) return false;
1570 else if (result==2) return true;
1571
1572
1573
1574 unsigned ID = AFI->createPICLabelUId();
1575
1576
1579 water_iterator IP;
1580 if (findAvailableWater(U, UserOffset, IP, CloserWater)) {
1583
1584
1585
1586
1587 if (NewWaterList.erase(WaterBB))
1588 NewWaterList.insert(NewIsland);
1589
1590
1592 } else {
1593
1595 createNewWater(CPUserIndex, UserOffset, NewMBB);
1596
1597
1598
1599
1600
1601
1603 IP = find(WaterList, WaterBB);
1604 if (IP != WaterList.end())
1605 NewWaterList.erase(WaterBB);
1606
1607
1608 NewWaterList.insert(NewIsland);
1609 }
1610
1611
1612
1616
1617
1618
1619
1620
1621 if (IP != WaterList.end())
1622 WaterList.erase(IP);
1623
1624
1625 MF->insert(NewMBB->getIterator(), NewIsland);
1626
1627
1628 updateForInsertedWaterBlock(NewIsland);
1629
1630
1631
1632 U.HighWaterMark = NewIsland;
1637 CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1));
1638 ++NumCPEs;
1639
1640
1641 decrementCPEReferenceCount(CPI, CPEMI);
1642
1643
1645
1646
1647 BBUtils->adjustBBSize(NewIsland, Size);
1648 BBUtils->adjustBBOffsetsAfter(&*--NewIsland->getIterator());
1649
1650
1652 if (MO.isCPI()) {
1653 MO.setIndex(ID);
1654 break;
1655 }
1656
1658 dbgs() << " Moved CPE to #" << ID << " CPI=" << CPI
1659 << format(" offset=%#x\n",
1660 BBUtils->getBBInfo()[NewIsland->getNumber()].Offset));
1661
1662 return true;
1663}
1664
1665
1666
1667void ARMConstantIslands::removeDeadCPEMI(MachineInstr *CPEMI) {
1671 BBInfoVector &BBInfo = BBUtils->getBBInfo();
1672 BBUtils->adjustBBSize(CPEBB, -Size);
1673
1674 if (CPEBB->empty()) {
1676
1677
1679 } else {
1680
1682 }
1683
1684 BBUtils->adjustBBOffsetsAfter(CPEBB);
1685
1686
1687
1689
1690}
1691
1692
1693
1694bool ARMConstantIslands::removeUnusedCPEntries() {
1695 unsigned MadeChange = false;
1696 for (std::vector &CPEs : CPEntries) {
1697 for (CPEntry &CPE : CPEs) {
1698 if (CPE.RefCount == 0 && CPE.CPEMI) {
1699 removeDeadCPEMI(CPE.CPEMI);
1700 CPE.CPEMI = nullptr;
1701 MadeChange = true;
1702 }
1703 }
1704 }
1705 return MadeChange;
1706}
1707
1708
1709
1710
1711bool ARMConstantIslands::fixupImmediateBr(ImmBranch &Br) {
1714
1715
1716 if (BBUtils->isBBInRange(MI, DestBB, Br.MaxDisp))
1717 return false;
1718
1719 if (!Br.isCond)
1720 return fixupUnconditionalBr(Br);
1721 return fixupConditionalBr(Br);
1722}
1723
1724
1725
1726
1727
1728bool
1729ARMConstantIslands::fixupUnconditionalBr(ImmBranch &Br) {
1732 if (!isThumb1)
1734
1735 if (!AFI->isLRSpilled())
1737
1738
1739 Br.MaxDisp = (1 << 21) * 2;
1740 MI->setDesc(TII->get(ARM::tBfar));
1741 BBInfoVector &BBInfo = BBUtils->getBBInfo();
1743 BBUtils->adjustBBOffsetsAfter(MBB);
1744 ++NumUBrFixed;
1745
1747
1748 return true;
1749}
1750
1751
1752
1753
1754bool
1755ARMConstantIslands::fixupConditionalBr(ImmBranch &Br) {
1758
1759
1760
1761
1762
1763
1764
1765
1768 Register CCReg = MI->getOperand(2).getReg();
1769
1770
1771
1772
1776
1777 ++NumCBrFixed;
1778 if (BMI != MI) {
1780 BMI->getOpcode() == Br.UncondBr) {
1781
1782
1783
1784
1785
1786
1787
1789 if (BBUtils->isBBInRange(MI, NewDest, Br.MaxDisp)) {
1791 dbgs() << " Invert Bcc condition and swap its destination with "
1792 << *BMI);
1794 MI->getOperand(0).setMBB(NewDest);
1795 MI->getOperand(1).setImm(CC);
1796 return true;
1797 }
1798 }
1799 }
1800
1801 if (NeedSplit) {
1802 splitBlockBeforeInstr(MI);
1803
1804
1805 int delta = TII->getInstSizeInBytes(MBB->back());
1806 BBUtils->adjustBBSize(MBB, -delta);
1808
1809
1810
1812 std::next(MBB->getIterator())->removeSuccessor(DestBB);
1813
1814
1815 }
1817
1819 << " also invert condition and change dest. to "
1821
1822
1823
1827 BBUtils->adjustBBSize(MBB, TII->getInstSizeInBytes(MBB->back()));
1832 else
1834 BBUtils->adjustBBSize(MBB, TII->getInstSizeInBytes(MBB->back()));
1836 ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr));
1837
1838
1839 BBUtils->adjustBBSize(MI->getParent(), -TII->getInstSizeInBytes(*MI));
1840 MI->eraseFromParent();
1841 BBUtils->adjustBBOffsetsAfter(MBB);
1842 return true;
1843}
1844
1845bool ARMConstantIslands::optimizeThumb2Instructions() {
1846 bool MadeChange = false;
1847
1848
1849 for (CPUser &U : CPUsers) {
1850 unsigned Opcode = U.MI->getOpcode();
1851 unsigned NewOpc = 0;
1852 unsigned Scale = 1;
1853 unsigned Bits = 0;
1854 switch (Opcode) {
1855 default: break;
1856 case ARM::t2LEApcrel:
1858 NewOpc = ARM::tLEApcrel;
1860 Scale = 4;
1861 }
1862 break;
1863 case ARM::t2LDRpci:
1865 NewOpc = ARM::tLDRpci;
1867 Scale = 4;
1868 }
1869 break;
1870 }
1871
1872 if (!NewOpc)
1873 continue;
1874
1875 unsigned UserOffset = getUserOffset(U);
1876 unsigned MaxOffs = ((1 << Bits) - 1) * Scale;
1877
1878
1879 if (.KnownAlignment)
1880 MaxOffs -= 2;
1881
1882
1883 if (isCPEntryInRange(U.MI, UserOffset, U.CPEMI, MaxOffs, false, true)) {
1885 U.MI->setDesc(TII->get(NewOpc));
1887 BBUtils->adjustBBSize(MBB, -2);
1888 BBUtils->adjustBBOffsetsAfter(MBB);
1889 ++NumT2CPShrunk;
1890 MadeChange = true;
1891 }
1892 }
1893
1894 return MadeChange;
1895}
1896
1897
1898bool ARMConstantIslands::optimizeThumb2Branches() {
1899
1900 auto TryShrinkBranch = [this](ImmBranch &Br) {
1901 unsigned Opcode = Br.MI->getOpcode();
1902 unsigned NewOpc = 0;
1903 unsigned Scale = 1;
1904 unsigned Bits = 0;
1905 switch (Opcode) {
1906 default: break;
1907 case ARM::t2B:
1908 NewOpc = ARM::tB;
1910 Scale = 2;
1911 break;
1912 case ARM::t2Bcc:
1913 NewOpc = ARM::tBcc;
1915 Scale = 2;
1916 break;
1917 }
1918 if (NewOpc) {
1919 unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale;
1921 if (BBUtils->isBBInRange(Br.MI, DestBB, MaxOffs)) {
1923 Br.MI->setDesc(TII->get(NewOpc));
1925 BBUtils->adjustBBSize(MBB, -2);
1926 BBUtils->adjustBBOffsetsAfter(MBB);
1927 ++NumT2BrShrunk;
1928 return true;
1929 }
1930 }
1931 return false;
1932 };
1933
1934 struct ImmCompare {
1936 unsigned NewOpc = 0;
1937 };
1938
1939 auto FindCmpForCBZ = [this](ImmBranch &Br, ImmCompare &ImmCmp,
1941 ImmCmp.MI = nullptr;
1942 ImmCmp.NewOpc = 0;
1943
1944
1945
1946 if (!Br.MI->killsRegister(ARM::CPSR, nullptr))
1947 return false;
1948
1950 unsigned NewOpc = 0;
1953 NewOpc = ARM::tCBZ;
1955 NewOpc = ARM::tCBNZ;
1956 else
1957 return false;
1958
1959
1960
1961 unsigned BrOffset = BBUtils->getOffsetOf(Br.MI) + 4 - 2;
1962 BBInfoVector &BBInfo = BBUtils->getBBInfo();
1963 unsigned DestOffset = BBInfo[DestBB->getNumber()].Offset;
1964 if (BrOffset >= DestOffset || (DestOffset - BrOffset) > 126)
1965 return false;
1966
1967
1968 auto *TRI = STI->getRegisterInfo();
1970 if (!CmpMI || CmpMI->getOpcode() != ARM::tCMPi8)
1971 return false;
1972
1973 ImmCmp.MI = CmpMI;
1974 ImmCmp.NewOpc = NewOpc;
1975 return true;
1976 };
1977
1978 auto TryConvertToLE = [this](ImmBranch &Br, ImmCompare &Cmp) {
1979 if (Br.MI->getOpcode() != ARM::t2Bcc || !STI->hasLOB() ||
1980 STI->hasMinSize())
1981 return false;
1982
1985 if (BBUtils->getOffsetOf(MBB) < BBUtils->getOffsetOf(DestBB) ||
1986 !BBUtils->isBBInRange(Br.MI, DestBB, 4094))
1987 return false;
1988
1990 return false;
1991
1992
1993
1994 Cmp.NewOpc = Cmp.NewOpc == ARM::tCBZ ? ARM::tCBNZ : ARM::tCBZ;
1995
1997 TII->get(ARM::t2LE));
1998
1999 MIB.add(Br.MI->getOperand(0));
2001 Br.MI = MIB;
2002 ++NumLEInserted;
2003 return true;
2004 };
2005
2006 bool MadeChange = false;
2007
2008
2009
2010
2011
2012
2013 for (ImmBranch &Br : reverse(ImmBranches)) {
2019
2020 ImmCompare Cmp;
2021 if (FindCmpForCBZ(Br, Cmp, ExitBB) && TryConvertToLE(Br, Cmp)) {
2022 DestBB = ExitBB;
2023 MadeChange = true;
2024 } else {
2025 FindCmpForCBZ(Br, Cmp, DestBB);
2026 MadeChange |= TryShrinkBranch(Br);
2027 }
2028
2029 unsigned Opcode = Br.MI->getOpcode();
2030 if ((Opcode != ARM::tBcc && Opcode != ARM::t2LE) || .NewOpc)
2031 continue;
2032
2034
2035
2036
2037 auto *TRI = STI->getRegisterInfo();
2039 bool RegKilled = false;
2040 do {
2041 --KillMI;
2042 if (KillMI->killsRegister(Reg, TRI)) {
2043 KillMI->clearRegisterKills(Reg, TRI);
2044 RegKilled = true;
2045 break;
2046 }
2047 } while (KillMI != Cmp.MI);
2048
2049
2050 LLVM_DEBUG(dbgs() << "Fold: " << *Cmp.MI << " and: " << *Br.MI);
2052 BuildMI(*MBB, Br.MI, Br.MI->getDebugLoc(), TII->get(Cmp.NewOpc))
2055 .addMBB(DestBB, Br.MI->getOperand(0).getTargetFlags());
2056
2057 Cmp.MI->eraseFromParent();
2058
2059 if (Br.MI->getOpcode() == ARM::tBcc) {
2060 Br.MI->eraseFromParent();
2061 Br.MI = NewBR;
2062 BBUtils->adjustBBSize(MBB, -2);
2064
2065
2066
2067
2068
2072 }
2073 BBUtils->adjustBBOffsetsAfter(MBB);
2074 ++NumCBZ;
2075 MadeChange = true;
2076 }
2077
2078 return MadeChange;
2079}
2080
2082 unsigned BaseReg) {
2083 if (I.getOpcode() != ARM::t2ADDrs)
2084 return false;
2085
2086 if (I.getOperand(0).getReg() != EntryReg)
2087 return false;
2088
2089 if (I.getOperand(1).getReg() != BaseReg)
2090 return false;
2091
2092
2093 return true;
2094}
2095
2096
2097
2098
2099
2100
2101
2102bool ARMConstantIslands::preserveBaseRegister(MachineInstr *JumpMI,
2104 unsigned &DeadSize,
2105 bool &CanDeleteLEA,
2106 bool &BaseRegKill) {
2108 return false;
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2128
2129 CanDeleteLEA = true;
2130 BaseRegKill = false;
2133 for (++I; &*I != JumpMI; ++I) {
2135 RemovableAdd = &*I;
2136 break;
2137 }
2138
2140 if (!MO.isReg() || !MO.getReg())
2141 continue;
2142 if (MO.isDef() && MO.getReg() == BaseReg)
2143 return false;
2144 if (MO.isUse() && MO.getReg() == BaseReg) {
2145 BaseRegKill = BaseRegKill || MO.isKill();
2146 CanDeleteLEA = false;
2147 }
2148 }
2149 }
2150
2151 if (!RemovableAdd)
2152 return true;
2153
2154
2155
2156 for (++I; &*I != JumpMI; ++I) {
2158 if (!MO.isReg() || !MO.getReg())
2159 continue;
2160 if (MO.isDef() && MO.getReg() == BaseReg)
2161 return false;
2162 if (MO.isUse() && MO.getReg() == EntryReg)
2163 RemovableAdd = nullptr;
2164 }
2165 }
2166
2167 if (RemovableAdd) {
2169 DeadSize += isThumb2 ? 4 : 2;
2170 } else if (BaseReg == EntryReg) {
2171
2172
2173 return false;
2174 }
2175
2176
2177
2178
2179 return true;
2180}
2181
2182
2183
2184
2185
2190
2192}
2193
2196 unsigned &DeadSize) {
2197
2198
2199
2202
2203
2205 for (++I; &*I != JumpMI; ++I) {
2206 if (I->getOpcode() == ARM::t2ADDrs && I->getOperand(0).getReg() == EntryReg)
2207 RemovableAdd = &*I;
2208 }
2209
2210 if (!RemovableAdd)
2211 return;
2212
2213
2215 for (++J; &*J != JumpMI; ++J) {
2217 if (!MO.isReg() || !MO.getReg())
2218 continue;
2219 if (MO.isDef() && MO.getReg() == EntryReg)
2220 return;
2221 if (MO.isUse() && MO.getReg() == EntryReg)
2222 return;
2223 }
2224 }
2225
2226 LLVM_DEBUG(dbgs() << "Removing Dead Add: " << *RemovableAdd);
2228 DeadSize += 4;
2229}
2230
2231
2232
2233bool ARMConstantIslands::optimizeThumb2JumpTables() {
2234 bool MadeChange = false;
2235
2236
2237
2239 if (!MJTI) return false;
2240
2241 const std::vector &JT = MJTI->getJumpTables();
2245 unsigned JTOpIdx = NumOps - (MI->isPredicable() ? 2 : 1);
2247 unsigned JTI = JTOP.getIndex();
2249
2250 bool ByteOk = true;
2251 bool HalfWordOk = true;
2252 unsigned JTOffset = BBUtils->getOffsetOf(MI) + 4;
2253 const std::vector<MachineBasicBlock*> &JTBBs = JT[JTI].MBBs;
2254 BBInfoVector &BBInfo = BBUtils->getBBInfo();
2256 unsigned DstOffset = BBInfo[MBB->getNumber()].Offset;
2257
2258
2259 if (ByteOk && (DstOffset - JTOffset) > ((1<<8)-1)*2)
2260 ByteOk = false;
2261 unsigned TBHLimit = ((1<<16)-1)*2;
2262 if (HalfWordOk && (DstOffset - JTOffset) > TBHLimit)
2263 HalfWordOk = false;
2264 if (!ByteOk && !HalfWordOk)
2265 break;
2266 }
2267
2268 if (!ByteOk && !HalfWordOk)
2269 continue;
2270
2271 CPUser &User = CPUsers[JumpTableUserIndices[JTI]];
2273 if (->getOperand(0).isKill())
2274 continue;
2275
2276 unsigned DeadSize = 0;
2277 bool CanDeleteLEA = false;
2278 bool BaseRegKill = false;
2279
2280 unsigned IdxReg = ~0U;
2281 bool IdxRegKill = true;
2282 if (isThumb2) {
2283 IdxReg = MI->getOperand(1).getReg();
2284 IdxRegKill = MI->getOperand(1).isKill();
2285
2286 bool PreservedBaseReg =
2287 preserveBaseRegister(MI, User.MI, DeadSize, CanDeleteLEA, BaseRegKill);
2289 continue;
2290 } else {
2291
2292
2293
2294
2296
2299 if (Shift == UserMBB->begin())
2300 continue;
2301
2303 if (Shift->getOpcode() != ARM::tLSLri ||
2304 Shift->getOperand(3).getImm() != 2 ||
2305 !Shift->getOperand(2).isKill())
2306 continue;
2307 IdxReg = Shift->getOperand(2).getReg();
2308 Register ShiftedIdxReg = Shift->getOperand(0).getReg();
2309
2310
2311
2312
2314 continue;
2315
2317 if (Load->getOpcode() != ARM::tLDRr)
2318 continue;
2319 if (Load->getOperand(1).getReg() != BaseReg ||
2320 Load->getOperand(2).getReg() != ShiftedIdxReg ||
2321 ->getOperand(2).isKill())
2322 continue;
2323
2324
2325 auto *TRI = STI->getRegisterInfo();
2326
2327
2328
2329
2330
2331
2333 continue;
2334
2335 if (isPositionIndependentOrROPI) {
2337 if (Add->getOpcode() != ARM::tADDrr ||
2338 Add->getOperand(2).getReg() != BaseReg ||
2339 Add->getOperand(3).getReg() != Load->getOperand(0).getReg() ||
2340 ->getOperand(3).isKill())
2341 continue;
2342 if (Add->getOperand(0).getReg() != MI->getOperand(0).getReg())
2343 continue;
2345
2346 continue;
2347 Add->eraseFromParent();
2348 DeadSize += 2;
2349 } else {
2350 if (Load->getOperand(0).getReg() != MI->getOperand(0).getReg())
2351 continue;
2353
2354 continue;
2355 }
2356
2357
2358 CanDeleteLEA = true;
2359 Shift->eraseFromParent();
2360 Load->eraseFromParent();
2361 DeadSize += 4;
2362 }
2363
2366 unsigned Opc = ByteOk ? ARM::t2TBB_JT : ARM::t2TBH_JT;
2367 if (!isThumb2)
2368 Opc = ByteOk ? ARM::tTBB_JT : ARM::tTBH_JT;
2369
2379
2380 unsigned JTOpc = ByteOk ? ARM::JUMPTABLE_TBB : ARM::JUMPTABLE_TBH;
2382
2386
2387 if (CanDeleteLEA) {
2388 if (isThumb2)
2390
2391 User.MI->eraseFromParent();
2392 DeadSize += isThumb2 ? 4 : 2;
2393
2394
2395
2396 User.MI = NewJTMI;
2397 User.MaxDisp = 4;
2398 User.NegOk = false;
2399 User.IsSoImm = false;
2400 User.KnownAlignment = false;
2401 } else {
2402
2403
2404 int CPEntryIdx = JumpTableEntryIndices[JTI];
2405 auto &CPEs = CPEntries[CPEntryIdx];
2407 find_if(CPEs, [&](CPEntry &E) { return E.CPEMI == User.CPEMI; });
2408 ++Entry->RefCount;
2409 CPUsers.emplace_back(CPUser(NewJTMI, User.CPEMI, 4, false, false));
2410 }
2411 }
2412
2413 unsigned NewSize = TII->getInstSizeInBytes(*NewJTMI);
2414 unsigned OrigSize = TII->getInstSizeInBytes(*MI);
2415 MI->eraseFromParent();
2416
2417 int Delta = OrigSize - NewSize + DeadSize;
2419 BBUtils->adjustBBOffsetsAfter(MBB);
2420
2421 ++NumTBs;
2422 MadeChange = true;
2423 }
2424
2425 return MadeChange;
2426}
2427
2428
2429
2430bool ARMConstantIslands::reorderThumb2JumpTables() {
2431 bool MadeChange = false;
2432
2434 if (!MJTI) return false;
2435
2436 const std::vector &JT = MJTI->getJumpTables();
2440 unsigned JTOpIdx = NumOps - (MI->isPredicable() ? 2 : 1);
2442 unsigned JTI = JTOP.getIndex();
2444
2445
2446
2447
2448 int JTNumber = MI->getParent()->getNumber();
2449 const std::vector<MachineBasicBlock*> &JTBBs = JT[JTI].MBBs;
2452
2453 if (DTNumber < JTNumber) {
2454
2455
2457 adjustJTTargetBlockForward(JTI, MBB, MI->getParent());
2458 if (NewBB)
2460 MadeChange = true;
2461 }
2462 }
2463 }
2464
2465 return MadeChange;
2466}
2467
2468MachineBasicBlock *ARMConstantIslands::adjustJTTargetBlockForward(
2470
2471
2472
2473
2480
2481
2483
2484
2485
2486
2487 if ( && Cond.empty() && BB != &MF->front() &&
2490 OldPrior->updateTerminator(BB);
2491 BB->updateTerminator(OldNext != MF->end() ? &*OldNext : nullptr);
2492
2493 MF->RenumberBlocks();
2495 ++NumJTMoved;
2496 return nullptr;
2497 }
2498
2499
2501 MF->CreateMachineBasicBlock(JTBB->getBasicBlock());
2503 MF->insert(MBBI, NewBB);
2504
2505
2508
2509
2510
2511
2512 if (isThumb2)
2516 else
2520
2521
2522 MF->RenumberBlocks(NewBB);
2524
2525
2528
2529 ++NumJTInserted;
2530 return NewBB;
2531}
2532
2533
2534
2536 return new ARMConstantIslands();
2537}
2538
2540 false, false)
unsigned const MachineRegisterInfo * MRI
static bool isThumb(const MCSubtargetInfo &STI)
static cl::opt< unsigned > CPMaxIteration("arm-constant-island-max-iteration", cl::Hidden, cl::init(30), cl::desc("The max number of iteration for converge"))
static bool isSimpleIndexCalc(MachineInstr &I, unsigned EntryReg, unsigned BaseReg)
static bool jumpTableFollowsTB(MachineInstr *JTMI, MachineInstr *CPEMI)
Returns whether CPEMI is the first instruction in the block immediately following JTMI (assumed to be...
static bool CompareMBBNumbers(const MachineBasicBlock *LHS, const MachineBasicBlock *RHS)
CompareMBBNumbers - Little predicate function to sort the WaterList by MBB ID.
static unsigned getUnconditionalBrDisp(int Opc)
getUnconditionalBrDisp - Returns the maximum displacement that can fit in the specific unconditional ...
static void RemoveDeadAddBetweenLEAAndJT(MachineInstr *LEAMI, MachineInstr *JumpMI, unsigned &DeadSize)
static bool isAlwaysIndirectTarget(const MachineBasicBlock &MBB)
static bool AlignBlocks(MachineFunction *MF, const ARMSubtarget *STI)
static cl::opt< bool > SynthesizeThumb1TBB("arm-synthesize-thumb-1-tbb", cl::Hidden, cl::init(true), cl::desc("Use compressed jump tables in Thumb-1 by synthesizing an " "equivalent to the TBB/TBH instructions"))
static cl::opt< bool > AdjustJumpTableBlocks("arm-adjust-jump-tables", cl::Hidden, cl::init(true), cl::desc("Adjust basic block layout to better use TB[BH]"))
#define ARM_CP_ISLANDS_OPT_NAME
static bool BBIsJumpedOver(MachineBasicBlock *MBB)
BBIsJumpedOver - Return true of the specified basic block's only predecessor unconditionally branches...
MachineBasicBlock MachineBasicBlock::iterator MBBI
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.
This file defines the DenseMap class.
const HexagonInstrInfo * TII
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
This file declares the MachineConstantPool class which is an abstract constant pool to keep track of ...
unsigned const TargetRegisterInfo * TRI
static bool BBHasFallthrough(MachineBasicBlock *MBB)
BBHasFallthrough - Return true if the specified basic block can fallthrough into the block immediatel...
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
ARMFunctionInfo - This class is derived from MachineFunctionInfo and contains private ARM-specific in...
bool branchTargetEnforcement() const
const ARMTargetLowering * getTargetLowering() const override
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
A parsed version of the target data layout string in and methods for querying it.
std::enable_if_t< GraphHasNodeNumbers< T * >, void > updateBlockNumbers()
Update dominator tree after renumbering blocks.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
FunctionPass class - This class is used to implement most global optimizations.
bool hasOptSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify) const override
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Describe properties that are true of each instruction in the target description file.
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
unsigned getSize() const
Return the number of bytes in the encoding of this instruction, or zero if the encoding size cannot b...
unsigned pred_size() const
bool isEHPad() const
Returns true if the block is a landing pad.
void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New)
Replace successor OLD with NEW and update probability info.
MachineBasicBlock * getFallThrough(bool JumpToFallThrough=true)
Return the fallthrough block if the block can implicitly transfer control to the block after it by fa...
void transferSuccessors(MachineBasicBlock *FromMBB)
Transfers all the successors from MBB to this machine basic block (i.e., copies all the successors Fr...
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
iterator_range< livein_iterator > liveins() const
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
void push_back(MachineInstr *MI)
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
void updateTerminator(MachineBasicBlock *PreviousLayoutSuccessor)
Update the terminator instructions in block to account for changes to block layout which may have bee...
bool canFallThrough()
Return true if the block can implicitly transfer control to the block after it by falling off the end...
succ_iterator succ_begin()
unsigned succ_size() const
bool hasAddressTaken() const
Test whether this block is used as something other than the target of a terminator,...
void setAlignment(Align A)
Set alignment of the basic block.
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
pred_iterator pred_begin()
iterator getLastNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the last non-debug instruction in the basic block, or end().
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator_range< iterator > terminators()
reverse_iterator rbegin()
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
Align getAlignment() const
Return alignment of the basic block.
MachineInstrBundleIterator< MachineInstr > iterator
void moveAfter(MachineBasicBlock *NewBefore)
The MachineConstantPool class keeps track of constants referenced by a function which must be spilled...
Analysis pass which computes a MachineDominatorTree.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
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.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
virtual MachineFunctionProperties getRequiredProperties() const
Properties which a MachineFunction may have at a given point in time.
MachineFunctionProperties & set(Property P)
Function & getFunction()
Return the LLVM function that this machine code represents.
MachineConstantPool * getConstantPool()
getConstantPool - Return the constant pool object for the current function.
void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)
RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them.
const MachineBasicBlock & front() const
const TargetMachine & getTarget() const
getTarget - Return the target machine this machine code is compiled with
BasicBlockListType::const_iterator const_iterator
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
const MachineInstrBuilder & add(const MachineOperand &MO) const
const MachineInstrBuilder & addConstantPoolIndex(unsigned Idx, int Offset=0, unsigned TargetFlags=0) const
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
const MachineInstrBuilder & addJumpTableIndex(unsigned Idx, unsigned TargetFlags=0) const
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const
reverse_iterator getReverse() const
Get a reverse iterator to the same node.
Representation of each machine instruction.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
const MachineBasicBlock * getParent() const
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
void setDesc(const MCInstrDesc &TID)
Replace the instruction descriptor (thus opcode) of the current instruction with a new one.
iterator_range< mop_iterator > operands()
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
const MachineOperand & getOperand(unsigned i) const
bool ReplaceMBBInJumpTable(unsigned Idx, MachineBasicBlock *Old, MachineBasicBlock *New)
ReplaceMBBInJumpTable - If Old is a target of the jump tables, update the jump table to branch to New...
@ EK_Inline
EK_Inline - Jump table entries are emitted inline at their point of use.
JTEntryKind getEntryKind() const
const std::vector< MachineJumpTableEntry > & getJumpTables() const
MachineOperand class - Representation of each machine instruction operand.
MachineBasicBlock * getMBB() const
bool isCPI() const
isCPI - Tests if this is a MO_ConstantPoolIndex operand.
void setReg(Register Reg)
Change the register this operand corresponds to.
void setIsKill(bool Val=true)
void setMBB(MachineBasicBlock *MBB)
Register getReg() const
getReg - Returns the register number.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Wrapper class representing virtual and physical registers.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
CodeGenOptLevel getOptLevel() const
Returns the optimization level: None, Less, Default, or Aggressive.
Value * getOperand(unsigned i) const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
static CondCodes getOppositeCondition(CondCodes CC)
@ MO_OPTION_MASK
MO_OPTION_MASK - Most flags are mutually exclusive; this mask selects just that part of the flag set.
@ MO_LO16
MO_LO16 - On a symbol operand, this represents a relocation containing lower 16 bit of the address.
@ MO_HI16
MO_HI16 - On a symbol operand, this represents a relocation containing higher 16 bit of the address.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Reg
All possible values of the reg field in the ModR/M byte.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
MachineInstr * findCMPToFoldIntoCBZ(MachineInstr *Br, const TargetRegisterInfo *TRI)
Search backwards from a tBcc to find a tCMPi8 against 0, meaning we can convert them to a tCBZ or tCB...
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
static bool isARMLowRegister(MCRegister Reg)
isARMLowRegister - Returns true if the register is a low register (r0-r7).
bool isAligned(Align Lhs, uint64_t SizeInBytes)
Checks that SizeInBytes is a multiple of the alignment.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
bool registerDefinedBetween(unsigned Reg, MachineBasicBlock::iterator From, MachineBasicBlock::iterator To, const TargetRegisterInfo *TRI)
Return true if Reg is defd between From and To.
static std::array< MachineOperand, 2 > predOps(ARMCC::CondCodes Pred, unsigned PredReg=0)
Get the operands corresponding to the given Pred value.
ARMCC::CondCodes getITInstrPredicate(const MachineInstr &MI, Register &PredReg)
getITInstrPredicate - Valid only in Thumb2 mode.
auto reverse(ContainerTy &&C)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
static bool isLoopStart(const MachineInstr &MI)
bool is_sorted(R &&Range, Compare C)
Wrapper function around std::is_sorted to check if elements in a range R are sorted with respect to a...
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
uint64_t offsetToAlignment(uint64_t Value, Align Alignment)
Returns the offset to the next integer (mod 2**64) that is greater than or equal to Value and is a mu...
unsigned getRegState(const MachineOperand &RegOp)
Get all register state flags from machine operand RegOp.
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
unsigned getKillRegState(bool B)
ARMCC::CondCodes getInstrPredicate(const MachineInstr &MI, Register &PredReg)
getInstrPredicate - If instruction is predicated, returns its predicate condition,...
FunctionPass * createARMConstantIslandPass()
createARMConstantIslandPass - returns an instance of the constpool island pass.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
unsigned UnknownPadding(Align Alignment, unsigned KnownBits)
UnknownPadding - Return the worst case padding that could result from unknown offset bits.
APFloat neg(APFloat X)
Returns the negated value of the argument.
unsigned Log2(Align A)
Returns the log2 of the alignment.
static bool isSpeculationBarrierEndBBOpcode(int Opc)
IterT prev_nodbg(IterT It, IterT Begin, bool SkipPseudoOp=true)
Decrement It, then continue decrementing it while it points to a debug instruction.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
This struct is a compact representation of a valid (non-zero power of two) alignment.
uint64_t value() const
This is a hole in the type system and should not be abused.
BasicBlockInfo - Information about the offset and size of a single basic block.
unsigned internalKnownBits() const
Compute the number of known offset bits internally to this block.
unsigned postOffset(Align Alignment=Align(1)) const
Compute the offset immediately following this block.
unsigned Offset
Offset - Distance from the beginning of the function to the beginning of this basic block.
Pair of physical register and lane mask.
MachineJumpTableEntry - One jump table in the jump table info.