xref: /freebsd/contrib/llvm-project/llvm/lib/Target/ARM/ARMConstantIslandPass.cpp (revision a4e5e0106ac7145f56eb39a691e302cabb4635be)
1 //===- ARMConstantIslandPass.cpp - ARM constant islands -------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file contains a pass that splits the constant pool up into 'islands'
10 // which are scattered through-out the function.  This is required due to the
11 // limited pc-relative displacements that ARM has.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "ARM.h"
16 #include "ARMBaseInstrInfo.h"
17 #include "ARMBasicBlockInfo.h"
18 #include "ARMMachineFunctionInfo.h"
19 #include "ARMSubtarget.h"
20 #include "MCTargetDesc/ARMBaseInfo.h"
21 #include "MVETailPredUtils.h"
22 #include "Thumb2InstrInfo.h"
23 #include "Utils/ARMBaseInfo.h"
24 #include "llvm/ADT/DenseMap.h"
25 #include "llvm/ADT/STLExtras.h"
26 #include "llvm/ADT/SmallSet.h"
27 #include "llvm/ADT/SmallVector.h"
28 #include "llvm/ADT/Statistic.h"
29 #include "llvm/ADT/StringRef.h"
30 #include "llvm/CodeGen/LivePhysRegs.h"
31 #include "llvm/CodeGen/MachineBasicBlock.h"
32 #include "llvm/CodeGen/MachineConstantPool.h"
33 #include "llvm/CodeGen/MachineDominators.h"
34 #include "llvm/CodeGen/MachineFunction.h"
35 #include "llvm/CodeGen/MachineFunctionPass.h"
36 #include "llvm/CodeGen/MachineInstr.h"
37 #include "llvm/CodeGen/MachineJumpTableInfo.h"
38 #include "llvm/CodeGen/MachineOperand.h"
39 #include "llvm/CodeGen/MachineRegisterInfo.h"
40 #include "llvm/Config/llvm-config.h"
41 #include "llvm/IR/DataLayout.h"
42 #include "llvm/IR/DebugLoc.h"
43 #include "llvm/MC/MCInstrDesc.h"
44 #include "llvm/Pass.h"
45 #include "llvm/Support/CommandLine.h"
46 #include "llvm/Support/Compiler.h"
47 #include "llvm/Support/Debug.h"
48 #include "llvm/Support/ErrorHandling.h"
49 #include "llvm/Support/Format.h"
50 #include "llvm/Support/MathExtras.h"
51 #include "llvm/Support/raw_ostream.h"
52 #include <algorithm>
53 #include <cassert>
54 #include <cstdint>
55 #include <iterator>
56 #include <utility>
57 #include <vector>
58 
59 using namespace llvm;
60 
61 #define DEBUG_TYPE "arm-cp-islands"
62 
63 #define ARM_CP_ISLANDS_OPT_NAME \
64   "ARM constant island placement and branch shortening pass"
65 STATISTIC(NumCPEs,       "Number of constpool entries");
66 STATISTIC(NumSplit,      "Number of uncond branches inserted");
67 STATISTIC(NumCBrFixed,   "Number of cond branches fixed");
68 STATISTIC(NumUBrFixed,   "Number of uncond branches fixed");
69 STATISTIC(NumTBs,        "Number of table branches generated");
70 STATISTIC(NumT2CPShrunk, "Number of Thumb2 constantpool instructions shrunk");
71 STATISTIC(NumT2BrShrunk, "Number of Thumb2 immediate branches shrunk");
72 STATISTIC(NumCBZ,        "Number of CBZ / CBNZ formed");
73 STATISTIC(NumJTMoved,    "Number of jump table destination blocks moved");
74 STATISTIC(NumJTInserted, "Number of jump table intermediate blocks inserted");
75 STATISTIC(NumLEInserted, "Number of LE backwards branches inserted");
76 
77 static cl::opt<bool>
78 AdjustJumpTableBlocks("arm-adjust-jump-tables", cl::Hidden, cl::init(true),
79           cl::desc("Adjust basic block layout to better use TB[BH]"));
80 
81 static cl::opt<unsigned>
82 CPMaxIteration("arm-constant-island-max-iteration", cl::Hidden, cl::init(30),
83           cl::desc("The max number of iteration for converge"));
84 
85 static cl::opt<bool> SynthesizeThumb1TBB(
86     "arm-synthesize-thumb-1-tbb", cl::Hidden, cl::init(true),
87     cl::desc("Use compressed jump tables in Thumb-1 by synthesizing an "
88              "equivalent to the TBB/TBH instructions"));
89 
90 namespace {
91 
92   /// ARMConstantIslands - Due to limited PC-relative displacements, ARM
93   /// requires constant pool entries to be scattered among the instructions
94   /// inside a function.  To do this, it completely ignores the normal LLVM
95   /// constant pool; instead, it places constants wherever it feels like with
96   /// special instructions.
97   ///
98   /// The terminology used in this pass includes:
99   ///   Islands - Clumps of constants placed in the function.
100   ///   Water   - Potential places where an island could be formed.
101   ///   CPE     - A constant pool entry that has been placed somewhere, which
102   ///             tracks a list of users.
103   class ARMConstantIslands : public MachineFunctionPass {
104     std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr;
105 
106     /// WaterList - A sorted list of basic blocks where islands could be placed
107     /// (i.e. blocks that don't fall through to the following block, due
108     /// to a return, unreachable, or unconditional branch).
109     std::vector<MachineBasicBlock*> WaterList;
110 
111     /// NewWaterList - The subset of WaterList that was created since the
112     /// previous iteration by inserting unconditional branches.
113     SmallSet<MachineBasicBlock*, 4> NewWaterList;
114 
115     using water_iterator = std::vector<MachineBasicBlock *>::iterator;
116 
117     /// CPUser - One user of a constant pool, keeping the machine instruction
118     /// pointer, the constant pool being referenced, and the max displacement
119     /// allowed from the instruction to the CP.  The HighWaterMark records the
120     /// highest basic block where a new CPEntry can be placed.  To ensure this
121     /// pass terminates, the CP entries are initially placed at the end of the
122     /// function and then move monotonically to lower addresses.  The
123     /// exception to this rule is when the current CP entry for a particular
124     /// CPUser is out of range, but there is another CP entry for the same
125     /// constant value in range.  We want to use the existing in-range CP
126     /// entry, but if it later moves out of range, the search for new water
127     /// should resume where it left off.  The HighWaterMark is used to record
128     /// that point.
129     struct CPUser {
130       MachineInstr *MI;
131       MachineInstr *CPEMI;
132       MachineBasicBlock *HighWaterMark;
133       unsigned MaxDisp;
134       bool NegOk;
135       bool IsSoImm;
136       bool KnownAlignment = false;
137 
138       CPUser(MachineInstr *mi, MachineInstr *cpemi, unsigned maxdisp,
139              bool neg, bool soimm)
140         : MI(mi), CPEMI(cpemi), MaxDisp(maxdisp), NegOk(neg), IsSoImm(soimm) {
141         HighWaterMark = CPEMI->getParent();
142       }
143 
144       /// getMaxDisp - Returns the maximum displacement supported by MI.
145       /// Correct for unknown alignment.
146       /// Conservatively subtract 2 bytes to handle weird alignment effects.
147       unsigned getMaxDisp() const {
148         return (KnownAlignment ? MaxDisp : MaxDisp - 2) - 2;
149       }
150     };
151 
152     /// CPUsers - Keep track of all of the machine instructions that use various
153     /// constant pools and their max displacement.
154     std::vector<CPUser> CPUsers;
155 
156     /// CPEntry - One per constant pool entry, keeping the machine instruction
157     /// pointer, the constpool index, and the number of CPUser's which
158     /// reference this entry.
159     struct CPEntry {
160       MachineInstr *CPEMI;
161       unsigned CPI;
162       unsigned RefCount;
163 
164       CPEntry(MachineInstr *cpemi, unsigned cpi, unsigned rc = 0)
165         : CPEMI(cpemi), CPI(cpi), RefCount(rc) {}
166     };
167 
168     /// CPEntries - Keep track of all of the constant pool entry machine
169     /// instructions. For each original constpool index (i.e. those that existed
170     /// upon entry to this pass), it keeps a vector of entries.  Original
171     /// elements are cloned as we go along; the clones are put in the vector of
172     /// the original element, but have distinct CPIs.
173     ///
174     /// The first half of CPEntries contains generic constants, the second half
175     /// contains jump tables. Use getCombinedIndex on a generic CPEMI to look up
176     /// which vector it will be in here.
177     std::vector<std::vector<CPEntry>> CPEntries;
178 
179     /// Maps a JT index to the offset in CPEntries containing copies of that
180     /// table. The equivalent map for a CONSTPOOL_ENTRY is the identity.
181     DenseMap<int, int> JumpTableEntryIndices;
182 
183     /// Maps a JT index to the LEA that actually uses the index to calculate its
184     /// base address.
185     DenseMap<int, int> JumpTableUserIndices;
186 
187     // Maps a MachineBasicBlock to the number of jump tables entries.
188     DenseMap<const MachineBasicBlock *, int> BlockJumpTableRefCount;
189 
190     /// ImmBranch - One per immediate branch, keeping the machine instruction
191     /// pointer, conditional or unconditional, the max displacement,
192     /// and (if isCond is true) the corresponding unconditional branch
193     /// opcode.
194     struct ImmBranch {
195       MachineInstr *MI;
196       unsigned MaxDisp : 31;
197       bool isCond : 1;
198       unsigned UncondBr;
199 
200       ImmBranch(MachineInstr *mi, unsigned maxdisp, bool cond, unsigned ubr)
201         : MI(mi), MaxDisp(maxdisp), isCond(cond), UncondBr(ubr) {}
202     };
203 
204     /// ImmBranches - Keep track of all the immediate branch instructions.
205     std::vector<ImmBranch> ImmBranches;
206 
207     /// PushPopMIs - Keep track of all the Thumb push / pop instructions.
208     SmallVector<MachineInstr*, 4> PushPopMIs;
209 
210     /// T2JumpTables - Keep track of all the Thumb2 jumptable instructions.
211     SmallVector<MachineInstr*, 4> T2JumpTables;
212 
213     MachineFunction *MF;
214     MachineConstantPool *MCP;
215     const ARMBaseInstrInfo *TII;
216     const ARMSubtarget *STI;
217     ARMFunctionInfo *AFI;
218     MachineDominatorTree *DT = nullptr;
219     bool isThumb;
220     bool isThumb1;
221     bool isThumb2;
222     bool isPositionIndependentOrROPI;
223 
224   public:
225     static char ID;
226 
227     ARMConstantIslands() : MachineFunctionPass(ID) {}
228 
229     bool runOnMachineFunction(MachineFunction &MF) override;
230 
231     void getAnalysisUsage(AnalysisUsage &AU) const override {
232       AU.addRequired<MachineDominatorTree>();
233       MachineFunctionPass::getAnalysisUsage(AU);
234     }
235 
236     MachineFunctionProperties getRequiredProperties() const override {
237       return MachineFunctionProperties().set(
238           MachineFunctionProperties::Property::NoVRegs);
239     }
240 
241     StringRef getPassName() const override {
242       return ARM_CP_ISLANDS_OPT_NAME;
243     }
244 
245   private:
246     void doInitialConstPlacement(std::vector<MachineInstr *> &CPEMIs);
247     void doInitialJumpTablePlacement(std::vector<MachineInstr *> &CPEMIs);
248     bool BBHasFallthrough(MachineBasicBlock *MBB);
249     CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI);
250     Align getCPEAlign(const MachineInstr *CPEMI);
251     void scanFunctionJumpTables();
252     void initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs);
253     MachineBasicBlock *splitBlockBeforeInstr(MachineInstr *MI);
254     void updateForInsertedWaterBlock(MachineBasicBlock *NewBB);
255     bool decrementCPEReferenceCount(unsigned CPI, MachineInstr* CPEMI);
256     unsigned getCombinedIndex(const MachineInstr *CPEMI);
257     int findInRangeCPEntry(CPUser& U, unsigned UserOffset);
258     bool findAvailableWater(CPUser&U, unsigned UserOffset,
259                             water_iterator &WaterIter, bool CloserWater);
260     void createNewWater(unsigned CPUserIndex, unsigned UserOffset,
261                         MachineBasicBlock *&NewMBB);
262     bool handleConstantPoolUser(unsigned CPUserIndex, bool CloserWater);
263     void removeDeadCPEMI(MachineInstr *CPEMI);
264     bool removeUnusedCPEntries();
265     bool isCPEntryInRange(MachineInstr *MI, unsigned UserOffset,
266                           MachineInstr *CPEMI, unsigned Disp, bool NegOk,
267                           bool DoDump = false);
268     bool isWaterInRange(unsigned UserOffset, MachineBasicBlock *Water,
269                         CPUser &U, unsigned &Growth);
270     bool fixupImmediateBr(ImmBranch &Br);
271     bool fixupConditionalBr(ImmBranch &Br);
272     bool fixupUnconditionalBr(ImmBranch &Br);
273     bool optimizeThumb2Instructions();
274     bool optimizeThumb2Branches();
275     bool reorderThumb2JumpTables();
276     bool preserveBaseRegister(MachineInstr *JumpMI, MachineInstr *LEAMI,
277                               unsigned &DeadSize, bool &CanDeleteLEA,
278                               bool &BaseRegKill);
279     bool optimizeThumb2JumpTables();
280     MachineBasicBlock *adjustJTTargetBlockForward(unsigned JTI,
281                                                   MachineBasicBlock *BB,
282                                                   MachineBasicBlock *JTBB);
283 
284     unsigned getUserOffset(CPUser&) const;
285     void dumpBBs();
286     void verify();
287 
288     bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset,
289                          unsigned Disp, bool NegativeOK, bool IsSoImm = false);
290     bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset,
291                          const CPUser &U) {
292       return isOffsetInRange(UserOffset, TrialOffset,
293                              U.getMaxDisp(), U.NegOk, U.IsSoImm);
294     }
295   };
296 
297 } // end anonymous namespace
298 
299 char ARMConstantIslands::ID = 0;
300 
301 /// verify - check BBOffsets, BBSizes, alignment of islands
302 void ARMConstantIslands::verify() {
303 #ifndef NDEBUG
304   BBInfoVector &BBInfo = BBUtils->getBBInfo();
305   assert(is_sorted(*MF, [&BBInfo](const MachineBasicBlock &LHS,
306                                   const MachineBasicBlock &RHS) {
307     return BBInfo[LHS.getNumber()].postOffset() <
308            BBInfo[RHS.getNumber()].postOffset();
309   }));
310   LLVM_DEBUG(dbgs() << "Verifying " << CPUsers.size() << " CP users.\n");
311   for (CPUser &U : CPUsers) {
312     unsigned UserOffset = getUserOffset(U);
313     // Verify offset using the real max displacement without the safety
314     // adjustment.
315     if (isCPEntryInRange(U.MI, UserOffset, U.CPEMI, U.getMaxDisp()+2, U.NegOk,
316                          /* DoDump = */ true)) {
317       LLVM_DEBUG(dbgs() << "OK\n");
318       continue;
319     }
320     LLVM_DEBUG(dbgs() << "Out of range.\n");
321     dumpBBs();
322     LLVM_DEBUG(MF->dump());
323     llvm_unreachable("Constant pool entry out of range!");
324   }
325 #endif
326 }
327 
328 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
329 /// print block size and offset information - debugging
330 LLVM_DUMP_METHOD void ARMConstantIslands::dumpBBs() {
331   LLVM_DEBUG({
332     BBInfoVector &BBInfo = BBUtils->getBBInfo();
333     for (unsigned J = 0, E = BBInfo.size(); J !=E; ++J) {
334       const BasicBlockInfo &BBI = BBInfo[J];
335       dbgs() << format("%08x %bb.%u\t", BBI.Offset, J)
336              << " kb=" << unsigned(BBI.KnownBits)
337              << " ua=" << unsigned(BBI.Unalign) << " pa=" << Log2(BBI.PostAlign)
338              << format(" size=%#x\n", BBInfo[J].Size);
339     }
340   });
341 }
342 #endif
343 
344 // Align blocks where the previous block does not fall through. This may add
345 // extra NOP's but they will not be executed. It uses the PrefLoopAlignment as a
346 // measure of how much to align, and only runs at CodeGenOpt::Aggressive.
347 static bool AlignBlocks(MachineFunction *MF, const ARMSubtarget *STI) {
348   if (MF->getTarget().getOptLevel() != CodeGenOpt::Aggressive ||
349       MF->getFunction().hasOptSize())
350     return false;
351 
352   auto *TLI = STI->getTargetLowering();
353   const Align Alignment = TLI->getPrefLoopAlignment();
354   if (Alignment < 4)
355     return false;
356 
357   bool Changed = false;
358   bool PrevCanFallthough = true;
359   for (auto &MBB : *MF) {
360     if (!PrevCanFallthough) {
361       Changed = true;
362       MBB.setAlignment(Alignment);
363     }
364 
365     PrevCanFallthough = MBB.canFallThrough();
366 
367     // For LOB's, the ARMLowOverheadLoops pass may remove the unconditional
368     // branch later in the pipeline.
369     if (STI->hasLOB()) {
370       for (const auto &MI : reverse(MBB.terminators())) {
371         if (MI.getOpcode() == ARM::t2B &&
372             MI.getOperand(0).getMBB() == MBB.getNextNode())
373           continue;
374         if (isLoopStart(MI) || MI.getOpcode() == ARM::t2LoopEnd ||
375             MI.getOpcode() == ARM::t2LoopEndDec) {
376           PrevCanFallthough = true;
377           break;
378         }
379         // Any other terminator - nothing to do
380         break;
381       }
382     }
383   }
384 
385   return Changed;
386 }
387 
388 bool ARMConstantIslands::runOnMachineFunction(MachineFunction &mf) {
389   MF = &mf;
390   MCP = mf.getConstantPool();
391   BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(mf));
392 
393   LLVM_DEBUG(dbgs() << "***** ARMConstantIslands: "
394                     << MCP->getConstants().size() << " CP entries, aligned to "
395                     << MCP->getConstantPoolAlign().value() << " bytes *****\n");
396 
397   STI = &MF->getSubtarget<ARMSubtarget>();
398   TII = STI->getInstrInfo();
399   isPositionIndependentOrROPI =
400       STI->getTargetLowering()->isPositionIndependent() || STI->isROPI();
401   AFI = MF->getInfo<ARMFunctionInfo>();
402   DT = &getAnalysis<MachineDominatorTree>();
403 
404   isThumb = AFI->isThumbFunction();
405   isThumb1 = AFI->isThumb1OnlyFunction();
406   isThumb2 = AFI->isThumb2Function();
407 
408   bool GenerateTBB = isThumb2 || (isThumb1 && SynthesizeThumb1TBB);
409   // TBB generation code in this constant island pass has not been adapted to
410   // deal with speculation barriers.
411   if (STI->hardenSlsRetBr())
412     GenerateTBB = false;
413 
414   // Renumber all of the machine basic blocks in the function, guaranteeing that
415   // the numbers agree with the position of the block in the function.
416   MF->RenumberBlocks();
417 
418   // Try to reorder and otherwise adjust the block layout to make good use
419   // of the TB[BH] instructions.
420   bool MadeChange = false;
421   if (GenerateTBB && AdjustJumpTableBlocks) {
422     scanFunctionJumpTables();
423     MadeChange |= reorderThumb2JumpTables();
424     // Data is out of date, so clear it. It'll be re-computed later.
425     T2JumpTables.clear();
426     // Blocks may have shifted around. Keep the numbering up to date.
427     MF->RenumberBlocks();
428   }
429 
430   // Align any non-fallthrough blocks
431   MadeChange |= AlignBlocks(MF, STI);
432 
433   // Perform the initial placement of the constant pool entries.  To start with,
434   // we put them all at the end of the function.
435   std::vector<MachineInstr*> CPEMIs;
436   if (!MCP->isEmpty())
437     doInitialConstPlacement(CPEMIs);
438 
439   if (MF->getJumpTableInfo())
440     doInitialJumpTablePlacement(CPEMIs);
441 
442   /// The next UID to take is the first unused one.
443   AFI->initPICLabelUId(CPEMIs.size());
444 
445   // Do the initial scan of the function, building up information about the
446   // sizes of each block, the location of all the water, and finding all of the
447   // constant pool users.
448   initializeFunctionInfo(CPEMIs);
449   CPEMIs.clear();
450   LLVM_DEBUG(dumpBBs());
451 
452   // Functions with jump tables need an alignment of 4 because they use the ADR
453   // instruction, which aligns the PC to 4 bytes before adding an offset.
454   if (!T2JumpTables.empty())
455     MF->ensureAlignment(Align(4));
456 
457   /// Remove dead constant pool entries.
458   MadeChange |= removeUnusedCPEntries();
459 
460   // Iteratively place constant pool entries and fix up branches until there
461   // is no change.
462   unsigned NoCPIters = 0, NoBRIters = 0;
463   while (true) {
464     LLVM_DEBUG(dbgs() << "Beginning CP iteration #" << NoCPIters << '\n');
465     bool CPChange = false;
466     for (unsigned i = 0, e = CPUsers.size(); i != e; ++i)
467       // For most inputs, it converges in no more than 5 iterations.
468       // If it doesn't end in 10, the input may have huge BB or many CPEs.
469       // In this case, we will try different heuristics.
470       CPChange |= handleConstantPoolUser(i, NoCPIters >= CPMaxIteration / 2);
471     if (CPChange && ++NoCPIters > CPMaxIteration)
472       report_fatal_error("Constant Island pass failed to converge!");
473     LLVM_DEBUG(dumpBBs());
474 
475     // Clear NewWaterList now.  If we split a block for branches, it should
476     // appear as "new water" for the next iteration of constant pool placement.
477     NewWaterList.clear();
478 
479     LLVM_DEBUG(dbgs() << "Beginning BR iteration #" << NoBRIters << '\n');
480     bool BRChange = false;
481     for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i)
482       BRChange |= fixupImmediateBr(ImmBranches[i]);
483     if (BRChange && ++NoBRIters > 30)
484       report_fatal_error("Branch Fix Up pass failed to converge!");
485     LLVM_DEBUG(dumpBBs());
486 
487     if (!CPChange && !BRChange)
488       break;
489     MadeChange = true;
490   }
491 
492   // Shrink 32-bit Thumb2 load and store instructions.
493   if (isThumb2 && !STI->prefers32BitThumb())
494     MadeChange |= optimizeThumb2Instructions();
495 
496   // Shrink 32-bit branch instructions.
497   if (isThumb && STI->hasV8MBaselineOps())
498     MadeChange |= optimizeThumb2Branches();
499 
500   // Optimize jump tables using TBB / TBH.
501   if (GenerateTBB && !STI->genExecuteOnly())
502     MadeChange |= optimizeThumb2JumpTables();
503 
504   // After a while, this might be made debug-only, but it is not expensive.
505   verify();
506 
507   // Save the mapping between original and cloned constpool entries.
508   for (unsigned i = 0, e = CPEntries.size(); i != e; ++i) {
509     for (unsigned j = 0, je = CPEntries[i].size(); j != je; ++j) {
510       const CPEntry & CPE = CPEntries[i][j];
511       if (CPE.CPEMI && CPE.CPEMI->getOperand(1).isCPI())
512         AFI->recordCPEClone(i, CPE.CPI);
513     }
514   }
515 
516   LLVM_DEBUG(dbgs() << '\n'; dumpBBs());
517 
518   BBUtils->clear();
519   WaterList.clear();
520   CPUsers.clear();
521   CPEntries.clear();
522   JumpTableEntryIndices.clear();
523   JumpTableUserIndices.clear();
524   BlockJumpTableRefCount.clear();
525   ImmBranches.clear();
526   PushPopMIs.clear();
527   T2JumpTables.clear();
528 
529   return MadeChange;
530 }
531 
532 /// Perform the initial placement of the regular constant pool entries.
533 /// To start with, we put them all at the end of the function.
534 void
535 ARMConstantIslands::doInitialConstPlacement(std::vector<MachineInstr*> &CPEMIs) {
536   // Create the basic block to hold the CPE's.
537   MachineBasicBlock *BB = MF->CreateMachineBasicBlock();
538   MF->push_back(BB);
539 
540   // MachineConstantPool measures alignment in bytes.
541   const Align MaxAlign = MCP->getConstantPoolAlign();
542   const unsigned MaxLogAlign = Log2(MaxAlign);
543 
544   // Mark the basic block as required by the const-pool.
545   BB->setAlignment(MaxAlign);
546 
547   // The function needs to be as aligned as the basic blocks. The linker may
548   // move functions around based on their alignment.
549   // Special case: halfword literals still need word alignment on the function.
550   Align FuncAlign = MaxAlign;
551   if (MaxAlign == 2)
552     FuncAlign = Align(4);
553   MF->ensureAlignment(FuncAlign);
554 
555   // Order the entries in BB by descending alignment.  That ensures correct
556   // alignment of all entries as long as BB is sufficiently aligned.  Keep
557   // track of the insertion point for each alignment.  We are going to bucket
558   // sort the entries as they are created.
559   SmallVector<MachineBasicBlock::iterator, 8> InsPoint(MaxLogAlign + 1,
560                                                        BB->end());
561 
562   // Add all of the constants from the constant pool to the end block, use an
563   // identity mapping of CPI's to CPE's.
564   const std::vector<MachineConstantPoolEntry> &CPs = MCP->getConstants();
565 
566   const DataLayout &TD = MF->getDataLayout();
567   for (unsigned i = 0, e = CPs.size(); i != e; ++i) {
568     unsigned Size = CPs[i].getSizeInBytes(TD);
569     Align Alignment = CPs[i].getAlign();
570     // Verify that all constant pool entries are a multiple of their alignment.
571     // If not, we would have to pad them out so that instructions stay aligned.
572     assert(isAligned(Alignment, Size) && "CP Entry not multiple of 4 bytes!");
573 
574     // Insert CONSTPOOL_ENTRY before entries with a smaller alignment.
575     unsigned LogAlign = Log2(Alignment);
576     MachineBasicBlock::iterator InsAt = InsPoint[LogAlign];
577     MachineInstr *CPEMI =
578       BuildMI(*BB, InsAt, DebugLoc(), TII->get(ARM::CONSTPOOL_ENTRY))
579         .addImm(i).addConstantPoolIndex(i).addImm(Size);
580     CPEMIs.push_back(CPEMI);
581 
582     // Ensure that future entries with higher alignment get inserted before
583     // CPEMI. This is bucket sort with iterators.
584     for (unsigned a = LogAlign + 1; a <= MaxLogAlign; ++a)
585       if (InsPoint[a] == InsAt)
586         InsPoint[a] = CPEMI;
587 
588     // Add a new CPEntry, but no corresponding CPUser yet.
589     CPEntries.emplace_back(1, CPEntry(CPEMI, i));
590     ++NumCPEs;
591     LLVM_DEBUG(dbgs() << "Moved CPI#" << i << " to end of function, size = "
592                       << Size << ", align = " << Alignment.value() << '\n');
593   }
594   LLVM_DEBUG(BB->dump());
595 }
596 
597 /// Do initial placement of the jump tables. Because Thumb2's TBB and TBH
598 /// instructions can be made more efficient if the jump table immediately
599 /// follows the instruction, it's best to place them immediately next to their
600 /// jumps to begin with. In almost all cases they'll never be moved from that
601 /// position.
602 void ARMConstantIslands::doInitialJumpTablePlacement(
603     std::vector<MachineInstr *> &CPEMIs) {
604   unsigned i = CPEntries.size();
605   auto MJTI = MF->getJumpTableInfo();
606   const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables();
607 
608   // Only inline jump tables are placed in the function.
609   if (MJTI->getEntryKind() != MachineJumpTableInfo::EK_Inline)
610     return;
611 
612   MachineBasicBlock *LastCorrectlyNumberedBB = nullptr;
613   for (MachineBasicBlock &MBB : *MF) {
614     auto MI = MBB.getLastNonDebugInstr();
615     // Look past potential SpeculationBarriers at end of BB.
616     while (MI != MBB.end() &&
617            (isSpeculationBarrierEndBBOpcode(MI->getOpcode()) ||
618             MI->isDebugInstr()))
619       --MI;
620 
621     if (MI == MBB.end())
622       continue;
623 
624     unsigned JTOpcode;
625     switch (MI->getOpcode()) {
626     default:
627       continue;
628     case ARM::BR_JTadd:
629     case ARM::BR_JTr:
630     case ARM::tBR_JTr:
631     case ARM::BR_JTm_i12:
632     case ARM::BR_JTm_rs:
633       // These instructions are emitted only in ARM or Thumb1 modes which do not
634       // support PACBTI. Hence we don't add BTI instructions in the destination
635       // blocks.
636       assert(!MF->getInfo<ARMFunctionInfo>()->branchTargetEnforcement() &&
637              "Branch protection must not be enabled for Arm or Thumb1 modes");
638       JTOpcode = ARM::JUMPTABLE_ADDRS;
639       break;
640     case ARM::t2BR_JT:
641       JTOpcode = ARM::JUMPTABLE_INSTS;
642       break;
643     case ARM::tTBB_JT:
644     case ARM::t2TBB_JT:
645       JTOpcode = ARM::JUMPTABLE_TBB;
646       break;
647     case ARM::tTBH_JT:
648     case ARM::t2TBH_JT:
649       JTOpcode = ARM::JUMPTABLE_TBH;
650       break;
651     }
652 
653     unsigned NumOps = MI->getDesc().getNumOperands();
654     MachineOperand JTOp =
655       MI->getOperand(NumOps - (MI->isPredicable() ? 2 : 1));
656     unsigned JTI = JTOp.getIndex();
657     unsigned Size = JT[JTI].MBBs.size() * sizeof(uint32_t);
658     MachineBasicBlock *JumpTableBB = MF->CreateMachineBasicBlock();
659     MF->insert(std::next(MachineFunction::iterator(MBB)), JumpTableBB);
660     MachineInstr *CPEMI = BuildMI(*JumpTableBB, JumpTableBB->begin(),
661                                   DebugLoc(), TII->get(JTOpcode))
662                               .addImm(i++)
663                               .addJumpTableIndex(JTI)
664                               .addImm(Size);
665     CPEMIs.push_back(CPEMI);
666     CPEntries.emplace_back(1, CPEntry(CPEMI, JTI));
667     JumpTableEntryIndices.insert(std::make_pair(JTI, CPEntries.size() - 1));
668     if (!LastCorrectlyNumberedBB)
669       LastCorrectlyNumberedBB = &MBB;
670   }
671 
672   // If we did anything then we need to renumber the subsequent blocks.
673   if (LastCorrectlyNumberedBB)
674     MF->RenumberBlocks(LastCorrectlyNumberedBB);
675 }
676 
677 /// BBHasFallthrough - Return true if the specified basic block can fallthrough
678 /// into the block immediately after it.
679 bool ARMConstantIslands::BBHasFallthrough(MachineBasicBlock *MBB) {
680   // Get the next machine basic block in the function.
681   MachineFunction::iterator MBBI = MBB->getIterator();
682   // Can't fall off end of function.
683   if (std::next(MBBI) == MBB->getParent()->end())
684     return false;
685 
686   MachineBasicBlock *NextBB = &*std::next(MBBI);
687   if (!MBB->isSuccessor(NextBB))
688     return false;
689 
690   // Try to analyze the end of the block. A potential fallthrough may already
691   // have an unconditional branch for whatever reason.
692   MachineBasicBlock *TBB, *FBB;
693   SmallVector<MachineOperand, 4> Cond;
694   bool TooDifficult = TII->analyzeBranch(*MBB, TBB, FBB, Cond);
695   return TooDifficult || FBB == nullptr;
696 }
697 
698 /// findConstPoolEntry - Given the constpool index and CONSTPOOL_ENTRY MI,
699 /// look up the corresponding CPEntry.
700 ARMConstantIslands::CPEntry *
701 ARMConstantIslands::findConstPoolEntry(unsigned CPI,
702                                        const MachineInstr *CPEMI) {
703   std::vector<CPEntry> &CPEs = CPEntries[CPI];
704   // Number of entries per constpool index should be small, just do a
705   // linear search.
706   for (CPEntry &CPE : CPEs)
707     if (CPE.CPEMI == CPEMI)
708       return &CPE;
709   return nullptr;
710 }
711 
712 /// getCPEAlign - Returns the required alignment of the constant pool entry
713 /// represented by CPEMI.
714 Align ARMConstantIslands::getCPEAlign(const MachineInstr *CPEMI) {
715   switch (CPEMI->getOpcode()) {
716   case ARM::CONSTPOOL_ENTRY:
717     break;
718   case ARM::JUMPTABLE_TBB:
719     return isThumb1 ? Align(4) : Align(1);
720   case ARM::JUMPTABLE_TBH:
721     return isThumb1 ? Align(4) : Align(2);
722   case ARM::JUMPTABLE_INSTS:
723     return Align(2);
724   case ARM::JUMPTABLE_ADDRS:
725     return Align(4);
726   default:
727     llvm_unreachable("unknown constpool entry kind");
728   }
729 
730   unsigned CPI = getCombinedIndex(CPEMI);
731   assert(CPI < MCP->getConstants().size() && "Invalid constant pool index.");
732   return MCP->getConstants()[CPI].getAlign();
733 }
734 
735 // Exception landing pads, blocks that has their adress taken, and function
736 // entry blocks will always be (potential) indirect jump targets, regardless of
737 // whether they are referenced by or not by jump tables.
738 static bool isAlwaysIndirectTarget(const MachineBasicBlock &MBB) {
739   return MBB.isEHPad() || MBB.hasAddressTaken() ||
740          &MBB == &MBB.getParent()->front();
741 }
742 
743 /// scanFunctionJumpTables - Do a scan of the function, building up
744 /// information about the sizes of each block and the locations of all
745 /// the jump tables.
746 void ARMConstantIslands::scanFunctionJumpTables() {
747   for (MachineBasicBlock &MBB : *MF) {
748     for (MachineInstr &I : MBB)
749       if (I.isBranch() &&
750           (I.getOpcode() == ARM::t2BR_JT || I.getOpcode() == ARM::tBR_JTr))
751         T2JumpTables.push_back(&I);
752   }
753 
754   if (!MF->getInfo<ARMFunctionInfo>()->branchTargetEnforcement())
755     return;
756 
757   if (const MachineJumpTableInfo *JTI = MF->getJumpTableInfo())
758     for (const MachineJumpTableEntry &JTE : JTI->getJumpTables())
759       for (const MachineBasicBlock *MBB : JTE.MBBs) {
760         if (isAlwaysIndirectTarget(*MBB))
761           // Set the reference count essentially to infinity, it will never
762           // reach zero and the BTI Instruction will never be removed.
763           BlockJumpTableRefCount[MBB] = std::numeric_limits<int>::max();
764         else
765           ++BlockJumpTableRefCount[MBB];
766       }
767 }
768 
769 /// initializeFunctionInfo - Do the initial scan of the function, building up
770 /// information about the sizes of each block, the location of all the water,
771 /// and finding all of the constant pool users.
772 void ARMConstantIslands::
773 initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs) {
774 
775   BBUtils->computeAllBlockSizes();
776   BBInfoVector &BBInfo = BBUtils->getBBInfo();
777   // The known bits of the entry block offset are determined by the function
778   // alignment.
779   BBInfo.front().KnownBits = Log2(MF->getAlignment());
780 
781   // Compute block offsets and known bits.
782   BBUtils->adjustBBOffsetsAfter(&MF->front());
783 
784   // We only care about jump table instructions when jump tables are inline.
785   MachineJumpTableInfo *MJTI = MF->getJumpTableInfo();
786   bool InlineJumpTables =
787       MJTI && MJTI->getEntryKind() == MachineJumpTableInfo::EK_Inline;
788 
789   // Now go back through the instructions and build up our data structures.
790   for (MachineBasicBlock &MBB : *MF) {
791     // If this block doesn't fall through into the next MBB, then this is
792     // 'water' that a constant pool island could be placed.
793     if (!BBHasFallthrough(&MBB))
794       WaterList.push_back(&MBB);
795 
796     for (MachineInstr &I : MBB) {
797       if (I.isDebugInstr())
798         continue;
799 
800       unsigned Opc = I.getOpcode();
801       if (I.isBranch()) {
802         bool isCond = false;
803         unsigned Bits = 0;
804         unsigned Scale = 1;
805         int UOpc = Opc;
806         switch (Opc) {
807         default:
808           continue;  // Ignore other JT branches
809         case ARM::t2BR_JT:
810         case ARM::tBR_JTr:
811           if (InlineJumpTables)
812             T2JumpTables.push_back(&I);
813           continue;   // Does not get an entry in ImmBranches
814         case ARM::Bcc:
815           isCond = true;
816           UOpc = ARM::B;
817           [[fallthrough]];
818         case ARM::B:
819           Bits = 24;
820           Scale = 4;
821           break;
822         case ARM::tBcc:
823           isCond = true;
824           UOpc = ARM::tB;
825           Bits = 8;
826           Scale = 2;
827           break;
828         case ARM::tB:
829           Bits = 11;
830           Scale = 2;
831           break;
832         case ARM::t2Bcc:
833           isCond = true;
834           UOpc = ARM::t2B;
835           Bits = 20;
836           Scale = 2;
837           break;
838         case ARM::t2B:
839           Bits = 24;
840           Scale = 2;
841           break;
842         }
843 
844         // Record this immediate branch.
845         unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale;
846         ImmBranches.push_back(ImmBranch(&I, MaxOffs, isCond, UOpc));
847       }
848 
849       if (Opc == ARM::tPUSH || Opc == ARM::tPOP_RET)
850         PushPopMIs.push_back(&I);
851 
852       if (Opc == ARM::CONSTPOOL_ENTRY || Opc == ARM::JUMPTABLE_ADDRS ||
853           Opc == ARM::JUMPTABLE_INSTS || Opc == ARM::JUMPTABLE_TBB ||
854           Opc == ARM::JUMPTABLE_TBH)
855         continue;
856 
857       // Scan the instructions for constant pool operands.
858       for (unsigned op = 0, e = I.getNumOperands(); op != e; ++op)
859         if (I.getOperand(op).isCPI() ||
860             (I.getOperand(op).isJTI() && InlineJumpTables)) {
861           // We found one.  The addressing mode tells us the max displacement
862           // from the PC that this instruction permits.
863 
864           // Basic size info comes from the TSFlags field.
865           unsigned Bits = 0;
866           unsigned Scale = 1;
867           bool NegOk = false;
868           bool IsSoImm = false;
869 
870           switch (Opc) {
871           default:
872             llvm_unreachable("Unknown addressing mode for CP reference!");
873 
874           // Taking the address of a CP entry.
875           case ARM::LEApcrel:
876           case ARM::LEApcrelJT: {
877               // This takes a SoImm, which is 8 bit immediate rotated. We'll
878               // pretend the maximum offset is 255 * 4. Since each instruction
879               // 4 byte wide, this is always correct. We'll check for other
880               // displacements that fits in a SoImm as well.
881               Bits = 8;
882               NegOk = true;
883               IsSoImm = true;
884               unsigned CPI = I.getOperand(op).getIndex();
885               assert(CPI < CPEMIs.size());
886               MachineInstr *CPEMI = CPEMIs[CPI];
887               const Align CPEAlign = getCPEAlign(CPEMI);
888               const unsigned LogCPEAlign = Log2(CPEAlign);
889               if (LogCPEAlign >= 2)
890                 Scale = 4;
891               else
892                 // For constants with less than 4-byte alignment,
893                 // we'll pretend the maximum offset is 255 * 1.
894                 Scale = 1;
895             }
896             break;
897           case ARM::t2LEApcrel:
898           case ARM::t2LEApcrelJT:
899             Bits = 12;
900             NegOk = true;
901             break;
902           case ARM::tLEApcrel:
903           case ARM::tLEApcrelJT:
904             Bits = 8;
905             Scale = 4;
906             break;
907 
908           case ARM::LDRBi12:
909           case ARM::LDRi12:
910           case ARM::LDRcp:
911           case ARM::t2LDRpci:
912           case ARM::t2LDRHpci:
913           case ARM::t2LDRSHpci:
914           case ARM::t2LDRBpci:
915           case ARM::t2LDRSBpci:
916             Bits = 12;  // +-offset_12
917             NegOk = true;
918             break;
919 
920           case ARM::tLDRpci:
921             Bits = 8;
922             Scale = 4;  // +(offset_8*4)
923             break;
924 
925           case ARM::VLDRD:
926           case ARM::VLDRS:
927             Bits = 8;
928             Scale = 4;  // +-(offset_8*4)
929             NegOk = true;
930             break;
931           case ARM::VLDRH:
932             Bits = 8;
933             Scale = 2;  // +-(offset_8*2)
934             NegOk = true;
935             break;
936           }
937 
938           // Remember that this is a user of a CP entry.
939           unsigned CPI = I.getOperand(op).getIndex();
940           if (I.getOperand(op).isJTI()) {
941             JumpTableUserIndices.insert(std::make_pair(CPI, CPUsers.size()));
942             CPI = JumpTableEntryIndices[CPI];
943           }
944 
945           MachineInstr *CPEMI = CPEMIs[CPI];
946           unsigned MaxOffs = ((1 << Bits)-1) * Scale;
947           CPUsers.push_back(CPUser(&I, CPEMI, MaxOffs, NegOk, IsSoImm));
948 
949           // Increment corresponding CPEntry reference count.
950           CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
951           assert(CPE && "Cannot find a corresponding CPEntry!");
952           CPE->RefCount++;
953 
954           // Instructions can only use one CP entry, don't bother scanning the
955           // rest of the operands.
956           break;
957         }
958     }
959   }
960 }
961 
962 /// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB
963 /// ID.
964 static bool CompareMBBNumbers(const MachineBasicBlock *LHS,
965                               const MachineBasicBlock *RHS) {
966   return LHS->getNumber() < RHS->getNumber();
967 }
968 
969 /// updateForInsertedWaterBlock - When a block is newly inserted into the
970 /// machine function, it upsets all of the block numbers.  Renumber the blocks
971 /// and update the arrays that parallel this numbering.
972 void ARMConstantIslands::updateForInsertedWaterBlock(MachineBasicBlock *NewBB) {
973   // Renumber the MBB's to keep them consecutive.
974   NewBB->getParent()->RenumberBlocks(NewBB);
975 
976   // Insert an entry into BBInfo to align it properly with the (newly
977   // renumbered) block numbers.
978   BBUtils->insert(NewBB->getNumber(), BasicBlockInfo());
979 
980   // Next, update WaterList.  Specifically, we need to add NewMBB as having
981   // available water after it.
982   water_iterator IP = llvm::lower_bound(WaterList, NewBB, CompareMBBNumbers);
983   WaterList.insert(IP, NewBB);
984 }
985 
986 /// Split the basic block containing MI into two blocks, which are joined by
987 /// an unconditional branch.  Update data structures and renumber blocks to
988 /// account for this change and returns the newly created block.
989 MachineBasicBlock *ARMConstantIslands::splitBlockBeforeInstr(MachineInstr *MI) {
990   MachineBasicBlock *OrigBB = MI->getParent();
991 
992   // Collect liveness information at MI.
993   LivePhysRegs LRs(*MF->getSubtarget().getRegisterInfo());
994   LRs.addLiveOuts(*OrigBB);
995   auto LivenessEnd = ++MachineBasicBlock::iterator(MI).getReverse();
996   for (MachineInstr &LiveMI : make_range(OrigBB->rbegin(), LivenessEnd))
997     LRs.stepBackward(LiveMI);
998 
999   // Create a new MBB for the code after the OrigBB.
1000   MachineBasicBlock *NewBB =
1001     MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
1002   MachineFunction::iterator MBBI = ++OrigBB->getIterator();
1003   MF->insert(MBBI, NewBB);
1004 
1005   // Splice the instructions starting with MI over to NewBB.
1006   NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end());
1007 
1008   // Add an unconditional branch from OrigBB to NewBB.
1009   // Note the new unconditional branch is not being recorded.
1010   // There doesn't seem to be meaningful DebugInfo available; this doesn't
1011   // correspond to anything in the source.
1012   unsigned Opc = isThumb ? (isThumb2 ? ARM::t2B : ARM::tB) : ARM::B;
1013   if (!isThumb)
1014     BuildMI(OrigBB, DebugLoc(), TII->get(Opc)).addMBB(NewBB);
1015   else
1016     BuildMI(OrigBB, DebugLoc(), TII->get(Opc))
1017         .addMBB(NewBB)
1018         .add(predOps(ARMCC::AL));
1019   ++NumSplit;
1020 
1021   // Update the CFG.  All succs of OrigBB are now succs of NewBB.
1022   NewBB->transferSuccessors(OrigBB);
1023 
1024   // OrigBB branches to NewBB.
1025   OrigBB->addSuccessor(NewBB);
1026 
1027   // Update live-in information in the new block.
1028   MachineRegisterInfo &MRI = MF->getRegInfo();
1029   for (MCPhysReg L : LRs)
1030     if (!MRI.isReserved(L))
1031       NewBB->addLiveIn(L);
1032 
1033   // Update internal data structures to account for the newly inserted MBB.
1034   // This is almost the same as updateForInsertedWaterBlock, except that
1035   // the Water goes after OrigBB, not NewBB.
1036   MF->RenumberBlocks(NewBB);
1037 
1038   // Insert an entry into BBInfo to align it properly with the (newly
1039   // renumbered) block numbers.
1040   BBUtils->insert(NewBB->getNumber(), BasicBlockInfo());
1041 
1042   // Next, update WaterList.  Specifically, we need to add OrigMBB as having
1043   // available water after it (but not if it's already there, which happens
1044   // when splitting before a conditional branch that is followed by an
1045   // unconditional branch - in that case we want to insert NewBB).
1046   water_iterator IP = llvm::lower_bound(WaterList, OrigBB, CompareMBBNumbers);
1047   MachineBasicBlock* WaterBB = *IP;
1048   if (WaterBB == OrigBB)
1049     WaterList.insert(std::next(IP), NewBB);
1050   else
1051     WaterList.insert(IP, OrigBB);
1052   NewWaterList.insert(OrigBB);
1053 
1054   // Figure out how large the OrigBB is.  As the first half of the original
1055   // block, it cannot contain a tablejump.  The size includes
1056   // the new jump we added.  (It should be possible to do this without
1057   // recounting everything, but it's very confusing, and this is rarely
1058   // executed.)
1059   BBUtils->computeBlockSize(OrigBB);
1060 
1061   // Figure out how large the NewMBB is.  As the second half of the original
1062   // block, it may contain a tablejump.
1063   BBUtils->computeBlockSize(NewBB);
1064 
1065   // All BBOffsets following these blocks must be modified.
1066   BBUtils->adjustBBOffsetsAfter(OrigBB);
1067 
1068   return NewBB;
1069 }
1070 
1071 /// getUserOffset - Compute the offset of U.MI as seen by the hardware
1072 /// displacement computation.  Update U.KnownAlignment to match its current
1073 /// basic block location.
1074 unsigned ARMConstantIslands::getUserOffset(CPUser &U) const {
1075   unsigned UserOffset = BBUtils->getOffsetOf(U.MI);
1076 
1077   SmallVectorImpl<BasicBlockInfo> &BBInfo = BBUtils->getBBInfo();
1078   const BasicBlockInfo &BBI = BBInfo[U.MI->getParent()->getNumber()];
1079   unsigned KnownBits = BBI.internalKnownBits();
1080 
1081   // The value read from PC is offset from the actual instruction address.
1082   UserOffset += (isThumb ? 4 : 8);
1083 
1084   // Because of inline assembly, we may not know the alignment (mod 4) of U.MI.
1085   // Make sure U.getMaxDisp() returns a constrained range.
1086   U.KnownAlignment = (KnownBits >= 2);
1087 
1088   // On Thumb, offsets==2 mod 4 are rounded down by the hardware for
1089   // purposes of the displacement computation; compensate for that here.
1090   // For unknown alignments, getMaxDisp() constrains the range instead.
1091   if (isThumb && U.KnownAlignment)
1092     UserOffset &= ~3u;
1093 
1094   return UserOffset;
1095 }
1096 
1097 /// isOffsetInRange - Checks whether UserOffset (the location of a constant pool
1098 /// reference) is within MaxDisp of TrialOffset (a proposed location of a
1099 /// constant pool entry).
1100 /// UserOffset is computed by getUserOffset above to include PC adjustments. If
1101 /// the mod 4 alignment of UserOffset is not known, the uncertainty must be
1102 /// subtracted from MaxDisp instead. CPUser::getMaxDisp() does that.
1103 bool ARMConstantIslands::isOffsetInRange(unsigned UserOffset,
1104                                          unsigned TrialOffset, unsigned MaxDisp,
1105                                          bool NegativeOK, bool IsSoImm) {
1106   if (UserOffset <= TrialOffset) {
1107     // User before the Trial.
1108     if (TrialOffset - UserOffset <= MaxDisp)
1109       return true;
1110     // FIXME: Make use full range of soimm values.
1111   } else if (NegativeOK) {
1112     if (UserOffset - TrialOffset <= MaxDisp)
1113       return true;
1114     // FIXME: Make use full range of soimm values.
1115   }
1116   return false;
1117 }
1118 
1119 /// isWaterInRange - Returns true if a CPE placed after the specified
1120 /// Water (a basic block) will be in range for the specific MI.
1121 ///
1122 /// Compute how much the function will grow by inserting a CPE after Water.
1123 bool ARMConstantIslands::isWaterInRange(unsigned UserOffset,
1124                                         MachineBasicBlock* Water, CPUser &U,
1125                                         unsigned &Growth) {
1126   BBInfoVector &BBInfo = BBUtils->getBBInfo();
1127   const Align CPEAlign = getCPEAlign(U.CPEMI);
1128   const unsigned CPEOffset = BBInfo[Water->getNumber()].postOffset(CPEAlign);
1129   unsigned NextBlockOffset;
1130   Align NextBlockAlignment;
1131   MachineFunction::const_iterator NextBlock = Water->getIterator();
1132   if (++NextBlock == MF->end()) {
1133     NextBlockOffset = BBInfo[Water->getNumber()].postOffset();
1134   } else {
1135     NextBlockOffset = BBInfo[NextBlock->getNumber()].Offset;
1136     NextBlockAlignment = NextBlock->getAlignment();
1137   }
1138   unsigned Size = U.CPEMI->getOperand(2).getImm();
1139   unsigned CPEEnd = CPEOffset + Size;
1140 
1141   // The CPE may be able to hide in the alignment padding before the next
1142   // block. It may also cause more padding to be required if it is more aligned
1143   // that the next block.
1144   if (CPEEnd > NextBlockOffset) {
1145     Growth = CPEEnd - NextBlockOffset;
1146     // Compute the padding that would go at the end of the CPE to align the next
1147     // block.
1148     Growth += offsetToAlignment(CPEEnd, NextBlockAlignment);
1149 
1150     // If the CPE is to be inserted before the instruction, that will raise
1151     // the offset of the instruction. Also account for unknown alignment padding
1152     // in blocks between CPE and the user.
1153     if (CPEOffset < UserOffset)
1154       UserOffset += Growth + UnknownPadding(MF->getAlignment(), Log2(CPEAlign));
1155   } else
1156     // CPE fits in existing padding.
1157     Growth = 0;
1158 
1159   return isOffsetInRange(UserOffset, CPEOffset, U);
1160 }
1161 
1162 /// isCPEntryInRange - Returns true if the distance between specific MI and
1163 /// specific ConstPool entry instruction can fit in MI's displacement field.
1164 bool ARMConstantIslands::isCPEntryInRange(MachineInstr *MI, unsigned UserOffset,
1165                                       MachineInstr *CPEMI, unsigned MaxDisp,
1166                                       bool NegOk, bool DoDump) {
1167   unsigned CPEOffset = BBUtils->getOffsetOf(CPEMI);
1168 
1169   if (DoDump) {
1170     LLVM_DEBUG({
1171         BBInfoVector &BBInfo = BBUtils->getBBInfo();
1172       unsigned Block = MI->getParent()->getNumber();
1173       const BasicBlockInfo &BBI = BBInfo[Block];
1174       dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm()
1175              << " max delta=" << MaxDisp
1176              << format(" insn address=%#x", UserOffset) << " in "
1177              << printMBBReference(*MI->getParent()) << ": "
1178              << format("%#x-%x\t", BBI.Offset, BBI.postOffset()) << *MI
1179              << format("CPE address=%#x offset=%+d: ", CPEOffset,
1180                        int(CPEOffset - UserOffset));
1181     });
1182   }
1183 
1184   return isOffsetInRange(UserOffset, CPEOffset, MaxDisp, NegOk);
1185 }
1186 
1187 #ifndef NDEBUG
1188 /// BBIsJumpedOver - Return true of the specified basic block's only predecessor
1189 /// unconditionally branches to its only successor.
1190 static bool BBIsJumpedOver(MachineBasicBlock *MBB) {
1191   if (MBB->pred_size() != 1 || MBB->succ_size() != 1)
1192     return false;
1193 
1194   MachineBasicBlock *Succ = *MBB->succ_begin();
1195   MachineBasicBlock *Pred = *MBB->pred_begin();
1196   MachineInstr *PredMI = &Pred->back();
1197   if (PredMI->getOpcode() == ARM::B || PredMI->getOpcode() == ARM::tB
1198       || PredMI->getOpcode() == ARM::t2B)
1199     return PredMI->getOperand(0).getMBB() == Succ;
1200   return false;
1201 }
1202 #endif // NDEBUG
1203 
1204 /// decrementCPEReferenceCount - find the constant pool entry with index CPI
1205 /// and instruction CPEMI, and decrement its refcount.  If the refcount
1206 /// becomes 0 remove the entry and instruction.  Returns true if we removed
1207 /// the entry, false if we didn't.
1208 bool ARMConstantIslands::decrementCPEReferenceCount(unsigned CPI,
1209                                                     MachineInstr *CPEMI) {
1210   // Find the old entry. Eliminate it if it is no longer used.
1211   CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
1212   assert(CPE && "Unexpected!");
1213   if (--CPE->RefCount == 0) {
1214     removeDeadCPEMI(CPEMI);
1215     CPE->CPEMI = nullptr;
1216     --NumCPEs;
1217     return true;
1218   }
1219   return false;
1220 }
1221 
1222 unsigned ARMConstantIslands::getCombinedIndex(const MachineInstr *CPEMI) {
1223   if (CPEMI->getOperand(1).isCPI())
1224     return CPEMI->getOperand(1).getIndex();
1225 
1226   return JumpTableEntryIndices[CPEMI->getOperand(1).getIndex()];
1227 }
1228 
1229 /// LookForCPEntryInRange - see if the currently referenced CPE is in range;
1230 /// if not, see if an in-range clone of the CPE is in range, and if so,
1231 /// change the data structures so the user references the clone.  Returns:
1232 /// 0 = no existing entry found
1233 /// 1 = entry found, and there were no code insertions or deletions
1234 /// 2 = entry found, and there were code insertions or deletions
1235 int ARMConstantIslands::findInRangeCPEntry(CPUser& U, unsigned UserOffset) {
1236   MachineInstr *UserMI = U.MI;
1237   MachineInstr *CPEMI  = U.CPEMI;
1238 
1239   // Check to see if the CPE is already in-range.
1240   if (isCPEntryInRange(UserMI, UserOffset, CPEMI, U.getMaxDisp(), U.NegOk,
1241                        true)) {
1242     LLVM_DEBUG(dbgs() << "In range\n");
1243     return 1;
1244   }
1245 
1246   // No.  Look for previously created clones of the CPE that are in range.
1247   unsigned CPI = getCombinedIndex(CPEMI);
1248   std::vector<CPEntry> &CPEs = CPEntries[CPI];
1249   for (CPEntry &CPE : CPEs) {
1250     // We already tried this one
1251     if (CPE.CPEMI == CPEMI)
1252       continue;
1253     // Removing CPEs can leave empty entries, skip
1254     if (CPE.CPEMI == nullptr)
1255       continue;
1256     if (isCPEntryInRange(UserMI, UserOffset, CPE.CPEMI, U.getMaxDisp(),
1257                          U.NegOk)) {
1258       LLVM_DEBUG(dbgs() << "Replacing CPE#" << CPI << " with CPE#" << CPE.CPI
1259                         << "\n");
1260       // Point the CPUser node to the replacement
1261       U.CPEMI = CPE.CPEMI;
1262       // Change the CPI in the instruction operand to refer to the clone.
1263       for (MachineOperand &MO : UserMI->operands())
1264         if (MO.isCPI()) {
1265           MO.setIndex(CPE.CPI);
1266           break;
1267         }
1268       // Adjust the refcount of the clone...
1269       CPE.RefCount++;
1270       // ...and the original.  If we didn't remove the old entry, none of the
1271       // addresses changed, so we don't need another pass.
1272       return decrementCPEReferenceCount(CPI, CPEMI) ? 2 : 1;
1273     }
1274   }
1275   return 0;
1276 }
1277 
1278 /// getUnconditionalBrDisp - Returns the maximum displacement that can fit in
1279 /// the specific unconditional branch instruction.
1280 static inline unsigned getUnconditionalBrDisp(int Opc) {
1281   switch (Opc) {
1282   case ARM::tB:
1283     return ((1<<10)-1)*2;
1284   case ARM::t2B:
1285     return ((1<<23)-1)*2;
1286   default:
1287     break;
1288   }
1289 
1290   return ((1<<23)-1)*4;
1291 }
1292 
1293 /// findAvailableWater - Look for an existing entry in the WaterList in which
1294 /// we can place the CPE referenced from U so it's within range of U's MI.
1295 /// Returns true if found, false if not.  If it returns true, WaterIter
1296 /// is set to the WaterList entry.  For Thumb, prefer water that will not
1297 /// introduce padding to water that will.  To ensure that this pass
1298 /// terminates, the CPE location for a particular CPUser is only allowed to
1299 /// move to a lower address, so search backward from the end of the list and
1300 /// prefer the first water that is in range.
1301 bool ARMConstantIslands::findAvailableWater(CPUser &U, unsigned UserOffset,
1302                                             water_iterator &WaterIter,
1303                                             bool CloserWater) {
1304   if (WaterList.empty())
1305     return false;
1306 
1307   unsigned BestGrowth = ~0u;
1308   // The nearest water without splitting the UserBB is right after it.
1309   // If the distance is still large (we have a big BB), then we need to split it
1310   // if we don't converge after certain iterations. This helps the following
1311   // situation to converge:
1312   //   BB0:
1313   //      Big BB
1314   //   BB1:
1315   //      Constant Pool
1316   // When a CP access is out of range, BB0 may be used as water. However,
1317   // inserting islands between BB0 and BB1 makes other accesses out of range.
1318   MachineBasicBlock *UserBB = U.MI->getParent();
1319   BBInfoVector &BBInfo = BBUtils->getBBInfo();
1320   const Align CPEAlign = getCPEAlign(U.CPEMI);
1321   unsigned MinNoSplitDisp = BBInfo[UserBB->getNumber()].postOffset(CPEAlign);
1322   if (CloserWater && MinNoSplitDisp > U.getMaxDisp() / 2)
1323     return false;
1324   for (water_iterator IP = std::prev(WaterList.end()), B = WaterList.begin();;
1325        --IP) {
1326     MachineBasicBlock* WaterBB = *IP;
1327     // Check if water is in range and is either at a lower address than the
1328     // current "high water mark" or a new water block that was created since
1329     // the previous iteration by inserting an unconditional branch.  In the
1330     // latter case, we want to allow resetting the high water mark back to
1331     // this new water since we haven't seen it before.  Inserting branches
1332     // should be relatively uncommon and when it does happen, we want to be
1333     // sure to take advantage of it for all the CPEs near that block, so that
1334     // we don't insert more branches than necessary.
1335     // When CloserWater is true, we try to find the lowest address after (or
1336     // equal to) user MI's BB no matter of padding growth.
1337     unsigned Growth;
1338     if (isWaterInRange(UserOffset, WaterBB, U, Growth) &&
1339         (WaterBB->getNumber() < U.HighWaterMark->getNumber() ||
1340          NewWaterList.count(WaterBB) || WaterBB == U.MI->getParent()) &&
1341         Growth < BestGrowth) {
1342       // This is the least amount of required padding seen so far.
1343       BestGrowth = Growth;
1344       WaterIter = IP;
1345       LLVM_DEBUG(dbgs() << "Found water after " << printMBBReference(*WaterBB)
1346                         << " Growth=" << Growth << '\n');
1347 
1348       if (CloserWater && WaterBB == U.MI->getParent())
1349         return true;
1350       // Keep looking unless it is perfect and we're not looking for the lowest
1351       // possible address.
1352       if (!CloserWater && BestGrowth == 0)
1353         return true;
1354     }
1355     if (IP == B)
1356       break;
1357   }
1358   return BestGrowth != ~0u;
1359 }
1360 
1361 /// createNewWater - No existing WaterList entry will work for
1362 /// CPUsers[CPUserIndex], so create a place to put the CPE.  The end of the
1363 /// block is used if in range, and the conditional branch munged so control
1364 /// flow is correct.  Otherwise the block is split to create a hole with an
1365 /// unconditional branch around it.  In either case NewMBB is set to a
1366 /// block following which the new island can be inserted (the WaterList
1367 /// is not adjusted).
1368 void ARMConstantIslands::createNewWater(unsigned CPUserIndex,
1369                                         unsigned UserOffset,
1370                                         MachineBasicBlock *&NewMBB) {
1371   CPUser &U = CPUsers[CPUserIndex];
1372   MachineInstr *UserMI = U.MI;
1373   MachineInstr *CPEMI  = U.CPEMI;
1374   const Align CPEAlign = getCPEAlign(CPEMI);
1375   MachineBasicBlock *UserMBB = UserMI->getParent();
1376   BBInfoVector &BBInfo = BBUtils->getBBInfo();
1377   const BasicBlockInfo &UserBBI = BBInfo[UserMBB->getNumber()];
1378 
1379   // If the block does not end in an unconditional branch already, and if the
1380   // end of the block is within range, make new water there.  (The addition
1381   // below is for the unconditional branch we will be adding: 4 bytes on ARM +
1382   // Thumb2, 2 on Thumb1.
1383   if (BBHasFallthrough(UserMBB)) {
1384     // Size of branch to insert.
1385     unsigned Delta = isThumb1 ? 2 : 4;
1386     // Compute the offset where the CPE will begin.
1387     unsigned CPEOffset = UserBBI.postOffset(CPEAlign) + Delta;
1388 
1389     if (isOffsetInRange(UserOffset, CPEOffset, U)) {
1390       LLVM_DEBUG(dbgs() << "Split at end of " << printMBBReference(*UserMBB)
1391                         << format(", expected CPE offset %#x\n", CPEOffset));
1392       NewMBB = &*++UserMBB->getIterator();
1393       // Add an unconditional branch from UserMBB to fallthrough block.  Record
1394       // it for branch lengthening; this new branch will not get out of range,
1395       // but if the preceding conditional branch is out of range, the targets
1396       // will be exchanged, and the altered branch may be out of range, so the
1397       // machinery has to know about it.
1398       int UncondBr = isThumb ? ((isThumb2) ? ARM::t2B : ARM::tB) : ARM::B;
1399       if (!isThumb)
1400         BuildMI(UserMBB, DebugLoc(), TII->get(UncondBr)).addMBB(NewMBB);
1401       else
1402         BuildMI(UserMBB, DebugLoc(), TII->get(UncondBr))
1403             .addMBB(NewMBB)
1404             .add(predOps(ARMCC::AL));
1405       unsigned MaxDisp = getUnconditionalBrDisp(UncondBr);
1406       ImmBranches.push_back(ImmBranch(&UserMBB->back(),
1407                                       MaxDisp, false, UncondBr));
1408       BBUtils->computeBlockSize(UserMBB);
1409       BBUtils->adjustBBOffsetsAfter(UserMBB);
1410       return;
1411     }
1412   }
1413 
1414   // What a big block.  Find a place within the block to split it.  This is a
1415   // little tricky on Thumb1 since instructions are 2 bytes and constant pool
1416   // entries are 4 bytes: if instruction I references island CPE, and
1417   // instruction I+1 references CPE', it will not work well to put CPE as far
1418   // forward as possible, since then CPE' cannot immediately follow it (that
1419   // location is 2 bytes farther away from I+1 than CPE was from I) and we'd
1420   // need to create a new island.  So, we make a first guess, then walk through
1421   // the instructions between the one currently being looked at and the
1422   // possible insertion point, and make sure any other instructions that
1423   // reference CPEs will be able to use the same island area; if not, we back
1424   // up the insertion point.
1425 
1426   // Try to split the block so it's fully aligned.  Compute the latest split
1427   // point where we can add a 4-byte branch instruction, and then align to
1428   // Align which is the largest possible alignment in the function.
1429   const Align Align = MF->getAlignment();
1430   assert(Align >= CPEAlign && "Over-aligned constant pool entry");
1431   unsigned KnownBits = UserBBI.internalKnownBits();
1432   unsigned UPad = UnknownPadding(Align, KnownBits);
1433   unsigned BaseInsertOffset = UserOffset + U.getMaxDisp() - UPad;
1434   LLVM_DEBUG(dbgs() << format("Split in middle of big block before %#x",
1435                               BaseInsertOffset));
1436 
1437   // The 4 in the following is for the unconditional branch we'll be inserting
1438   // (allows for long branch on Thumb1).  Alignment of the island is handled
1439   // inside isOffsetInRange.
1440   BaseInsertOffset -= 4;
1441 
1442   LLVM_DEBUG(dbgs() << format(", adjusted to %#x", BaseInsertOffset)
1443                     << " la=" << Log2(Align) << " kb=" << KnownBits
1444                     << " up=" << UPad << '\n');
1445 
1446   // This could point off the end of the block if we've already got constant
1447   // pool entries following this block; only the last one is in the water list.
1448   // Back past any possible branches (allow for a conditional and a maximally
1449   // long unconditional).
1450   if (BaseInsertOffset + 8 >= UserBBI.postOffset()) {
1451     // Ensure BaseInsertOffset is larger than the offset of the instruction
1452     // following UserMI so that the loop which searches for the split point
1453     // iterates at least once.
1454     BaseInsertOffset =
1455         std::max(UserBBI.postOffset() - UPad - 8,
1456                  UserOffset + TII->getInstSizeInBytes(*UserMI) + 1);
1457     // If the CP is referenced(ie, UserOffset) is in first four instructions
1458     // after IT, this recalculated BaseInsertOffset could be in the middle of
1459     // an IT block. If it is, change the BaseInsertOffset to just after the
1460     // IT block. This still make the CP Entry is in range becuase of the
1461     // following reasons.
1462     //   1. The initial BaseseInsertOffset calculated is (UserOffset +
1463     //   U.getMaxDisp() - UPad).
1464     //   2. An IT block is only at most 4 instructions plus the "it" itself (18
1465     //   bytes).
1466     //   3. All the relevant instructions support much larger Maximum
1467     //   displacement.
1468     MachineBasicBlock::iterator I = UserMI;
1469     ++I;
1470     Register PredReg;
1471     for (unsigned Offset = UserOffset + TII->getInstSizeInBytes(*UserMI);
1472          I->getOpcode() != ARM::t2IT &&
1473          getITInstrPredicate(*I, PredReg) != ARMCC::AL;
1474          Offset += TII->getInstSizeInBytes(*I), I = std::next(I)) {
1475       BaseInsertOffset =
1476           std::max(BaseInsertOffset, Offset + TII->getInstSizeInBytes(*I) + 1);
1477       assert(I != UserMBB->end() && "Fell off end of block");
1478     }
1479     LLVM_DEBUG(dbgs() << format("Move inside block: %#x\n", BaseInsertOffset));
1480   }
1481   unsigned EndInsertOffset = BaseInsertOffset + 4 + UPad +
1482     CPEMI->getOperand(2).getImm();
1483   MachineBasicBlock::iterator MI = UserMI;
1484   ++MI;
1485   unsigned CPUIndex = CPUserIndex+1;
1486   unsigned NumCPUsers = CPUsers.size();
1487   MachineInstr *LastIT = nullptr;
1488   for (unsigned Offset = UserOffset + TII->getInstSizeInBytes(*UserMI);
1489        Offset < BaseInsertOffset;
1490        Offset += TII->getInstSizeInBytes(*MI), MI = std::next(MI)) {
1491     assert(MI != UserMBB->end() && "Fell off end of block");
1492     if (CPUIndex < NumCPUsers && CPUsers[CPUIndex].MI == &*MI) {
1493       CPUser &U = CPUsers[CPUIndex];
1494       if (!isOffsetInRange(Offset, EndInsertOffset, U)) {
1495         // Shift intertion point by one unit of alignment so it is within reach.
1496         BaseInsertOffset -= Align.value();
1497         EndInsertOffset -= Align.value();
1498       }
1499       // This is overly conservative, as we don't account for CPEMIs being
1500       // reused within the block, but it doesn't matter much.  Also assume CPEs
1501       // are added in order with alignment padding.  We may eventually be able
1502       // to pack the aligned CPEs better.
1503       EndInsertOffset += U.CPEMI->getOperand(2).getImm();
1504       CPUIndex++;
1505     }
1506 
1507     // Remember the last IT instruction.
1508     if (MI->getOpcode() == ARM::t2IT)
1509       LastIT = &*MI;
1510   }
1511 
1512   --MI;
1513 
1514   // Avoid splitting an IT block.
1515   if (LastIT) {
1516     Register PredReg;
1517     ARMCC::CondCodes CC = getITInstrPredicate(*MI, PredReg);
1518     if (CC != ARMCC::AL)
1519       MI = LastIT;
1520   }
1521 
1522   // Avoid splitting a MOVW+MOVT pair with a relocation on Windows.
1523   // On Windows, this instruction pair is covered by one single
1524   // IMAGE_REL_ARM_MOV32T relocation which covers both instructions. If a
1525   // constant island is injected inbetween them, the relocation will clobber
1526   // the instruction and fail to update the MOVT instruction.
1527   // (These instructions are bundled up until right before the ConstantIslands
1528   // pass.)
1529   if (STI->isTargetWindows() && isThumb && MI->getOpcode() == ARM::t2MOVTi16 &&
1530       (MI->getOperand(2).getTargetFlags() & ARMII::MO_OPTION_MASK) ==
1531           ARMII::MO_HI16) {
1532     --MI;
1533     assert(MI->getOpcode() == ARM::t2MOVi16 &&
1534            (MI->getOperand(1).getTargetFlags() & ARMII::MO_OPTION_MASK) ==
1535                ARMII::MO_LO16);
1536   }
1537 
1538   // We really must not split an IT block.
1539 #ifndef NDEBUG
1540   Register PredReg;
1541   assert(!isThumb || getITInstrPredicate(*MI, PredReg) == ARMCC::AL);
1542 #endif
1543   NewMBB = splitBlockBeforeInstr(&*MI);
1544 }
1545 
1546 /// handleConstantPoolUser - Analyze the specified user, checking to see if it
1547 /// is out-of-range.  If so, pick up the constant pool value and move it some
1548 /// place in-range.  Return true if we changed any addresses (thus must run
1549 /// another pass of branch lengthening), false otherwise.
1550 bool ARMConstantIslands::handleConstantPoolUser(unsigned CPUserIndex,
1551                                                 bool CloserWater) {
1552   CPUser &U = CPUsers[CPUserIndex];
1553   MachineInstr *UserMI = U.MI;
1554   MachineInstr *CPEMI  = U.CPEMI;
1555   unsigned CPI = getCombinedIndex(CPEMI);
1556   unsigned Size = CPEMI->getOperand(2).getImm();
1557   // Compute this only once, it's expensive.
1558   unsigned UserOffset = getUserOffset(U);
1559 
1560   // See if the current entry is within range, or there is a clone of it
1561   // in range.
1562   int result = findInRangeCPEntry(U, UserOffset);
1563   if (result==1) return false;
1564   else if (result==2) return true;
1565 
1566   // No existing clone of this CPE is within range.
1567   // We will be generating a new clone.  Get a UID for it.
1568   unsigned ID = AFI->createPICLabelUId();
1569 
1570   // Look for water where we can place this CPE.
1571   MachineBasicBlock *NewIsland = MF->CreateMachineBasicBlock();
1572   MachineBasicBlock *NewMBB;
1573   water_iterator IP;
1574   if (findAvailableWater(U, UserOffset, IP, CloserWater)) {
1575     LLVM_DEBUG(dbgs() << "Found water in range\n");
1576     MachineBasicBlock *WaterBB = *IP;
1577 
1578     // If the original WaterList entry was "new water" on this iteration,
1579     // propagate that to the new island.  This is just keeping NewWaterList
1580     // updated to match the WaterList, which will be updated below.
1581     if (NewWaterList.erase(WaterBB))
1582       NewWaterList.insert(NewIsland);
1583 
1584     // The new CPE goes before the following block (NewMBB).
1585     NewMBB = &*++WaterBB->getIterator();
1586   } else {
1587     // No water found.
1588     LLVM_DEBUG(dbgs() << "No water found\n");
1589     createNewWater(CPUserIndex, UserOffset, NewMBB);
1590 
1591     // splitBlockBeforeInstr adds to WaterList, which is important when it is
1592     // called while handling branches so that the water will be seen on the
1593     // next iteration for constant pools, but in this context, we don't want
1594     // it.  Check for this so it will be removed from the WaterList.
1595     // Also remove any entry from NewWaterList.
1596     MachineBasicBlock *WaterBB = &*--NewMBB->getIterator();
1597     IP = find(WaterList, WaterBB);
1598     if (IP != WaterList.end())
1599       NewWaterList.erase(WaterBB);
1600 
1601     // We are adding new water.  Update NewWaterList.
1602     NewWaterList.insert(NewIsland);
1603   }
1604   // Always align the new block because CP entries can be smaller than 4
1605   // bytes. Be careful not to decrease the existing alignment, e.g. NewMBB may
1606   // be an already aligned constant pool block.
1607   const Align Alignment = isThumb ? Align(2) : Align(4);
1608   if (NewMBB->getAlignment() < Alignment)
1609     NewMBB->setAlignment(Alignment);
1610 
1611   // Remove the original WaterList entry; we want subsequent insertions in
1612   // this vicinity to go after the one we're about to insert.  This
1613   // considerably reduces the number of times we have to move the same CPE
1614   // more than once and is also important to ensure the algorithm terminates.
1615   if (IP != WaterList.end())
1616     WaterList.erase(IP);
1617 
1618   // Okay, we know we can put an island before NewMBB now, do it!
1619   MF->insert(NewMBB->getIterator(), NewIsland);
1620 
1621   // Update internal data structures to account for the newly inserted MBB.
1622   updateForInsertedWaterBlock(NewIsland);
1623 
1624   // Now that we have an island to add the CPE to, clone the original CPE and
1625   // add it to the island.
1626   U.HighWaterMark = NewIsland;
1627   U.CPEMI = BuildMI(NewIsland, DebugLoc(), CPEMI->getDesc())
1628                 .addImm(ID)
1629                 .add(CPEMI->getOperand(1))
1630                 .addImm(Size);
1631   CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1));
1632   ++NumCPEs;
1633 
1634   // Decrement the old entry, and remove it if refcount becomes 0.
1635   decrementCPEReferenceCount(CPI, CPEMI);
1636 
1637   // Mark the basic block as aligned as required by the const-pool entry.
1638   NewIsland->setAlignment(getCPEAlign(U.CPEMI));
1639 
1640   // Increase the size of the island block to account for the new entry.
1641   BBUtils->adjustBBSize(NewIsland, Size);
1642   BBUtils->adjustBBOffsetsAfter(&*--NewIsland->getIterator());
1643 
1644   // Finally, change the CPI in the instruction operand to be ID.
1645   for (MachineOperand &MO : UserMI->operands())
1646     if (MO.isCPI()) {
1647       MO.setIndex(ID);
1648       break;
1649     }
1650 
1651   LLVM_DEBUG(
1652       dbgs() << "  Moved CPE to #" << ID << " CPI=" << CPI
1653              << format(" offset=%#x\n",
1654                        BBUtils->getBBInfo()[NewIsland->getNumber()].Offset));
1655 
1656   return true;
1657 }
1658 
1659 /// removeDeadCPEMI - Remove a dead constant pool entry instruction. Update
1660 /// sizes and offsets of impacted basic blocks.
1661 void ARMConstantIslands::removeDeadCPEMI(MachineInstr *CPEMI) {
1662   MachineBasicBlock *CPEBB = CPEMI->getParent();
1663   unsigned Size = CPEMI->getOperand(2).getImm();
1664   CPEMI->eraseFromParent();
1665   BBInfoVector &BBInfo = BBUtils->getBBInfo();
1666   BBUtils->adjustBBSize(CPEBB, -Size);
1667   // All succeeding offsets have the current size value added in, fix this.
1668   if (CPEBB->empty()) {
1669     BBInfo[CPEBB->getNumber()].Size = 0;
1670 
1671     // This block no longer needs to be aligned.
1672     CPEBB->setAlignment(Align(1));
1673   } else {
1674     // Entries are sorted by descending alignment, so realign from the front.
1675     CPEBB->setAlignment(getCPEAlign(&*CPEBB->begin()));
1676   }
1677 
1678   BBUtils->adjustBBOffsetsAfter(CPEBB);
1679   // An island has only one predecessor BB and one successor BB. Check if
1680   // this BB's predecessor jumps directly to this BB's successor. This
1681   // shouldn't happen currently.
1682   assert(!BBIsJumpedOver(CPEBB) && "How did this happen?");
1683   // FIXME: remove the empty blocks after all the work is done?
1684 }
1685 
1686 /// removeUnusedCPEntries - Remove constant pool entries whose refcounts
1687 /// are zero.
1688 bool ARMConstantIslands::removeUnusedCPEntries() {
1689   unsigned MadeChange = false;
1690   for (std::vector<CPEntry> &CPEs : CPEntries) {
1691     for (CPEntry &CPE : CPEs) {
1692       if (CPE.RefCount == 0 && CPE.CPEMI) {
1693         removeDeadCPEMI(CPE.CPEMI);
1694         CPE.CPEMI = nullptr;
1695         MadeChange = true;
1696       }
1697     }
1698   }
1699   return MadeChange;
1700 }
1701 
1702 
1703 /// fixupImmediateBr - Fix up an immediate branch whose destination is too far
1704 /// away to fit in its displacement field.
1705 bool ARMConstantIslands::fixupImmediateBr(ImmBranch &Br) {
1706   MachineInstr *MI = Br.MI;
1707   MachineBasicBlock *DestBB = MI->getOperand(0).getMBB();
1708 
1709   // Check to see if the DestBB is already in-range.
1710   if (BBUtils->isBBInRange(MI, DestBB, Br.MaxDisp))
1711     return false;
1712 
1713   if (!Br.isCond)
1714     return fixupUnconditionalBr(Br);
1715   return fixupConditionalBr(Br);
1716 }
1717 
1718 /// fixupUnconditionalBr - Fix up an unconditional branch whose destination is
1719 /// too far away to fit in its displacement field. If the LR register has been
1720 /// spilled in the epilogue, then we can use BL to implement a far jump.
1721 /// Otherwise, add an intermediate branch instruction to a branch.
1722 bool
1723 ARMConstantIslands::fixupUnconditionalBr(ImmBranch &Br) {
1724   MachineInstr *MI = Br.MI;
1725   MachineBasicBlock *MBB = MI->getParent();
1726   if (!isThumb1)
1727     llvm_unreachable("fixupUnconditionalBr is Thumb1 only!");
1728 
1729   if (!AFI->isLRSpilled())
1730     report_fatal_error("underestimated function size");
1731 
1732   // Use BL to implement far jump.
1733   Br.MaxDisp = (1 << 21) * 2;
1734   MI->setDesc(TII->get(ARM::tBfar));
1735   BBInfoVector &BBInfo = BBUtils->getBBInfo();
1736   BBInfo[MBB->getNumber()].Size += 2;
1737   BBUtils->adjustBBOffsetsAfter(MBB);
1738   ++NumUBrFixed;
1739 
1740   LLVM_DEBUG(dbgs() << "  Changed B to long jump " << *MI);
1741 
1742   return true;
1743 }
1744 
1745 /// fixupConditionalBr - Fix up a conditional branch whose destination is too
1746 /// far away to fit in its displacement field. It is converted to an inverse
1747 /// conditional branch + an unconditional branch to the destination.
1748 bool
1749 ARMConstantIslands::fixupConditionalBr(ImmBranch &Br) {
1750   MachineInstr *MI = Br.MI;
1751   MachineBasicBlock *DestBB = MI->getOperand(0).getMBB();
1752 
1753   // Add an unconditional branch to the destination and invert the branch
1754   // condition to jump over it:
1755   // blt L1
1756   // =>
1757   // bge L2
1758   // b   L1
1759   // L2:
1760   ARMCC::CondCodes CC = (ARMCC::CondCodes)MI->getOperand(1).getImm();
1761   CC = ARMCC::getOppositeCondition(CC);
1762   Register CCReg = MI->getOperand(2).getReg();
1763 
1764   // If the branch is at the end of its MBB and that has a fall-through block,
1765   // direct the updated conditional branch to the fall-through block. Otherwise,
1766   // split the MBB before the next instruction.
1767   MachineBasicBlock *MBB = MI->getParent();
1768   MachineInstr *BMI = &MBB->back();
1769   bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB);
1770 
1771   ++NumCBrFixed;
1772   if (BMI != MI) {
1773     if (std::next(MachineBasicBlock::iterator(MI)) == std::prev(MBB->end()) &&
1774         BMI->getOpcode() == Br.UncondBr) {
1775       // Last MI in the BB is an unconditional branch. Can we simply invert the
1776       // condition and swap destinations:
1777       // beq L1
1778       // b   L2
1779       // =>
1780       // bne L2
1781       // b   L1
1782       MachineBasicBlock *NewDest = BMI->getOperand(0).getMBB();
1783       if (BBUtils->isBBInRange(MI, NewDest, Br.MaxDisp)) {
1784         LLVM_DEBUG(
1785             dbgs() << "  Invert Bcc condition and swap its destination with "
1786                    << *BMI);
1787         BMI->getOperand(0).setMBB(DestBB);
1788         MI->getOperand(0).setMBB(NewDest);
1789         MI->getOperand(1).setImm(CC);
1790         return true;
1791       }
1792     }
1793   }
1794 
1795   if (NeedSplit) {
1796     splitBlockBeforeInstr(MI);
1797     // No need for the branch to the next block. We're adding an unconditional
1798     // branch to the destination.
1799     int delta = TII->getInstSizeInBytes(MBB->back());
1800     BBUtils->adjustBBSize(MBB, -delta);
1801     MBB->back().eraseFromParent();
1802 
1803     // The conditional successor will be swapped between the BBs after this, so
1804     // update CFG.
1805     MBB->addSuccessor(DestBB);
1806     std::next(MBB->getIterator())->removeSuccessor(DestBB);
1807 
1808     // BBInfo[SplitBB].Offset is wrong temporarily, fixed below
1809   }
1810   MachineBasicBlock *NextBB = &*++MBB->getIterator();
1811 
1812   LLVM_DEBUG(dbgs() << "  Insert B to " << printMBBReference(*DestBB)
1813                     << " also invert condition and change dest. to "
1814                     << printMBBReference(*NextBB) << "\n");
1815 
1816   // Insert a new conditional branch and a new unconditional branch.
1817   // Also update the ImmBranch as well as adding a new entry for the new branch.
1818   BuildMI(MBB, DebugLoc(), TII->get(MI->getOpcode()))
1819     .addMBB(NextBB).addImm(CC).addReg(CCReg);
1820   Br.MI = &MBB->back();
1821   BBUtils->adjustBBSize(MBB, TII->getInstSizeInBytes(MBB->back()));
1822   if (isThumb)
1823     BuildMI(MBB, DebugLoc(), TII->get(Br.UncondBr))
1824         .addMBB(DestBB)
1825         .add(predOps(ARMCC::AL));
1826   else
1827     BuildMI(MBB, DebugLoc(), TII->get(Br.UncondBr)).addMBB(DestBB);
1828   BBUtils->adjustBBSize(MBB, TII->getInstSizeInBytes(MBB->back()));
1829   unsigned MaxDisp = getUnconditionalBrDisp(Br.UncondBr);
1830   ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr));
1831 
1832   // Remove the old conditional branch.  It may or may not still be in MBB.
1833   BBUtils->adjustBBSize(MI->getParent(), -TII->getInstSizeInBytes(*MI));
1834   MI->eraseFromParent();
1835   BBUtils->adjustBBOffsetsAfter(MBB);
1836   return true;
1837 }
1838 
1839 bool ARMConstantIslands::optimizeThumb2Instructions() {
1840   bool MadeChange = false;
1841 
1842   // Shrink ADR and LDR from constantpool.
1843   for (CPUser &U : CPUsers) {
1844     unsigned Opcode = U.MI->getOpcode();
1845     unsigned NewOpc = 0;
1846     unsigned Scale = 1;
1847     unsigned Bits = 0;
1848     switch (Opcode) {
1849     default: break;
1850     case ARM::t2LEApcrel:
1851       if (isARMLowRegister(U.MI->getOperand(0).getReg())) {
1852         NewOpc = ARM::tLEApcrel;
1853         Bits = 8;
1854         Scale = 4;
1855       }
1856       break;
1857     case ARM::t2LDRpci:
1858       if (isARMLowRegister(U.MI->getOperand(0).getReg())) {
1859         NewOpc = ARM::tLDRpci;
1860         Bits = 8;
1861         Scale = 4;
1862       }
1863       break;
1864     }
1865 
1866     if (!NewOpc)
1867       continue;
1868 
1869     unsigned UserOffset = getUserOffset(U);
1870     unsigned MaxOffs = ((1 << Bits) - 1) * Scale;
1871 
1872     // Be conservative with inline asm.
1873     if (!U.KnownAlignment)
1874       MaxOffs -= 2;
1875 
1876     // FIXME: Check if offset is multiple of scale if scale is not 4.
1877     if (isCPEntryInRange(U.MI, UserOffset, U.CPEMI, MaxOffs, false, true)) {
1878       LLVM_DEBUG(dbgs() << "Shrink: " << *U.MI);
1879       U.MI->setDesc(TII->get(NewOpc));
1880       MachineBasicBlock *MBB = U.MI->getParent();
1881       BBUtils->adjustBBSize(MBB, -2);
1882       BBUtils->adjustBBOffsetsAfter(MBB);
1883       ++NumT2CPShrunk;
1884       MadeChange = true;
1885     }
1886   }
1887 
1888   return MadeChange;
1889 }
1890 
1891 
1892 bool ARMConstantIslands::optimizeThumb2Branches() {
1893 
1894   auto TryShrinkBranch = [this](ImmBranch &Br) {
1895     unsigned Opcode = Br.MI->getOpcode();
1896     unsigned NewOpc = 0;
1897     unsigned Scale = 1;
1898     unsigned Bits = 0;
1899     switch (Opcode) {
1900     default: break;
1901     case ARM::t2B:
1902       NewOpc = ARM::tB;
1903       Bits = 11;
1904       Scale = 2;
1905       break;
1906     case ARM::t2Bcc:
1907       NewOpc = ARM::tBcc;
1908       Bits = 8;
1909       Scale = 2;
1910       break;
1911     }
1912     if (NewOpc) {
1913       unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale;
1914       MachineBasicBlock *DestBB = Br.MI->getOperand(0).getMBB();
1915       if (BBUtils->isBBInRange(Br.MI, DestBB, MaxOffs)) {
1916         LLVM_DEBUG(dbgs() << "Shrink branch: " << *Br.MI);
1917         Br.MI->setDesc(TII->get(NewOpc));
1918         MachineBasicBlock *MBB = Br.MI->getParent();
1919         BBUtils->adjustBBSize(MBB, -2);
1920         BBUtils->adjustBBOffsetsAfter(MBB);
1921         ++NumT2BrShrunk;
1922         return true;
1923       }
1924     }
1925     return false;
1926   };
1927 
1928   struct ImmCompare {
1929     MachineInstr* MI = nullptr;
1930     unsigned NewOpc = 0;
1931   };
1932 
1933   auto FindCmpForCBZ = [this](ImmBranch &Br, ImmCompare &ImmCmp,
1934                               MachineBasicBlock *DestBB) {
1935     ImmCmp.MI = nullptr;
1936     ImmCmp.NewOpc = 0;
1937 
1938     // If the conditional branch doesn't kill CPSR, then CPSR can be liveout
1939     // so this transformation is not safe.
1940     if (!Br.MI->killsRegister(ARM::CPSR))
1941       return false;
1942 
1943     Register PredReg;
1944     unsigned NewOpc = 0;
1945     ARMCC::CondCodes Pred = getInstrPredicate(*Br.MI, PredReg);
1946     if (Pred == ARMCC::EQ)
1947       NewOpc = ARM::tCBZ;
1948     else if (Pred == ARMCC::NE)
1949       NewOpc = ARM::tCBNZ;
1950     else
1951       return false;
1952 
1953     // Check if the distance is within 126. Subtract starting offset by 2
1954     // because the cmp will be eliminated.
1955     unsigned BrOffset = BBUtils->getOffsetOf(Br.MI) + 4 - 2;
1956     BBInfoVector &BBInfo = BBUtils->getBBInfo();
1957     unsigned DestOffset = BBInfo[DestBB->getNumber()].Offset;
1958     if (BrOffset >= DestOffset || (DestOffset - BrOffset) > 126)
1959       return false;
1960 
1961     // Search backwards to find a tCMPi8
1962     auto *TRI = STI->getRegisterInfo();
1963     MachineInstr *CmpMI = findCMPToFoldIntoCBZ(Br.MI, TRI);
1964     if (!CmpMI || CmpMI->getOpcode() != ARM::tCMPi8)
1965       return false;
1966 
1967     ImmCmp.MI = CmpMI;
1968     ImmCmp.NewOpc = NewOpc;
1969     return true;
1970   };
1971 
1972   auto TryConvertToLE = [this](ImmBranch &Br, ImmCompare &Cmp) {
1973     if (Br.MI->getOpcode() != ARM::t2Bcc || !STI->hasLOB() ||
1974         STI->hasMinSize())
1975       return false;
1976 
1977     MachineBasicBlock *MBB = Br.MI->getParent();
1978     MachineBasicBlock *DestBB = Br.MI->getOperand(0).getMBB();
1979     if (BBUtils->getOffsetOf(MBB) < BBUtils->getOffsetOf(DestBB) ||
1980         !BBUtils->isBBInRange(Br.MI, DestBB, 4094))
1981       return false;
1982 
1983     if (!DT->dominates(DestBB, MBB))
1984       return false;
1985 
1986     // We queried for the CBN?Z opcode based upon the 'ExitBB', the opposite
1987     // target of Br. So now we need to reverse the condition.
1988     Cmp.NewOpc = Cmp.NewOpc == ARM::tCBZ ? ARM::tCBNZ : ARM::tCBZ;
1989 
1990     MachineInstrBuilder MIB = BuildMI(*MBB, Br.MI, Br.MI->getDebugLoc(),
1991                                       TII->get(ARM::t2LE));
1992     // Swapped a t2Bcc for a t2LE, so no need to update the size of the block.
1993     MIB.add(Br.MI->getOperand(0));
1994     Br.MI->eraseFromParent();
1995     Br.MI = MIB;
1996     ++NumLEInserted;
1997     return true;
1998   };
1999 
2000   bool MadeChange = false;
2001 
2002   // The order in which branches appear in ImmBranches is approximately their
2003   // order within the function body. By visiting later branches first, we reduce
2004   // the distance between earlier forward branches and their targets, making it
2005   // more likely that the cbn?z optimization, which can only apply to forward
2006   // branches, will succeed.
2007   for (ImmBranch &Br : reverse(ImmBranches)) {
2008     MachineBasicBlock *DestBB = Br.MI->getOperand(0).getMBB();
2009     MachineBasicBlock *MBB = Br.MI->getParent();
2010     MachineBasicBlock *ExitBB = &MBB->back() == Br.MI ?
2011       MBB->getFallThrough() :
2012       MBB->back().getOperand(0).getMBB();
2013 
2014     ImmCompare Cmp;
2015     if (FindCmpForCBZ(Br, Cmp, ExitBB) && TryConvertToLE(Br, Cmp)) {
2016       DestBB = ExitBB;
2017       MadeChange = true;
2018     } else {
2019       FindCmpForCBZ(Br, Cmp, DestBB);
2020       MadeChange |= TryShrinkBranch(Br);
2021     }
2022 
2023     unsigned Opcode = Br.MI->getOpcode();
2024     if ((Opcode != ARM::tBcc && Opcode != ARM::t2LE) || !Cmp.NewOpc)
2025       continue;
2026 
2027     Register Reg = Cmp.MI->getOperand(0).getReg();
2028 
2029     // Check for Kill flags on Reg. If they are present remove them and set kill
2030     // on the new CBZ.
2031     auto *TRI = STI->getRegisterInfo();
2032     MachineBasicBlock::iterator KillMI = Br.MI;
2033     bool RegKilled = false;
2034     do {
2035       --KillMI;
2036       if (KillMI->killsRegister(Reg, TRI)) {
2037         KillMI->clearRegisterKills(Reg, TRI);
2038         RegKilled = true;
2039         break;
2040       }
2041     } while (KillMI != Cmp.MI);
2042 
2043     // Create the new CBZ/CBNZ
2044     LLVM_DEBUG(dbgs() << "Fold: " << *Cmp.MI << " and: " << *Br.MI);
2045     MachineInstr *NewBR =
2046         BuildMI(*MBB, Br.MI, Br.MI->getDebugLoc(), TII->get(Cmp.NewOpc))
2047             .addReg(Reg, getKillRegState(RegKilled) |
2048                              getRegState(Cmp.MI->getOperand(0)))
2049             .addMBB(DestBB, Br.MI->getOperand(0).getTargetFlags());
2050 
2051     Cmp.MI->eraseFromParent();
2052 
2053     if (Br.MI->getOpcode() == ARM::tBcc) {
2054       Br.MI->eraseFromParent();
2055       Br.MI = NewBR;
2056       BBUtils->adjustBBSize(MBB, -2);
2057     } else if (MBB->back().getOpcode() != ARM::t2LE) {
2058       // An LE has been generated, but it's not the terminator - that is an
2059       // unconditional branch. However, the logic has now been reversed with the
2060       // CBN?Z being the conditional branch and the LE being the unconditional
2061       // branch. So this means we can remove the redundant unconditional branch
2062       // at the end of the block.
2063       MachineInstr *LastMI = &MBB->back();
2064       BBUtils->adjustBBSize(MBB, -LastMI->getDesc().getSize());
2065       LastMI->eraseFromParent();
2066     }
2067     BBUtils->adjustBBOffsetsAfter(MBB);
2068     ++NumCBZ;
2069     MadeChange = true;
2070   }
2071 
2072   return MadeChange;
2073 }
2074 
2075 static bool isSimpleIndexCalc(MachineInstr &I, unsigned EntryReg,
2076                               unsigned BaseReg) {
2077   if (I.getOpcode() != ARM::t2ADDrs)
2078     return false;
2079 
2080   if (I.getOperand(0).getReg() != EntryReg)
2081     return false;
2082 
2083   if (I.getOperand(1).getReg() != BaseReg)
2084     return false;
2085 
2086   // FIXME: what about CC and IdxReg?
2087   return true;
2088 }
2089 
2090 /// While trying to form a TBB/TBH instruction, we may (if the table
2091 /// doesn't immediately follow the BR_JT) need access to the start of the
2092 /// jump-table. We know one instruction that produces such a register; this
2093 /// function works out whether that definition can be preserved to the BR_JT,
2094 /// possibly by removing an intervening addition (which is usually needed to
2095 /// calculate the actual entry to jump to).
2096 bool ARMConstantIslands::preserveBaseRegister(MachineInstr *JumpMI,
2097                                               MachineInstr *LEAMI,
2098                                               unsigned &DeadSize,
2099                                               bool &CanDeleteLEA,
2100                                               bool &BaseRegKill) {
2101   if (JumpMI->getParent() != LEAMI->getParent())
2102     return false;
2103 
2104   // Now we hope that we have at least these instructions in the basic block:
2105   //     BaseReg = t2LEA ...
2106   //     [...]
2107   //     EntryReg = t2ADDrs BaseReg, ...
2108   //     [...]
2109   //     t2BR_JT EntryReg
2110   //
2111   // We have to be very conservative about what we recognise here though. The
2112   // main perturbing factors to watch out for are:
2113   //    + Spills at any point in the chain: not direct problems but we would
2114   //      expect a blocking Def of the spilled register so in practice what we
2115   //      can do is limited.
2116   //    + EntryReg == BaseReg: this is the one situation we should allow a Def
2117   //      of BaseReg, but only if the t2ADDrs can be removed.
2118   //    + Some instruction other than t2ADDrs computing the entry. Not seen in
2119   //      the wild, but we should be careful.
2120   Register EntryReg = JumpMI->getOperand(0).getReg();
2121   Register BaseReg = LEAMI->getOperand(0).getReg();
2122 
2123   CanDeleteLEA = true;
2124   BaseRegKill = false;
2125   MachineInstr *RemovableAdd = nullptr;
2126   MachineBasicBlock::iterator I(LEAMI);
2127   for (++I; &*I != JumpMI; ++I) {
2128     if (isSimpleIndexCalc(*I, EntryReg, BaseReg)) {
2129       RemovableAdd = &*I;
2130       break;
2131     }
2132 
2133     for (const MachineOperand &MO : I->operands()) {
2134       if (!MO.isReg() || !MO.getReg())
2135         continue;
2136       if (MO.isDef() && MO.getReg() == BaseReg)
2137         return false;
2138       if (MO.isUse() && MO.getReg() == BaseReg) {
2139         BaseRegKill = BaseRegKill || MO.isKill();
2140         CanDeleteLEA = false;
2141       }
2142     }
2143   }
2144 
2145   if (!RemovableAdd)
2146     return true;
2147 
2148   // Check the add really is removable, and that nothing else in the block
2149   // clobbers BaseReg.
2150   for (++I; &*I != JumpMI; ++I) {
2151     for (const MachineOperand &MO : I->operands()) {
2152       if (!MO.isReg() || !MO.getReg())
2153         continue;
2154       if (MO.isDef() && MO.getReg() == BaseReg)
2155         return false;
2156       if (MO.isUse() && MO.getReg() == EntryReg)
2157         RemovableAdd = nullptr;
2158     }
2159   }
2160 
2161   if (RemovableAdd) {
2162     RemovableAdd->eraseFromParent();
2163     DeadSize += isThumb2 ? 4 : 2;
2164   } else if (BaseReg == EntryReg) {
2165     // The add wasn't removable, but clobbered the base for the TBB. So we can't
2166     // preserve it.
2167     return false;
2168   }
2169 
2170   // We reached the end of the block without seeing another definition of
2171   // BaseReg (except, possibly the t2ADDrs, which was removed). BaseReg can be
2172   // used in the TBB/TBH if necessary.
2173   return true;
2174 }
2175 
2176 /// Returns whether CPEMI is the first instruction in the block
2177 /// immediately following JTMI (assumed to be a TBB or TBH terminator). If so,
2178 /// we can switch the first register to PC and usually remove the address
2179 /// calculation that preceded it.
2180 static bool jumpTableFollowsTB(MachineInstr *JTMI, MachineInstr *CPEMI) {
2181   MachineFunction::iterator MBB = JTMI->getParent()->getIterator();
2182   MachineFunction *MF = MBB->getParent();
2183   ++MBB;
2184 
2185   return MBB != MF->end() && !MBB->empty() && &*MBB->begin() == CPEMI;
2186 }
2187 
2188 static void RemoveDeadAddBetweenLEAAndJT(MachineInstr *LEAMI,
2189                                          MachineInstr *JumpMI,
2190                                          unsigned &DeadSize) {
2191   // Remove a dead add between the LEA and JT, which used to compute EntryReg,
2192   // but the JT now uses PC. Finds the last ADD (if any) that def's EntryReg
2193   // and is not clobbered / used.
2194   MachineInstr *RemovableAdd = nullptr;
2195   Register EntryReg = JumpMI->getOperand(0).getReg();
2196 
2197   // Find the last ADD to set EntryReg
2198   MachineBasicBlock::iterator I(LEAMI);
2199   for (++I; &*I != JumpMI; ++I) {
2200     if (I->getOpcode() == ARM::t2ADDrs && I->getOperand(0).getReg() == EntryReg)
2201       RemovableAdd = &*I;
2202   }
2203 
2204   if (!RemovableAdd)
2205     return;
2206 
2207   // Ensure EntryReg is not clobbered or used.
2208   MachineBasicBlock::iterator J(RemovableAdd);
2209   for (++J; &*J != JumpMI; ++J) {
2210     for (const MachineOperand &MO : J->operands()) {
2211       if (!MO.isReg() || !MO.getReg())
2212         continue;
2213       if (MO.isDef() && MO.getReg() == EntryReg)
2214         return;
2215       if (MO.isUse() && MO.getReg() == EntryReg)
2216         return;
2217     }
2218   }
2219 
2220   LLVM_DEBUG(dbgs() << "Removing Dead Add: " << *RemovableAdd);
2221   RemovableAdd->eraseFromParent();
2222   DeadSize += 4;
2223 }
2224 
2225 /// optimizeThumb2JumpTables - Use tbb / tbh instructions to generate smaller
2226 /// jumptables when it's possible.
2227 bool ARMConstantIslands::optimizeThumb2JumpTables() {
2228   bool MadeChange = false;
2229 
2230   // FIXME: After the tables are shrunk, can we get rid some of the
2231   // constantpool tables?
2232   MachineJumpTableInfo *MJTI = MF->getJumpTableInfo();
2233   if (!MJTI) return false;
2234 
2235   const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables();
2236   for (unsigned i = 0, e = T2JumpTables.size(); i != e; ++i) {
2237     MachineInstr *MI = T2JumpTables[i];
2238     const MCInstrDesc &MCID = MI->getDesc();
2239     unsigned NumOps = MCID.getNumOperands();
2240     unsigned JTOpIdx = NumOps - (MI->isPredicable() ? 2 : 1);
2241     MachineOperand JTOP = MI->getOperand(JTOpIdx);
2242     unsigned JTI = JTOP.getIndex();
2243     assert(JTI < JT.size());
2244 
2245     bool ByteOk = true;
2246     bool HalfWordOk = true;
2247     unsigned JTOffset = BBUtils->getOffsetOf(MI) + 4;
2248     const std::vector<MachineBasicBlock*> &JTBBs = JT[JTI].MBBs;
2249     BBInfoVector &BBInfo = BBUtils->getBBInfo();
2250     for (MachineBasicBlock *MBB : JTBBs) {
2251       unsigned DstOffset = BBInfo[MBB->getNumber()].Offset;
2252       // Negative offset is not ok. FIXME: We should change BB layout to make
2253       // sure all the branches are forward.
2254       if (ByteOk && (DstOffset - JTOffset) > ((1<<8)-1)*2)
2255         ByteOk = false;
2256       unsigned TBHLimit = ((1<<16)-1)*2;
2257       if (HalfWordOk && (DstOffset - JTOffset) > TBHLimit)
2258         HalfWordOk = false;
2259       if (!ByteOk && !HalfWordOk)
2260         break;
2261     }
2262 
2263     if (!ByteOk && !HalfWordOk)
2264       continue;
2265 
2266     CPUser &User = CPUsers[JumpTableUserIndices[JTI]];
2267     MachineBasicBlock *MBB = MI->getParent();
2268     if (!MI->getOperand(0).isKill()) // FIXME: needed now?
2269       continue;
2270 
2271     unsigned DeadSize = 0;
2272     bool CanDeleteLEA = false;
2273     bool BaseRegKill = false;
2274 
2275     unsigned IdxReg = ~0U;
2276     bool IdxRegKill = true;
2277     if (isThumb2) {
2278       IdxReg = MI->getOperand(1).getReg();
2279       IdxRegKill = MI->getOperand(1).isKill();
2280 
2281       bool PreservedBaseReg =
2282         preserveBaseRegister(MI, User.MI, DeadSize, CanDeleteLEA, BaseRegKill);
2283       if (!jumpTableFollowsTB(MI, User.CPEMI) && !PreservedBaseReg)
2284         continue;
2285     } else {
2286       // We're in thumb-1 mode, so we must have something like:
2287       //   %idx = tLSLri %idx, 2
2288       //   %base = tLEApcrelJT
2289       //   %t = tLDRr %base, %idx
2290       Register BaseReg = User.MI->getOperand(0).getReg();
2291 
2292       MachineBasicBlock *UserMBB = User.MI->getParent();
2293       MachineBasicBlock::iterator Shift = User.MI->getIterator();
2294       if (Shift == UserMBB->begin())
2295         continue;
2296 
2297       Shift = prev_nodbg(Shift, UserMBB->begin());
2298       if (Shift->getOpcode() != ARM::tLSLri ||
2299           Shift->getOperand(3).getImm() != 2 ||
2300           !Shift->getOperand(2).isKill())
2301         continue;
2302       IdxReg = Shift->getOperand(2).getReg();
2303       Register ShiftedIdxReg = Shift->getOperand(0).getReg();
2304 
2305       // It's important that IdxReg is live until the actual TBB/TBH. Most of
2306       // the range is checked later, but the LEA might still clobber it and not
2307       // actually get removed.
2308       if (BaseReg == IdxReg && !jumpTableFollowsTB(MI, User.CPEMI))
2309         continue;
2310 
2311       MachineInstr *Load = User.MI->getNextNode();
2312       if (Load->getOpcode() != ARM::tLDRr)
2313         continue;
2314       if (Load->getOperand(1).getReg() != BaseReg ||
2315           Load->getOperand(2).getReg() != ShiftedIdxReg ||
2316           !Load->getOperand(2).isKill())
2317         continue;
2318 
2319       // If we're in PIC mode, there should be another ADD following.
2320       auto *TRI = STI->getRegisterInfo();
2321 
2322       // %base cannot be redefined after the load as it will appear before
2323       // TBB/TBH like:
2324       //      %base =
2325       //      %base =
2326       //      tBB %base, %idx
2327       if (registerDefinedBetween(BaseReg, Load->getNextNode(), MBB->end(), TRI))
2328         continue;
2329 
2330       if (isPositionIndependentOrROPI) {
2331         MachineInstr *Add = Load->getNextNode();
2332         if (Add->getOpcode() != ARM::tADDrr ||
2333             Add->getOperand(2).getReg() != BaseReg ||
2334             Add->getOperand(3).getReg() != Load->getOperand(0).getReg() ||
2335             !Add->getOperand(3).isKill())
2336           continue;
2337         if (Add->getOperand(0).getReg() != MI->getOperand(0).getReg())
2338           continue;
2339         if (registerDefinedBetween(IdxReg, Add->getNextNode(), MI, TRI))
2340           // IdxReg gets redefined in the middle of the sequence.
2341           continue;
2342         Add->eraseFromParent();
2343         DeadSize += 2;
2344       } else {
2345         if (Load->getOperand(0).getReg() != MI->getOperand(0).getReg())
2346           continue;
2347         if (registerDefinedBetween(IdxReg, Load->getNextNode(), MI, TRI))
2348           // IdxReg gets redefined in the middle of the sequence.
2349           continue;
2350       }
2351 
2352       // Now safe to delete the load and lsl. The LEA will be removed later.
2353       CanDeleteLEA = true;
2354       Shift->eraseFromParent();
2355       Load->eraseFromParent();
2356       DeadSize += 4;
2357     }
2358 
2359     LLVM_DEBUG(dbgs() << "Shrink JT: " << *MI);
2360     MachineInstr *CPEMI = User.CPEMI;
2361     unsigned Opc = ByteOk ? ARM::t2TBB_JT : ARM::t2TBH_JT;
2362     if (!isThumb2)
2363       Opc = ByteOk ? ARM::tTBB_JT : ARM::tTBH_JT;
2364 
2365     MachineBasicBlock::iterator MI_JT = MI;
2366     MachineInstr *NewJTMI =
2367         BuildMI(*MBB, MI_JT, MI->getDebugLoc(), TII->get(Opc))
2368             .addReg(User.MI->getOperand(0).getReg(),
2369                     getKillRegState(BaseRegKill))
2370             .addReg(IdxReg, getKillRegState(IdxRegKill))
2371             .addJumpTableIndex(JTI, JTOP.getTargetFlags())
2372             .addImm(CPEMI->getOperand(0).getImm());
2373     LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": " << *NewJTMI);
2374 
2375     unsigned JTOpc = ByteOk ? ARM::JUMPTABLE_TBB : ARM::JUMPTABLE_TBH;
2376     CPEMI->setDesc(TII->get(JTOpc));
2377 
2378     if (jumpTableFollowsTB(MI, User.CPEMI)) {
2379       NewJTMI->getOperand(0).setReg(ARM::PC);
2380       NewJTMI->getOperand(0).setIsKill(false);
2381 
2382       if (CanDeleteLEA) {
2383         if (isThumb2)
2384           RemoveDeadAddBetweenLEAAndJT(User.MI, MI, DeadSize);
2385 
2386         User.MI->eraseFromParent();
2387         DeadSize += isThumb2 ? 4 : 2;
2388 
2389         // The LEA was eliminated, the TBB instruction becomes the only new user
2390         // of the jump table.
2391         User.MI = NewJTMI;
2392         User.MaxDisp = 4;
2393         User.NegOk = false;
2394         User.IsSoImm = false;
2395         User.KnownAlignment = false;
2396       } else {
2397         // The LEA couldn't be eliminated, so we must add another CPUser to
2398         // record the TBB or TBH use.
2399         int CPEntryIdx = JumpTableEntryIndices[JTI];
2400         auto &CPEs = CPEntries[CPEntryIdx];
2401         auto Entry =
2402             find_if(CPEs, [&](CPEntry &E) { return E.CPEMI == User.CPEMI; });
2403         ++Entry->RefCount;
2404         CPUsers.emplace_back(CPUser(NewJTMI, User.CPEMI, 4, false, false));
2405       }
2406     }
2407 
2408     unsigned NewSize = TII->getInstSizeInBytes(*NewJTMI);
2409     unsigned OrigSize = TII->getInstSizeInBytes(*MI);
2410     MI->eraseFromParent();
2411 
2412     int Delta = OrigSize - NewSize + DeadSize;
2413     BBInfo[MBB->getNumber()].Size -= Delta;
2414     BBUtils->adjustBBOffsetsAfter(MBB);
2415 
2416     ++NumTBs;
2417     MadeChange = true;
2418   }
2419 
2420   return MadeChange;
2421 }
2422 
2423 /// reorderThumb2JumpTables - Adjust the function's block layout to ensure that
2424 /// jump tables always branch forwards, since that's what tbb and tbh need.
2425 bool ARMConstantIslands::reorderThumb2JumpTables() {
2426   bool MadeChange = false;
2427 
2428   MachineJumpTableInfo *MJTI = MF->getJumpTableInfo();
2429   if (!MJTI) return false;
2430 
2431   const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables();
2432   for (unsigned i = 0, e = T2JumpTables.size(); i != e; ++i) {
2433     MachineInstr *MI = T2JumpTables[i];
2434     const MCInstrDesc &MCID = MI->getDesc();
2435     unsigned NumOps = MCID.getNumOperands();
2436     unsigned JTOpIdx = NumOps - (MI->isPredicable() ? 2 : 1);
2437     MachineOperand JTOP = MI->getOperand(JTOpIdx);
2438     unsigned JTI = JTOP.getIndex();
2439     assert(JTI < JT.size());
2440 
2441     // We prefer if target blocks for the jump table come after the jump
2442     // instruction so we can use TB[BH]. Loop through the target blocks
2443     // and try to adjust them such that that's true.
2444     int JTNumber = MI->getParent()->getNumber();
2445     const std::vector<MachineBasicBlock*> &JTBBs = JT[JTI].MBBs;
2446     for (MachineBasicBlock *MBB : JTBBs) {
2447       int DTNumber = MBB->getNumber();
2448 
2449       if (DTNumber < JTNumber) {
2450         // The destination precedes the switch. Try to move the block forward
2451         // so we have a positive offset.
2452         MachineBasicBlock *NewBB =
2453             adjustJTTargetBlockForward(JTI, MBB, MI->getParent());
2454         if (NewBB)
2455           MJTI->ReplaceMBBInJumpTable(JTI, MBB, NewBB);
2456         MadeChange = true;
2457       }
2458     }
2459   }
2460 
2461   return MadeChange;
2462 }
2463 
2464 MachineBasicBlock *ARMConstantIslands::adjustJTTargetBlockForward(
2465     unsigned JTI, MachineBasicBlock *BB, MachineBasicBlock *JTBB) {
2466   // If the destination block is terminated by an unconditional branch,
2467   // try to move it; otherwise, create a new block following the jump
2468   // table that branches back to the actual target. This is a very simple
2469   // heuristic. FIXME: We can definitely improve it.
2470   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
2471   SmallVector<MachineOperand, 4> Cond;
2472   SmallVector<MachineOperand, 4> CondPrior;
2473   MachineFunction::iterator BBi = BB->getIterator();
2474   MachineFunction::iterator OldPrior = std::prev(BBi);
2475   MachineFunction::iterator OldNext = std::next(BBi);
2476 
2477   // If the block terminator isn't analyzable, don't try to move the block
2478   bool B = TII->analyzeBranch(*BB, TBB, FBB, Cond);
2479 
2480   // If the block ends in an unconditional branch, move it. The prior block
2481   // has to have an analyzable terminator for us to move this one. Be paranoid
2482   // and make sure we're not trying to move the entry block of the function.
2483   if (!B && Cond.empty() && BB != &MF->front() &&
2484       !TII->analyzeBranch(*OldPrior, TBB, FBB, CondPrior)) {
2485     BB->moveAfter(JTBB);
2486     OldPrior->updateTerminator(BB);
2487     BB->updateTerminator(OldNext != MF->end() ? &*OldNext : nullptr);
2488     // Update numbering to account for the block being moved.
2489     MF->RenumberBlocks();
2490     ++NumJTMoved;
2491     return nullptr;
2492   }
2493 
2494   // Create a new MBB for the code after the jump BB.
2495   MachineBasicBlock *NewBB =
2496     MF->CreateMachineBasicBlock(JTBB->getBasicBlock());
2497   MachineFunction::iterator MBBI = ++JTBB->getIterator();
2498   MF->insert(MBBI, NewBB);
2499 
2500   // Copy live-in information to new block.
2501   for (const MachineBasicBlock::RegisterMaskPair &RegMaskPair : BB->liveins())
2502     NewBB->addLiveIn(RegMaskPair);
2503 
2504   // Add an unconditional branch from NewBB to BB.
2505   // There doesn't seem to be meaningful DebugInfo available; this doesn't
2506   // correspond directly to anything in the source.
2507   if (isThumb2)
2508     BuildMI(NewBB, DebugLoc(), TII->get(ARM::t2B))
2509         .addMBB(BB)
2510         .add(predOps(ARMCC::AL));
2511   else
2512     BuildMI(NewBB, DebugLoc(), TII->get(ARM::tB))
2513         .addMBB(BB)
2514         .add(predOps(ARMCC::AL));
2515 
2516   // Update internal data structures to account for the newly inserted MBB.
2517   MF->RenumberBlocks(NewBB);
2518 
2519   // Update the CFG.
2520   NewBB->addSuccessor(BB);
2521   JTBB->replaceSuccessor(BB, NewBB);
2522 
2523   ++NumJTInserted;
2524   return NewBB;
2525 }
2526 
2527 /// createARMConstantIslandPass - returns an instance of the constpool
2528 /// island pass.
2529 FunctionPass *llvm::createARMConstantIslandPass() {
2530   return new ARMConstantIslands();
2531 }
2532 
2533 INITIALIZE_PASS(ARMConstantIslands, "arm-cp-islands", ARM_CP_ISLANDS_OPT_NAME,
2534                 false, false)
2535