xref: /freebsd-src/contrib/llvm-project/llvm/lib/Target/CSKY/CSKYConstantIslandPass.cpp (revision 04eeddc0aa8e0a417a16eaf9d7d095207f4a8623)
1*04eeddc0SDimitry Andric //===- CSKYConstantIslandPass.cpp - Emit PC Relative loads ----------------===//
2*04eeddc0SDimitry Andric //
3*04eeddc0SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4*04eeddc0SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
5*04eeddc0SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6*04eeddc0SDimitry Andric //
7*04eeddc0SDimitry Andric //===----------------------------------------------------------------------===//
8*04eeddc0SDimitry Andric //
9*04eeddc0SDimitry Andric //
10*04eeddc0SDimitry Andric // Loading constants inline is expensive on CSKY and it's in general better
11*04eeddc0SDimitry Andric // to place the constant nearby in code space and then it can be loaded with a
12*04eeddc0SDimitry Andric // simple 16/32 bit load instruction like lrw.
13*04eeddc0SDimitry Andric //
14*04eeddc0SDimitry Andric // The constants can be not just numbers but addresses of functions and labels.
15*04eeddc0SDimitry Andric // This can be particularly helpful in static relocation mode for embedded
16*04eeddc0SDimitry Andric // non-linux targets.
17*04eeddc0SDimitry Andric //
18*04eeddc0SDimitry Andric //===----------------------------------------------------------------------===//
19*04eeddc0SDimitry Andric 
20*04eeddc0SDimitry Andric #include "CSKY.h"
21*04eeddc0SDimitry Andric #include "CSKYConstantPoolValue.h"
22*04eeddc0SDimitry Andric #include "CSKYMachineFunctionInfo.h"
23*04eeddc0SDimitry Andric #include "CSKYSubtarget.h"
24*04eeddc0SDimitry Andric #include "llvm/ADT/STLExtras.h"
25*04eeddc0SDimitry Andric #include "llvm/ADT/SmallSet.h"
26*04eeddc0SDimitry Andric #include "llvm/ADT/SmallVector.h"
27*04eeddc0SDimitry Andric #include "llvm/ADT/Statistic.h"
28*04eeddc0SDimitry Andric #include "llvm/ADT/StringRef.h"
29*04eeddc0SDimitry Andric #include "llvm/CodeGen/MachineBasicBlock.h"
30*04eeddc0SDimitry Andric #include "llvm/CodeGen/MachineConstantPool.h"
31*04eeddc0SDimitry Andric #include "llvm/CodeGen/MachineDominators.h"
32*04eeddc0SDimitry Andric #include "llvm/CodeGen/MachineFunction.h"
33*04eeddc0SDimitry Andric #include "llvm/CodeGen/MachineFunctionPass.h"
34*04eeddc0SDimitry Andric #include "llvm/CodeGen/MachineInstr.h"
35*04eeddc0SDimitry Andric #include "llvm/CodeGen/MachineInstrBuilder.h"
36*04eeddc0SDimitry Andric #include "llvm/CodeGen/MachineOperand.h"
37*04eeddc0SDimitry Andric #include "llvm/CodeGen/MachineRegisterInfo.h"
38*04eeddc0SDimitry Andric #include "llvm/Config/llvm-config.h"
39*04eeddc0SDimitry Andric #include "llvm/IR/Constants.h"
40*04eeddc0SDimitry Andric #include "llvm/IR/DataLayout.h"
41*04eeddc0SDimitry Andric #include "llvm/IR/DebugLoc.h"
42*04eeddc0SDimitry Andric #include "llvm/IR/Function.h"
43*04eeddc0SDimitry Andric #include "llvm/IR/Type.h"
44*04eeddc0SDimitry Andric #include "llvm/Support/CommandLine.h"
45*04eeddc0SDimitry Andric #include "llvm/Support/Compiler.h"
46*04eeddc0SDimitry Andric #include "llvm/Support/Debug.h"
47*04eeddc0SDimitry Andric #include "llvm/Support/ErrorHandling.h"
48*04eeddc0SDimitry Andric #include "llvm/Support/Format.h"
49*04eeddc0SDimitry Andric #include "llvm/Support/MathExtras.h"
50*04eeddc0SDimitry Andric #include "llvm/Support/raw_ostream.h"
51*04eeddc0SDimitry Andric #include <algorithm>
52*04eeddc0SDimitry Andric #include <cassert>
53*04eeddc0SDimitry Andric #include <cstdint>
54*04eeddc0SDimitry Andric #include <iterator>
55*04eeddc0SDimitry Andric #include <vector>
56*04eeddc0SDimitry Andric 
57*04eeddc0SDimitry Andric using namespace llvm;
58*04eeddc0SDimitry Andric 
59*04eeddc0SDimitry Andric #define DEBUG_TYPE "CSKY-constant-islands"
60*04eeddc0SDimitry Andric 
61*04eeddc0SDimitry Andric STATISTIC(NumCPEs, "Number of constpool entries");
62*04eeddc0SDimitry Andric STATISTIC(NumSplit, "Number of uncond branches inserted");
63*04eeddc0SDimitry Andric STATISTIC(NumCBrFixed, "Number of cond branches fixed");
64*04eeddc0SDimitry Andric STATISTIC(NumUBrFixed, "Number of uncond branches fixed");
65*04eeddc0SDimitry Andric 
66*04eeddc0SDimitry Andric namespace {
67*04eeddc0SDimitry Andric 
68*04eeddc0SDimitry Andric using Iter = MachineBasicBlock::iterator;
69*04eeddc0SDimitry Andric using ReverseIter = MachineBasicBlock::reverse_iterator;
70*04eeddc0SDimitry Andric 
71*04eeddc0SDimitry Andric /// CSKYConstantIslands - Due to limited PC-relative displacements, CSKY
72*04eeddc0SDimitry Andric /// requires constant pool entries to be scattered among the instructions
73*04eeddc0SDimitry Andric /// inside a function.  To do this, it completely ignores the normal LLVM
74*04eeddc0SDimitry Andric /// constant pool; instead, it places constants wherever it feels like with
75*04eeddc0SDimitry Andric /// special instructions.
76*04eeddc0SDimitry Andric ///
77*04eeddc0SDimitry Andric /// The terminology used in this pass includes:
78*04eeddc0SDimitry Andric ///   Islands - Clumps of constants placed in the function.
79*04eeddc0SDimitry Andric ///   Water   - Potential places where an island could be formed.
80*04eeddc0SDimitry Andric ///   CPE     - A constant pool entry that has been placed somewhere, which
81*04eeddc0SDimitry Andric ///             tracks a list of users.
82*04eeddc0SDimitry Andric 
83*04eeddc0SDimitry Andric class CSKYConstantIslands : public MachineFunctionPass {
84*04eeddc0SDimitry Andric   /// BasicBlockInfo - Information about the offset and size of a single
85*04eeddc0SDimitry Andric   /// basic block.
86*04eeddc0SDimitry Andric   struct BasicBlockInfo {
87*04eeddc0SDimitry Andric     /// Offset - Distance from the beginning of the function to the beginning
88*04eeddc0SDimitry Andric     /// of this basic block.
89*04eeddc0SDimitry Andric     ///
90*04eeddc0SDimitry Andric     /// Offsets are computed assuming worst case padding before an aligned
91*04eeddc0SDimitry Andric     /// block. This means that subtracting basic block offsets always gives a
92*04eeddc0SDimitry Andric     /// conservative estimate of the real distance which may be smaller.
93*04eeddc0SDimitry Andric     ///
94*04eeddc0SDimitry Andric     /// Because worst case padding is used, the computed offset of an aligned
95*04eeddc0SDimitry Andric     /// block may not actually be aligned.
96*04eeddc0SDimitry Andric     unsigned Offset = 0;
97*04eeddc0SDimitry Andric 
98*04eeddc0SDimitry Andric     /// Size - Size of the basic block in bytes.  If the block contains
99*04eeddc0SDimitry Andric     /// inline assembly, this is a worst case estimate.
100*04eeddc0SDimitry Andric     ///
101*04eeddc0SDimitry Andric     /// The size does not include any alignment padding whether from the
102*04eeddc0SDimitry Andric     /// beginning of the block, or from an aligned jump table at the end.
103*04eeddc0SDimitry Andric     unsigned Size = 0;
104*04eeddc0SDimitry Andric 
105*04eeddc0SDimitry Andric     BasicBlockInfo() = default;
106*04eeddc0SDimitry Andric 
107*04eeddc0SDimitry Andric     unsigned postOffset() const { return Offset + Size; }
108*04eeddc0SDimitry Andric   };
109*04eeddc0SDimitry Andric 
110*04eeddc0SDimitry Andric   std::vector<BasicBlockInfo> BBInfo;
111*04eeddc0SDimitry Andric 
112*04eeddc0SDimitry Andric   /// WaterList - A sorted list of basic blocks where islands could be placed
113*04eeddc0SDimitry Andric   /// (i.e. blocks that don't fall through to the following block, due
114*04eeddc0SDimitry Andric   /// to a return, unreachable, or unconditional branch).
115*04eeddc0SDimitry Andric   std::vector<MachineBasicBlock *> WaterList;
116*04eeddc0SDimitry Andric 
117*04eeddc0SDimitry Andric   /// NewWaterList - The subset of WaterList that was created since the
118*04eeddc0SDimitry Andric   /// previous iteration by inserting unconditional branches.
119*04eeddc0SDimitry Andric   SmallSet<MachineBasicBlock *, 4> NewWaterList;
120*04eeddc0SDimitry Andric 
121*04eeddc0SDimitry Andric   using water_iterator = std::vector<MachineBasicBlock *>::iterator;
122*04eeddc0SDimitry Andric 
123*04eeddc0SDimitry Andric   /// CPUser - One user of a constant pool, keeping the machine instruction
124*04eeddc0SDimitry Andric   /// pointer, the constant pool being referenced, and the max displacement
125*04eeddc0SDimitry Andric   /// allowed from the instruction to the CP.  The HighWaterMark records the
126*04eeddc0SDimitry Andric   /// highest basic block where a new CPEntry can be placed.  To ensure this
127*04eeddc0SDimitry Andric   /// pass terminates, the CP entries are initially placed at the end of the
128*04eeddc0SDimitry Andric   /// function and then move monotonically to lower addresses.  The
129*04eeddc0SDimitry Andric   /// exception to this rule is when the current CP entry for a particular
130*04eeddc0SDimitry Andric   /// CPUser is out of range, but there is another CP entry for the same
131*04eeddc0SDimitry Andric   /// constant value in range.  We want to use the existing in-range CP
132*04eeddc0SDimitry Andric   /// entry, but if it later moves out of range, the search for new water
133*04eeddc0SDimitry Andric   /// should resume where it left off.  The HighWaterMark is used to record
134*04eeddc0SDimitry Andric   /// that point.
135*04eeddc0SDimitry Andric   struct CPUser {
136*04eeddc0SDimitry Andric     MachineInstr *MI;
137*04eeddc0SDimitry Andric     MachineInstr *CPEMI;
138*04eeddc0SDimitry Andric     MachineBasicBlock *HighWaterMark;
139*04eeddc0SDimitry Andric 
140*04eeddc0SDimitry Andric   private:
141*04eeddc0SDimitry Andric     unsigned MaxDisp;
142*04eeddc0SDimitry Andric 
143*04eeddc0SDimitry Andric   public:
144*04eeddc0SDimitry Andric     bool NegOk;
145*04eeddc0SDimitry Andric 
146*04eeddc0SDimitry Andric     CPUser(MachineInstr *Mi, MachineInstr *Cpemi, unsigned Maxdisp, bool Neg)
147*04eeddc0SDimitry Andric         : MI(Mi), CPEMI(Cpemi), MaxDisp(Maxdisp), NegOk(Neg) {
148*04eeddc0SDimitry Andric       HighWaterMark = CPEMI->getParent();
149*04eeddc0SDimitry Andric     }
150*04eeddc0SDimitry Andric 
151*04eeddc0SDimitry Andric     /// getMaxDisp - Returns the maximum displacement supported by MI.
152*04eeddc0SDimitry Andric     unsigned getMaxDisp() const { return MaxDisp - 16; }
153*04eeddc0SDimitry Andric 
154*04eeddc0SDimitry Andric     void setMaxDisp(unsigned Val) { MaxDisp = Val; }
155*04eeddc0SDimitry Andric   };
156*04eeddc0SDimitry Andric 
157*04eeddc0SDimitry Andric   /// CPUsers - Keep track of all of the machine instructions that use various
158*04eeddc0SDimitry Andric   /// constant pools and their max displacement.
159*04eeddc0SDimitry Andric   std::vector<CPUser> CPUsers;
160*04eeddc0SDimitry Andric 
161*04eeddc0SDimitry Andric   /// CPEntry - One per constant pool entry, keeping the machine instruction
162*04eeddc0SDimitry Andric   /// pointer, the constpool index, and the number of CPUser's which
163*04eeddc0SDimitry Andric   /// reference this entry.
164*04eeddc0SDimitry Andric   struct CPEntry {
165*04eeddc0SDimitry Andric     MachineInstr *CPEMI;
166*04eeddc0SDimitry Andric     unsigned CPI;
167*04eeddc0SDimitry Andric     unsigned RefCount;
168*04eeddc0SDimitry Andric 
169*04eeddc0SDimitry Andric     CPEntry(MachineInstr *Cpemi, unsigned Cpi, unsigned Rc = 0)
170*04eeddc0SDimitry Andric         : CPEMI(Cpemi), CPI(Cpi), RefCount(Rc) {}
171*04eeddc0SDimitry Andric   };
172*04eeddc0SDimitry Andric 
173*04eeddc0SDimitry Andric   /// CPEntries - Keep track of all of the constant pool entry machine
174*04eeddc0SDimitry Andric   /// instructions. For each original constpool index (i.e. those that
175*04eeddc0SDimitry Andric   /// existed upon entry to this pass), it keeps a vector of entries.
176*04eeddc0SDimitry Andric   /// Original elements are cloned as we go along; the clones are
177*04eeddc0SDimitry Andric   /// put in the vector of the original element, but have distinct CPIs.
178*04eeddc0SDimitry Andric   std::vector<std::vector<CPEntry>> CPEntries;
179*04eeddc0SDimitry Andric 
180*04eeddc0SDimitry Andric   /// ImmBranch - One per immediate branch, keeping the machine instruction
181*04eeddc0SDimitry Andric   /// pointer, conditional or unconditional, the max displacement,
182*04eeddc0SDimitry Andric   /// and (if isCond is true) the corresponding unconditional branch
183*04eeddc0SDimitry Andric   /// opcode.
184*04eeddc0SDimitry Andric   struct ImmBranch {
185*04eeddc0SDimitry Andric     MachineInstr *MI;
186*04eeddc0SDimitry Andric     unsigned MaxDisp : 31;
187*04eeddc0SDimitry Andric     bool IsCond : 1;
188*04eeddc0SDimitry Andric     int UncondBr;
189*04eeddc0SDimitry Andric 
190*04eeddc0SDimitry Andric     ImmBranch(MachineInstr *Mi, unsigned Maxdisp, bool Cond, int Ubr)
191*04eeddc0SDimitry Andric         : MI(Mi), MaxDisp(Maxdisp), IsCond(Cond), UncondBr(Ubr) {}
192*04eeddc0SDimitry Andric   };
193*04eeddc0SDimitry Andric 
194*04eeddc0SDimitry Andric   /// ImmBranches - Keep track of all the immediate branch instructions.
195*04eeddc0SDimitry Andric   ///
196*04eeddc0SDimitry Andric   std::vector<ImmBranch> ImmBranches;
197*04eeddc0SDimitry Andric 
198*04eeddc0SDimitry Andric   const CSKYSubtarget *STI = nullptr;
199*04eeddc0SDimitry Andric   const CSKYInstrInfo *TII;
200*04eeddc0SDimitry Andric   CSKYMachineFunctionInfo *MFI;
201*04eeddc0SDimitry Andric   MachineFunction *MF = nullptr;
202*04eeddc0SDimitry Andric   MachineConstantPool *MCP = nullptr;
203*04eeddc0SDimitry Andric 
204*04eeddc0SDimitry Andric   unsigned PICLabelUId;
205*04eeddc0SDimitry Andric 
206*04eeddc0SDimitry Andric   void initPICLabelUId(unsigned UId) { PICLabelUId = UId; }
207*04eeddc0SDimitry Andric 
208*04eeddc0SDimitry Andric   unsigned createPICLabelUId() { return PICLabelUId++; }
209*04eeddc0SDimitry Andric 
210*04eeddc0SDimitry Andric public:
211*04eeddc0SDimitry Andric   static char ID;
212*04eeddc0SDimitry Andric 
213*04eeddc0SDimitry Andric   CSKYConstantIslands() : MachineFunctionPass(ID) {}
214*04eeddc0SDimitry Andric 
215*04eeddc0SDimitry Andric   StringRef getPassName() const override { return "CSKY Constant Islands"; }
216*04eeddc0SDimitry Andric 
217*04eeddc0SDimitry Andric   bool runOnMachineFunction(MachineFunction &F) override;
218*04eeddc0SDimitry Andric 
219*04eeddc0SDimitry Andric   void getAnalysisUsage(AnalysisUsage &AU) const override {
220*04eeddc0SDimitry Andric     AU.addRequired<MachineDominatorTree>();
221*04eeddc0SDimitry Andric     MachineFunctionPass::getAnalysisUsage(AU);
222*04eeddc0SDimitry Andric   }
223*04eeddc0SDimitry Andric 
224*04eeddc0SDimitry Andric   MachineFunctionProperties getRequiredProperties() const override {
225*04eeddc0SDimitry Andric     return MachineFunctionProperties().set(
226*04eeddc0SDimitry Andric         MachineFunctionProperties::Property::NoVRegs);
227*04eeddc0SDimitry Andric   }
228*04eeddc0SDimitry Andric 
229*04eeddc0SDimitry Andric   void doInitialPlacement(std::vector<MachineInstr *> &CPEMIs);
230*04eeddc0SDimitry Andric   CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI);
231*04eeddc0SDimitry Andric   Align getCPEAlign(const MachineInstr &CPEMI);
232*04eeddc0SDimitry Andric   void initializeFunctionInfo(const std::vector<MachineInstr *> &CPEMIs);
233*04eeddc0SDimitry Andric   unsigned getOffsetOf(MachineInstr *MI) const;
234*04eeddc0SDimitry Andric   unsigned getUserOffset(CPUser &) const;
235*04eeddc0SDimitry Andric   void dumpBBs();
236*04eeddc0SDimitry Andric 
237*04eeddc0SDimitry Andric   bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset, unsigned Disp,
238*04eeddc0SDimitry Andric                        bool NegativeOK);
239*04eeddc0SDimitry Andric   bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset,
240*04eeddc0SDimitry Andric                        const CPUser &U);
241*04eeddc0SDimitry Andric 
242*04eeddc0SDimitry Andric   void computeBlockSize(MachineBasicBlock *MBB);
243*04eeddc0SDimitry Andric   MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI);
244*04eeddc0SDimitry Andric   void updateForInsertedWaterBlock(MachineBasicBlock *NewBB);
245*04eeddc0SDimitry Andric   void adjustBBOffsetsAfter(MachineBasicBlock *BB);
246*04eeddc0SDimitry Andric   bool decrementCPEReferenceCount(unsigned CPI, MachineInstr *CPEMI);
247*04eeddc0SDimitry Andric   int findInRangeCPEntry(CPUser &U, unsigned UserOffset);
248*04eeddc0SDimitry Andric   bool findAvailableWater(CPUser &U, unsigned UserOffset,
249*04eeddc0SDimitry Andric                           water_iterator &WaterIter);
250*04eeddc0SDimitry Andric   void createNewWater(unsigned CPUserIndex, unsigned UserOffset,
251*04eeddc0SDimitry Andric                       MachineBasicBlock *&NewMBB);
252*04eeddc0SDimitry Andric   bool handleConstantPoolUser(unsigned CPUserIndex);
253*04eeddc0SDimitry Andric   void removeDeadCPEMI(MachineInstr *CPEMI);
254*04eeddc0SDimitry Andric   bool removeUnusedCPEntries();
255*04eeddc0SDimitry Andric   bool isCPEntryInRange(MachineInstr *MI, unsigned UserOffset,
256*04eeddc0SDimitry Andric                         MachineInstr *CPEMI, unsigned Disp, bool NegOk,
257*04eeddc0SDimitry Andric                         bool DoDump = false);
258*04eeddc0SDimitry Andric   bool isWaterInRange(unsigned UserOffset, MachineBasicBlock *Water, CPUser &U,
259*04eeddc0SDimitry Andric                       unsigned &Growth);
260*04eeddc0SDimitry Andric   bool isBBInRange(MachineInstr *MI, MachineBasicBlock *BB, unsigned Disp);
261*04eeddc0SDimitry Andric   bool fixupImmediateBr(ImmBranch &Br);
262*04eeddc0SDimitry Andric   bool fixupConditionalBr(ImmBranch &Br);
263*04eeddc0SDimitry Andric   bool fixupUnconditionalBr(ImmBranch &Br);
264*04eeddc0SDimitry Andric };
265*04eeddc0SDimitry Andric } // end anonymous namespace
266*04eeddc0SDimitry Andric 
267*04eeddc0SDimitry Andric char CSKYConstantIslands::ID = 0;
268*04eeddc0SDimitry Andric 
269*04eeddc0SDimitry Andric bool CSKYConstantIslands::isOffsetInRange(unsigned UserOffset,
270*04eeddc0SDimitry Andric                                           unsigned TrialOffset,
271*04eeddc0SDimitry Andric                                           const CPUser &U) {
272*04eeddc0SDimitry Andric   return isOffsetInRange(UserOffset, TrialOffset, U.getMaxDisp(), U.NegOk);
273*04eeddc0SDimitry Andric }
274*04eeddc0SDimitry Andric 
275*04eeddc0SDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
276*04eeddc0SDimitry Andric /// print block size and offset information - debugging
277*04eeddc0SDimitry Andric LLVM_DUMP_METHOD void CSKYConstantIslands::dumpBBs() {
278*04eeddc0SDimitry Andric   for (unsigned J = 0, E = BBInfo.size(); J != E; ++J) {
279*04eeddc0SDimitry Andric     const BasicBlockInfo &BBI = BBInfo[J];
280*04eeddc0SDimitry Andric     dbgs() << format("%08x %bb.%u\t", BBI.Offset, J)
281*04eeddc0SDimitry Andric            << format(" size=%#x\n", BBInfo[J].Size);
282*04eeddc0SDimitry Andric   }
283*04eeddc0SDimitry Andric }
284*04eeddc0SDimitry Andric #endif
285*04eeddc0SDimitry Andric 
286*04eeddc0SDimitry Andric bool CSKYConstantIslands::runOnMachineFunction(MachineFunction &Mf) {
287*04eeddc0SDimitry Andric   MF = &Mf;
288*04eeddc0SDimitry Andric   MCP = Mf.getConstantPool();
289*04eeddc0SDimitry Andric   STI = &static_cast<const CSKYSubtarget &>(Mf.getSubtarget());
290*04eeddc0SDimitry Andric 
291*04eeddc0SDimitry Andric   LLVM_DEBUG(dbgs() << "***** CSKYConstantIslands: "
292*04eeddc0SDimitry Andric                     << MCP->getConstants().size() << " CP entries, aligned to "
293*04eeddc0SDimitry Andric                     << MCP->getConstantPoolAlign().value() << " bytes *****\n");
294*04eeddc0SDimitry Andric 
295*04eeddc0SDimitry Andric   TII = STI->getInstrInfo();
296*04eeddc0SDimitry Andric   MFI = MF->getInfo<CSKYMachineFunctionInfo>();
297*04eeddc0SDimitry Andric 
298*04eeddc0SDimitry Andric   // This pass invalidates liveness information when it splits basic blocks.
299*04eeddc0SDimitry Andric   MF->getRegInfo().invalidateLiveness();
300*04eeddc0SDimitry Andric 
301*04eeddc0SDimitry Andric   // Renumber all of the machine basic blocks in the function, guaranteeing that
302*04eeddc0SDimitry Andric   // the numbers agree with the position of the block in the function.
303*04eeddc0SDimitry Andric   MF->RenumberBlocks();
304*04eeddc0SDimitry Andric 
305*04eeddc0SDimitry Andric   bool MadeChange = false;
306*04eeddc0SDimitry Andric 
307*04eeddc0SDimitry Andric   // Perform the initial placement of the constant pool entries.  To start with,
308*04eeddc0SDimitry Andric   // we put them all at the end of the function.
309*04eeddc0SDimitry Andric   std::vector<MachineInstr *> CPEMIs;
310*04eeddc0SDimitry Andric   if (!MCP->isEmpty())
311*04eeddc0SDimitry Andric     doInitialPlacement(CPEMIs);
312*04eeddc0SDimitry Andric 
313*04eeddc0SDimitry Andric   /// The next UID to take is the first unused one.
314*04eeddc0SDimitry Andric   initPICLabelUId(CPEMIs.size());
315*04eeddc0SDimitry Andric 
316*04eeddc0SDimitry Andric   // Do the initial scan of the function, building up information about the
317*04eeddc0SDimitry Andric   // sizes of each block, the location of all the water, and finding all of the
318*04eeddc0SDimitry Andric   // constant pool users.
319*04eeddc0SDimitry Andric   initializeFunctionInfo(CPEMIs);
320*04eeddc0SDimitry Andric   CPEMIs.clear();
321*04eeddc0SDimitry Andric   LLVM_DEBUG(dumpBBs());
322*04eeddc0SDimitry Andric 
323*04eeddc0SDimitry Andric   /// Remove dead constant pool entries.
324*04eeddc0SDimitry Andric   MadeChange |= removeUnusedCPEntries();
325*04eeddc0SDimitry Andric 
326*04eeddc0SDimitry Andric   // Iteratively place constant pool entries and fix up branches until there
327*04eeddc0SDimitry Andric   // is no change.
328*04eeddc0SDimitry Andric   unsigned NoCPIters = 0, NoBRIters = 0;
329*04eeddc0SDimitry Andric   (void)NoBRIters;
330*04eeddc0SDimitry Andric   while (true) {
331*04eeddc0SDimitry Andric     LLVM_DEBUG(dbgs() << "Beginning CP iteration #" << NoCPIters << '\n');
332*04eeddc0SDimitry Andric     bool CPChange = false;
333*04eeddc0SDimitry Andric     for (unsigned I = 0, E = CPUsers.size(); I != E; ++I)
334*04eeddc0SDimitry Andric       CPChange |= handleConstantPoolUser(I);
335*04eeddc0SDimitry Andric     if (CPChange && ++NoCPIters > 30)
336*04eeddc0SDimitry Andric       report_fatal_error("Constant Island pass failed to converge!");
337*04eeddc0SDimitry Andric     LLVM_DEBUG(dumpBBs());
338*04eeddc0SDimitry Andric 
339*04eeddc0SDimitry Andric     // Clear NewWaterList now.  If we split a block for branches, it should
340*04eeddc0SDimitry Andric     // appear as "new water" for the next iteration of constant pool placement.
341*04eeddc0SDimitry Andric     NewWaterList.clear();
342*04eeddc0SDimitry Andric 
343*04eeddc0SDimitry Andric     LLVM_DEBUG(dbgs() << "Beginning BR iteration #" << NoBRIters << '\n');
344*04eeddc0SDimitry Andric     bool BRChange = false;
345*04eeddc0SDimitry Andric     for (unsigned I = 0, E = ImmBranches.size(); I != E; ++I)
346*04eeddc0SDimitry Andric       BRChange |= fixupImmediateBr(ImmBranches[I]);
347*04eeddc0SDimitry Andric     if (BRChange && ++NoBRIters > 30)
348*04eeddc0SDimitry Andric       report_fatal_error("Branch Fix Up pass failed to converge!");
349*04eeddc0SDimitry Andric     LLVM_DEBUG(dumpBBs());
350*04eeddc0SDimitry Andric     if (!CPChange && !BRChange)
351*04eeddc0SDimitry Andric       break;
352*04eeddc0SDimitry Andric     MadeChange = true;
353*04eeddc0SDimitry Andric   }
354*04eeddc0SDimitry Andric 
355*04eeddc0SDimitry Andric   LLVM_DEBUG(dbgs() << '\n'; dumpBBs());
356*04eeddc0SDimitry Andric 
357*04eeddc0SDimitry Andric   BBInfo.clear();
358*04eeddc0SDimitry Andric   WaterList.clear();
359*04eeddc0SDimitry Andric   CPUsers.clear();
360*04eeddc0SDimitry Andric   CPEntries.clear();
361*04eeddc0SDimitry Andric   ImmBranches.clear();
362*04eeddc0SDimitry Andric   return MadeChange;
363*04eeddc0SDimitry Andric }
364*04eeddc0SDimitry Andric 
365*04eeddc0SDimitry Andric /// doInitialPlacement - Perform the initial placement of the constant pool
366*04eeddc0SDimitry Andric /// entries.  To start with, we put them all at the end of the function.
367*04eeddc0SDimitry Andric void CSKYConstantIslands::doInitialPlacement(
368*04eeddc0SDimitry Andric     std::vector<MachineInstr *> &CPEMIs) {
369*04eeddc0SDimitry Andric   // Create the basic block to hold the CPE's.
370*04eeddc0SDimitry Andric   MachineBasicBlock *BB = MF->CreateMachineBasicBlock();
371*04eeddc0SDimitry Andric   MF->push_back(BB);
372*04eeddc0SDimitry Andric 
373*04eeddc0SDimitry Andric   // MachineConstantPool measures alignment in bytes. We measure in log2(bytes).
374*04eeddc0SDimitry Andric   const Align MaxAlign = MCP->getConstantPoolAlign();
375*04eeddc0SDimitry Andric 
376*04eeddc0SDimitry Andric   // Mark the basic block as required by the const-pool.
377*04eeddc0SDimitry Andric   BB->setAlignment(Align(2));
378*04eeddc0SDimitry Andric 
379*04eeddc0SDimitry Andric   // The function needs to be as aligned as the basic blocks. The linker may
380*04eeddc0SDimitry Andric   // move functions around based on their alignment.
381*04eeddc0SDimitry Andric   MF->ensureAlignment(BB->getAlignment());
382*04eeddc0SDimitry Andric 
383*04eeddc0SDimitry Andric   // Order the entries in BB by descending alignment.  That ensures correct
384*04eeddc0SDimitry Andric   // alignment of all entries as long as BB is sufficiently aligned.  Keep
385*04eeddc0SDimitry Andric   // track of the insertion point for each alignment.  We are going to bucket
386*04eeddc0SDimitry Andric   // sort the entries as they are created.
387*04eeddc0SDimitry Andric   SmallVector<MachineBasicBlock::iterator, 8> InsPoint(Log2(MaxAlign) + 1,
388*04eeddc0SDimitry Andric                                                        BB->end());
389*04eeddc0SDimitry Andric 
390*04eeddc0SDimitry Andric   // Add all of the constants from the constant pool to the end block, use an
391*04eeddc0SDimitry Andric   // identity mapping of CPI's to CPE's.
392*04eeddc0SDimitry Andric   const std::vector<MachineConstantPoolEntry> &CPs = MCP->getConstants();
393*04eeddc0SDimitry Andric 
394*04eeddc0SDimitry Andric   const DataLayout &TD = MF->getDataLayout();
395*04eeddc0SDimitry Andric   for (unsigned I = 0, E = CPs.size(); I != E; ++I) {
396*04eeddc0SDimitry Andric     unsigned Size = CPs[I].getSizeInBytes(TD);
397*04eeddc0SDimitry Andric     assert(Size >= 4 && "Too small constant pool entry");
398*04eeddc0SDimitry Andric     Align Alignment = CPs[I].getAlign();
399*04eeddc0SDimitry Andric     // Verify that all constant pool entries are a multiple of their alignment.
400*04eeddc0SDimitry Andric     // If not, we would have to pad them out so that instructions stay aligned.
401*04eeddc0SDimitry Andric     assert(isAligned(Alignment, Size) && "CP Entry not multiple of 4 bytes!");
402*04eeddc0SDimitry Andric 
403*04eeddc0SDimitry Andric     // Insert CONSTPOOL_ENTRY before entries with a smaller alignment.
404*04eeddc0SDimitry Andric     unsigned LogAlign = Log2(Alignment);
405*04eeddc0SDimitry Andric     MachineBasicBlock::iterator InsAt = InsPoint[LogAlign];
406*04eeddc0SDimitry Andric 
407*04eeddc0SDimitry Andric     MachineInstr *CPEMI =
408*04eeddc0SDimitry Andric         BuildMI(*BB, InsAt, DebugLoc(), TII->get(CSKY::CONSTPOOL_ENTRY))
409*04eeddc0SDimitry Andric             .addImm(I)
410*04eeddc0SDimitry Andric             .addConstantPoolIndex(I)
411*04eeddc0SDimitry Andric             .addImm(Size);
412*04eeddc0SDimitry Andric 
413*04eeddc0SDimitry Andric     CPEMIs.push_back(CPEMI);
414*04eeddc0SDimitry Andric 
415*04eeddc0SDimitry Andric     // Ensure that future entries with higher alignment get inserted before
416*04eeddc0SDimitry Andric     // CPEMI. This is bucket sort with iterators.
417*04eeddc0SDimitry Andric     for (unsigned A = LogAlign + 1; A <= Log2(MaxAlign); ++A)
418*04eeddc0SDimitry Andric       if (InsPoint[A] == InsAt)
419*04eeddc0SDimitry Andric         InsPoint[A] = CPEMI;
420*04eeddc0SDimitry Andric     // Add a new CPEntry, but no corresponding CPUser yet.
421*04eeddc0SDimitry Andric     CPEntries.emplace_back(1, CPEntry(CPEMI, I));
422*04eeddc0SDimitry Andric     ++NumCPEs;
423*04eeddc0SDimitry Andric     LLVM_DEBUG(dbgs() << "Moved CPI#" << I << " to end of function, size = "
424*04eeddc0SDimitry Andric                       << Size << ", align = " << Alignment.value() << '\n');
425*04eeddc0SDimitry Andric   }
426*04eeddc0SDimitry Andric   LLVM_DEBUG(BB->dump());
427*04eeddc0SDimitry Andric }
428*04eeddc0SDimitry Andric 
429*04eeddc0SDimitry Andric /// BBHasFallthrough - Return true if the specified basic block can fallthrough
430*04eeddc0SDimitry Andric /// into the block immediately after it.
431*04eeddc0SDimitry Andric static bool bbHasFallthrough(MachineBasicBlock *MBB) {
432*04eeddc0SDimitry Andric   // Get the next machine basic block in the function.
433*04eeddc0SDimitry Andric   MachineFunction::iterator MBBI = MBB->getIterator();
434*04eeddc0SDimitry Andric   // Can't fall off end of function.
435*04eeddc0SDimitry Andric   if (std::next(MBBI) == MBB->getParent()->end())
436*04eeddc0SDimitry Andric     return false;
437*04eeddc0SDimitry Andric 
438*04eeddc0SDimitry Andric   MachineBasicBlock *NextBB = &*std::next(MBBI);
439*04eeddc0SDimitry Andric   for (MachineBasicBlock::succ_iterator I = MBB->succ_begin(),
440*04eeddc0SDimitry Andric                                         E = MBB->succ_end();
441*04eeddc0SDimitry Andric        I != E; ++I)
442*04eeddc0SDimitry Andric     if (*I == NextBB)
443*04eeddc0SDimitry Andric       return true;
444*04eeddc0SDimitry Andric 
445*04eeddc0SDimitry Andric   return false;
446*04eeddc0SDimitry Andric }
447*04eeddc0SDimitry Andric 
448*04eeddc0SDimitry Andric /// findConstPoolEntry - Given the constpool index and CONSTPOOL_ENTRY MI,
449*04eeddc0SDimitry Andric /// look up the corresponding CPEntry.
450*04eeddc0SDimitry Andric CSKYConstantIslands::CPEntry *
451*04eeddc0SDimitry Andric CSKYConstantIslands::findConstPoolEntry(unsigned CPI,
452*04eeddc0SDimitry Andric                                         const MachineInstr *CPEMI) {
453*04eeddc0SDimitry Andric   std::vector<CPEntry> &CPEs = CPEntries[CPI];
454*04eeddc0SDimitry Andric   // Number of entries per constpool index should be small, just do a
455*04eeddc0SDimitry Andric   // linear search.
456*04eeddc0SDimitry Andric   for (unsigned I = 0, E = CPEs.size(); I != E; ++I) {
457*04eeddc0SDimitry Andric     if (CPEs[I].CPEMI == CPEMI)
458*04eeddc0SDimitry Andric       return &CPEs[I];
459*04eeddc0SDimitry Andric   }
460*04eeddc0SDimitry Andric   return nullptr;
461*04eeddc0SDimitry Andric }
462*04eeddc0SDimitry Andric 
463*04eeddc0SDimitry Andric /// getCPEAlign - Returns the required alignment of the constant pool entry
464*04eeddc0SDimitry Andric /// represented by CPEMI.  Alignment is measured in log2(bytes) units.
465*04eeddc0SDimitry Andric Align CSKYConstantIslands::getCPEAlign(const MachineInstr &CPEMI) {
466*04eeddc0SDimitry Andric   assert(CPEMI.getOpcode() == CSKY::CONSTPOOL_ENTRY);
467*04eeddc0SDimitry Andric 
468*04eeddc0SDimitry Andric   unsigned CPI = CPEMI.getOperand(1).getIndex();
469*04eeddc0SDimitry Andric   assert(CPI < MCP->getConstants().size() && "Invalid constant pool index.");
470*04eeddc0SDimitry Andric   return MCP->getConstants()[CPI].getAlign();
471*04eeddc0SDimitry Andric }
472*04eeddc0SDimitry Andric 
473*04eeddc0SDimitry Andric /// initializeFunctionInfo - Do the initial scan of the function, building up
474*04eeddc0SDimitry Andric /// information about the sizes of each block, the location of all the water,
475*04eeddc0SDimitry Andric /// and finding all of the constant pool users.
476*04eeddc0SDimitry Andric void CSKYConstantIslands::initializeFunctionInfo(
477*04eeddc0SDimitry Andric     const std::vector<MachineInstr *> &CPEMIs) {
478*04eeddc0SDimitry Andric   BBInfo.clear();
479*04eeddc0SDimitry Andric   BBInfo.resize(MF->getNumBlockIDs());
480*04eeddc0SDimitry Andric 
481*04eeddc0SDimitry Andric   // First thing, compute the size of all basic blocks, and see if the function
482*04eeddc0SDimitry Andric   // has any inline assembly in it. If so, we have to be conservative about
483*04eeddc0SDimitry Andric   // alignment assumptions, as we don't know for sure the size of any
484*04eeddc0SDimitry Andric   // instructions in the inline assembly.
485*04eeddc0SDimitry Andric   for (MachineFunction::iterator I = MF->begin(), E = MF->end(); I != E; ++I)
486*04eeddc0SDimitry Andric     computeBlockSize(&*I);
487*04eeddc0SDimitry Andric 
488*04eeddc0SDimitry Andric   // Compute block offsets.
489*04eeddc0SDimitry Andric   adjustBBOffsetsAfter(&MF->front());
490*04eeddc0SDimitry Andric 
491*04eeddc0SDimitry Andric   // Now go back through the instructions and build up our data structures.
492*04eeddc0SDimitry Andric   for (MachineBasicBlock &MBB : *MF) {
493*04eeddc0SDimitry Andric     // If this block doesn't fall through into the next MBB, then this is
494*04eeddc0SDimitry Andric     // 'water' that a constant pool island could be placed.
495*04eeddc0SDimitry Andric     if (!bbHasFallthrough(&MBB))
496*04eeddc0SDimitry Andric       WaterList.push_back(&MBB);
497*04eeddc0SDimitry Andric     for (MachineInstr &MI : MBB) {
498*04eeddc0SDimitry Andric       if (MI.isDebugInstr())
499*04eeddc0SDimitry Andric         continue;
500*04eeddc0SDimitry Andric 
501*04eeddc0SDimitry Andric       int Opc = MI.getOpcode();
502*04eeddc0SDimitry Andric       if (MI.isBranch() && !MI.isIndirectBranch()) {
503*04eeddc0SDimitry Andric         bool IsCond = MI.isConditionalBranch();
504*04eeddc0SDimitry Andric         unsigned Bits = 0;
505*04eeddc0SDimitry Andric         unsigned Scale = 1;
506*04eeddc0SDimitry Andric         int UOpc = CSKY::BR32;
507*04eeddc0SDimitry Andric 
508*04eeddc0SDimitry Andric         switch (MI.getOpcode()) {
509*04eeddc0SDimitry Andric         case CSKY::BR16:
510*04eeddc0SDimitry Andric         case CSKY::BF16:
511*04eeddc0SDimitry Andric         case CSKY::BT16:
512*04eeddc0SDimitry Andric           Bits = 10;
513*04eeddc0SDimitry Andric           Scale = 2;
514*04eeddc0SDimitry Andric           break;
515*04eeddc0SDimitry Andric         default:
516*04eeddc0SDimitry Andric           Bits = 16;
517*04eeddc0SDimitry Andric           Scale = 2;
518*04eeddc0SDimitry Andric           break;
519*04eeddc0SDimitry Andric         }
520*04eeddc0SDimitry Andric 
521*04eeddc0SDimitry Andric         // Record this immediate branch.
522*04eeddc0SDimitry Andric         unsigned MaxOffs = ((1 << (Bits - 1)) - 1) * Scale;
523*04eeddc0SDimitry Andric         ImmBranches.push_back(ImmBranch(&MI, MaxOffs, IsCond, UOpc));
524*04eeddc0SDimitry Andric       }
525*04eeddc0SDimitry Andric 
526*04eeddc0SDimitry Andric       if (Opc == CSKY::CONSTPOOL_ENTRY)
527*04eeddc0SDimitry Andric         continue;
528*04eeddc0SDimitry Andric 
529*04eeddc0SDimitry Andric       // Scan the instructions for constant pool operands.
530*04eeddc0SDimitry Andric       for (unsigned Op = 0, E = MI.getNumOperands(); Op != E; ++Op)
531*04eeddc0SDimitry Andric         if (MI.getOperand(Op).isCPI()) {
532*04eeddc0SDimitry Andric           // We found one.  The addressing mode tells us the max displacement
533*04eeddc0SDimitry Andric           // from the PC that this instruction permits.
534*04eeddc0SDimitry Andric 
535*04eeddc0SDimitry Andric           // Basic size info comes from the TSFlags field.
536*04eeddc0SDimitry Andric           unsigned Bits = 0;
537*04eeddc0SDimitry Andric           unsigned Scale = 1;
538*04eeddc0SDimitry Andric           bool NegOk = false;
539*04eeddc0SDimitry Andric 
540*04eeddc0SDimitry Andric           switch (Opc) {
541*04eeddc0SDimitry Andric           default:
542*04eeddc0SDimitry Andric             llvm_unreachable("Unknown addressing mode for CP reference!");
543*04eeddc0SDimitry Andric           case CSKY::MOVIH32:
544*04eeddc0SDimitry Andric           case CSKY::ORI32:
545*04eeddc0SDimitry Andric             continue;
546*04eeddc0SDimitry Andric           case CSKY::PseudoTLSLA32:
547*04eeddc0SDimitry Andric           case CSKY::JSRI32:
548*04eeddc0SDimitry Andric           case CSKY::JMPI32:
549*04eeddc0SDimitry Andric           case CSKY::LRW32:
550*04eeddc0SDimitry Andric           case CSKY::LRW32_Gen:
551*04eeddc0SDimitry Andric             Bits = 16;
552*04eeddc0SDimitry Andric             Scale = 4;
553*04eeddc0SDimitry Andric             break;
554*04eeddc0SDimitry Andric           case CSKY::f2FLRW_S:
555*04eeddc0SDimitry Andric           case CSKY::f2FLRW_D:
556*04eeddc0SDimitry Andric             Bits = 8;
557*04eeddc0SDimitry Andric             Scale = 4;
558*04eeddc0SDimitry Andric             break;
559*04eeddc0SDimitry Andric           case CSKY::GRS32:
560*04eeddc0SDimitry Andric             Bits = 17;
561*04eeddc0SDimitry Andric             Scale = 2;
562*04eeddc0SDimitry Andric             NegOk = true;
563*04eeddc0SDimitry Andric             break;
564*04eeddc0SDimitry Andric           }
565*04eeddc0SDimitry Andric           // Remember that this is a user of a CP entry.
566*04eeddc0SDimitry Andric           unsigned CPI = MI.getOperand(Op).getIndex();
567*04eeddc0SDimitry Andric           MachineInstr *CPEMI = CPEMIs[CPI];
568*04eeddc0SDimitry Andric           unsigned MaxOffs = ((1 << Bits) - 1) * Scale;
569*04eeddc0SDimitry Andric           CPUsers.push_back(CPUser(&MI, CPEMI, MaxOffs, NegOk));
570*04eeddc0SDimitry Andric 
571*04eeddc0SDimitry Andric           // Increment corresponding CPEntry reference count.
572*04eeddc0SDimitry Andric           CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
573*04eeddc0SDimitry Andric           assert(CPE && "Cannot find a corresponding CPEntry!");
574*04eeddc0SDimitry Andric           CPE->RefCount++;
575*04eeddc0SDimitry Andric 
576*04eeddc0SDimitry Andric           // Instructions can only use one CP entry, don't bother scanning the
577*04eeddc0SDimitry Andric           // rest of the operands.
578*04eeddc0SDimitry Andric           break;
579*04eeddc0SDimitry Andric         }
580*04eeddc0SDimitry Andric     }
581*04eeddc0SDimitry Andric   }
582*04eeddc0SDimitry Andric }
583*04eeddc0SDimitry Andric 
584*04eeddc0SDimitry Andric /// computeBlockSize - Compute the size and some alignment information for MBB.
585*04eeddc0SDimitry Andric /// This function updates BBInfo directly.
586*04eeddc0SDimitry Andric void CSKYConstantIslands::computeBlockSize(MachineBasicBlock *MBB) {
587*04eeddc0SDimitry Andric   BasicBlockInfo &BBI = BBInfo[MBB->getNumber()];
588*04eeddc0SDimitry Andric   BBI.Size = 0;
589*04eeddc0SDimitry Andric 
590*04eeddc0SDimitry Andric   for (const MachineInstr &MI : *MBB)
591*04eeddc0SDimitry Andric     BBI.Size += TII->getInstSizeInBytes(MI);
592*04eeddc0SDimitry Andric }
593*04eeddc0SDimitry Andric 
594*04eeddc0SDimitry Andric /// getOffsetOf - Return the current offset of the specified machine instruction
595*04eeddc0SDimitry Andric /// from the start of the function.  This offset changes as stuff is moved
596*04eeddc0SDimitry Andric /// around inside the function.
597*04eeddc0SDimitry Andric unsigned CSKYConstantIslands::getOffsetOf(MachineInstr *MI) const {
598*04eeddc0SDimitry Andric   MachineBasicBlock *MBB = MI->getParent();
599*04eeddc0SDimitry Andric 
600*04eeddc0SDimitry Andric   // The offset is composed of two things: the sum of the sizes of all MBB's
601*04eeddc0SDimitry Andric   // before this instruction's block, and the offset from the start of the block
602*04eeddc0SDimitry Andric   // it is in.
603*04eeddc0SDimitry Andric   unsigned Offset = BBInfo[MBB->getNumber()].Offset;
604*04eeddc0SDimitry Andric 
605*04eeddc0SDimitry Andric   // Sum instructions before MI in MBB.
606*04eeddc0SDimitry Andric   for (MachineBasicBlock::iterator I = MBB->begin(); &*I != MI; ++I) {
607*04eeddc0SDimitry Andric     assert(I != MBB->end() && "Didn't find MI in its own basic block?");
608*04eeddc0SDimitry Andric     Offset += TII->getInstSizeInBytes(*I);
609*04eeddc0SDimitry Andric   }
610*04eeddc0SDimitry Andric   return Offset;
611*04eeddc0SDimitry Andric }
612*04eeddc0SDimitry Andric 
613*04eeddc0SDimitry Andric /// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB
614*04eeddc0SDimitry Andric /// ID.
615*04eeddc0SDimitry Andric static bool compareMbbNumbers(const MachineBasicBlock *LHS,
616*04eeddc0SDimitry Andric                               const MachineBasicBlock *RHS) {
617*04eeddc0SDimitry Andric   return LHS->getNumber() < RHS->getNumber();
618*04eeddc0SDimitry Andric }
619*04eeddc0SDimitry Andric 
620*04eeddc0SDimitry Andric /// updateForInsertedWaterBlock - When a block is newly inserted into the
621*04eeddc0SDimitry Andric /// machine function, it upsets all of the block numbers.  Renumber the blocks
622*04eeddc0SDimitry Andric /// and update the arrays that parallel this numbering.
623*04eeddc0SDimitry Andric void CSKYConstantIslands::updateForInsertedWaterBlock(
624*04eeddc0SDimitry Andric     MachineBasicBlock *NewBB) {
625*04eeddc0SDimitry Andric   // Renumber the MBB's to keep them consecutive.
626*04eeddc0SDimitry Andric   NewBB->getParent()->RenumberBlocks(NewBB);
627*04eeddc0SDimitry Andric 
628*04eeddc0SDimitry Andric   // Insert an entry into BBInfo to align it properly with the (newly
629*04eeddc0SDimitry Andric   // renumbered) block numbers.
630*04eeddc0SDimitry Andric   BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
631*04eeddc0SDimitry Andric 
632*04eeddc0SDimitry Andric   // Next, update WaterList.  Specifically, we need to add NewMBB as having
633*04eeddc0SDimitry Andric   // available water after it.
634*04eeddc0SDimitry Andric   water_iterator IP = llvm::lower_bound(WaterList, NewBB, compareMbbNumbers);
635*04eeddc0SDimitry Andric   WaterList.insert(IP, NewBB);
636*04eeddc0SDimitry Andric }
637*04eeddc0SDimitry Andric 
638*04eeddc0SDimitry Andric unsigned CSKYConstantIslands::getUserOffset(CPUser &U) const {
639*04eeddc0SDimitry Andric   unsigned UserOffset = getOffsetOf(U.MI);
640*04eeddc0SDimitry Andric 
641*04eeddc0SDimitry Andric   UserOffset &= ~3u;
642*04eeddc0SDimitry Andric 
643*04eeddc0SDimitry Andric   return UserOffset;
644*04eeddc0SDimitry Andric }
645*04eeddc0SDimitry Andric 
646*04eeddc0SDimitry Andric /// Split the basic block containing MI into two blocks, which are joined by
647*04eeddc0SDimitry Andric /// an unconditional branch.  Update data structures and renumber blocks to
648*04eeddc0SDimitry Andric /// account for this change and returns the newly created block.
649*04eeddc0SDimitry Andric MachineBasicBlock *
650*04eeddc0SDimitry Andric CSKYConstantIslands::splitBlockBeforeInstr(MachineInstr &MI) {
651*04eeddc0SDimitry Andric   MachineBasicBlock *OrigBB = MI.getParent();
652*04eeddc0SDimitry Andric 
653*04eeddc0SDimitry Andric   // Create a new MBB for the code after the OrigBB.
654*04eeddc0SDimitry Andric   MachineBasicBlock *NewBB =
655*04eeddc0SDimitry Andric       MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
656*04eeddc0SDimitry Andric   MachineFunction::iterator MBBI = ++OrigBB->getIterator();
657*04eeddc0SDimitry Andric   MF->insert(MBBI, NewBB);
658*04eeddc0SDimitry Andric 
659*04eeddc0SDimitry Andric   // Splice the instructions starting with MI over to NewBB.
660*04eeddc0SDimitry Andric   NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end());
661*04eeddc0SDimitry Andric 
662*04eeddc0SDimitry Andric   // Add an unconditional branch from OrigBB to NewBB.
663*04eeddc0SDimitry Andric   // Note the new unconditional branch is not being recorded.
664*04eeddc0SDimitry Andric   // There doesn't seem to be meaningful DebugInfo available; this doesn't
665*04eeddc0SDimitry Andric   // correspond to anything in the source.
666*04eeddc0SDimitry Andric 
667*04eeddc0SDimitry Andric   // TODO: Add support for 16bit instr.
668*04eeddc0SDimitry Andric   BuildMI(OrigBB, DebugLoc(), TII->get(CSKY::BR32)).addMBB(NewBB);
669*04eeddc0SDimitry Andric   ++NumSplit;
670*04eeddc0SDimitry Andric 
671*04eeddc0SDimitry Andric   // Update the CFG.  All succs of OrigBB are now succs of NewBB.
672*04eeddc0SDimitry Andric   NewBB->transferSuccessors(OrigBB);
673*04eeddc0SDimitry Andric 
674*04eeddc0SDimitry Andric   // OrigBB branches to NewBB.
675*04eeddc0SDimitry Andric   OrigBB->addSuccessor(NewBB);
676*04eeddc0SDimitry Andric 
677*04eeddc0SDimitry Andric   // Update internal data structures to account for the newly inserted MBB.
678*04eeddc0SDimitry Andric   // This is almost the same as updateForInsertedWaterBlock, except that
679*04eeddc0SDimitry Andric   // the Water goes after OrigBB, not NewBB.
680*04eeddc0SDimitry Andric   MF->RenumberBlocks(NewBB);
681*04eeddc0SDimitry Andric 
682*04eeddc0SDimitry Andric   // Insert an entry into BBInfo to align it properly with the (newly
683*04eeddc0SDimitry Andric   // renumbered) block numbers.
684*04eeddc0SDimitry Andric   BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
685*04eeddc0SDimitry Andric 
686*04eeddc0SDimitry Andric   // Next, update WaterList.  Specifically, we need to add OrigMBB as having
687*04eeddc0SDimitry Andric   // available water after it (but not if it's already there, which happens
688*04eeddc0SDimitry Andric   // when splitting before a conditional branch that is followed by an
689*04eeddc0SDimitry Andric   // unconditional branch - in that case we want to insert NewBB).
690*04eeddc0SDimitry Andric   water_iterator IP = llvm::lower_bound(WaterList, OrigBB, compareMbbNumbers);
691*04eeddc0SDimitry Andric   MachineBasicBlock *WaterBB = *IP;
692*04eeddc0SDimitry Andric   if (WaterBB == OrigBB)
693*04eeddc0SDimitry Andric     WaterList.insert(std::next(IP), NewBB);
694*04eeddc0SDimitry Andric   else
695*04eeddc0SDimitry Andric     WaterList.insert(IP, OrigBB);
696*04eeddc0SDimitry Andric   NewWaterList.insert(OrigBB);
697*04eeddc0SDimitry Andric 
698*04eeddc0SDimitry Andric   // Figure out how large the OrigBB is.  As the first half of the original
699*04eeddc0SDimitry Andric   // block, it cannot contain a tablejump.  The size includes
700*04eeddc0SDimitry Andric   // the new jump we added.  (It should be possible to do this without
701*04eeddc0SDimitry Andric   // recounting everything, but it's very confusing, and this is rarely
702*04eeddc0SDimitry Andric   // executed.)
703*04eeddc0SDimitry Andric   computeBlockSize(OrigBB);
704*04eeddc0SDimitry Andric 
705*04eeddc0SDimitry Andric   // Figure out how large the NewMBB is.  As the second half of the original
706*04eeddc0SDimitry Andric   // block, it may contain a tablejump.
707*04eeddc0SDimitry Andric   computeBlockSize(NewBB);
708*04eeddc0SDimitry Andric 
709*04eeddc0SDimitry Andric   // All BBOffsets following these blocks must be modified.
710*04eeddc0SDimitry Andric   adjustBBOffsetsAfter(OrigBB);
711*04eeddc0SDimitry Andric 
712*04eeddc0SDimitry Andric   return NewBB;
713*04eeddc0SDimitry Andric }
714*04eeddc0SDimitry Andric 
715*04eeddc0SDimitry Andric /// isOffsetInRange - Checks whether UserOffset (the location of a constant pool
716*04eeddc0SDimitry Andric /// reference) is within MaxDisp of TrialOffset (a proposed location of a
717*04eeddc0SDimitry Andric /// constant pool entry).
718*04eeddc0SDimitry Andric bool CSKYConstantIslands::isOffsetInRange(unsigned UserOffset,
719*04eeddc0SDimitry Andric                                           unsigned TrialOffset,
720*04eeddc0SDimitry Andric                                           unsigned MaxDisp, bool NegativeOK) {
721*04eeddc0SDimitry Andric   if (UserOffset <= TrialOffset) {
722*04eeddc0SDimitry Andric     // User before the Trial.
723*04eeddc0SDimitry Andric     if (TrialOffset - UserOffset <= MaxDisp)
724*04eeddc0SDimitry Andric       return true;
725*04eeddc0SDimitry Andric   } else if (NegativeOK) {
726*04eeddc0SDimitry Andric     if (UserOffset - TrialOffset <= MaxDisp)
727*04eeddc0SDimitry Andric       return true;
728*04eeddc0SDimitry Andric   }
729*04eeddc0SDimitry Andric   return false;
730*04eeddc0SDimitry Andric }
731*04eeddc0SDimitry Andric 
732*04eeddc0SDimitry Andric /// isWaterInRange - Returns true if a CPE placed after the specified
733*04eeddc0SDimitry Andric /// Water (a basic block) will be in range for the specific MI.
734*04eeddc0SDimitry Andric ///
735*04eeddc0SDimitry Andric /// Compute how much the function will grow by inserting a CPE after Water.
736*04eeddc0SDimitry Andric bool CSKYConstantIslands::isWaterInRange(unsigned UserOffset,
737*04eeddc0SDimitry Andric                                          MachineBasicBlock *Water, CPUser &U,
738*04eeddc0SDimitry Andric                                          unsigned &Growth) {
739*04eeddc0SDimitry Andric   unsigned CPEOffset = BBInfo[Water->getNumber()].postOffset();
740*04eeddc0SDimitry Andric   unsigned NextBlockOffset;
741*04eeddc0SDimitry Andric   Align NextBlockAlignment;
742*04eeddc0SDimitry Andric   MachineFunction::const_iterator NextBlock = ++Water->getIterator();
743*04eeddc0SDimitry Andric   if (NextBlock == MF->end()) {
744*04eeddc0SDimitry Andric     NextBlockOffset = BBInfo[Water->getNumber()].postOffset();
745*04eeddc0SDimitry Andric     NextBlockAlignment = Align(4);
746*04eeddc0SDimitry Andric   } else {
747*04eeddc0SDimitry Andric     NextBlockOffset = BBInfo[NextBlock->getNumber()].Offset;
748*04eeddc0SDimitry Andric     NextBlockAlignment = NextBlock->getAlignment();
749*04eeddc0SDimitry Andric   }
750*04eeddc0SDimitry Andric   unsigned Size = U.CPEMI->getOperand(2).getImm();
751*04eeddc0SDimitry Andric   unsigned CPEEnd = CPEOffset + Size;
752*04eeddc0SDimitry Andric 
753*04eeddc0SDimitry Andric   // The CPE may be able to hide in the alignment padding before the next
754*04eeddc0SDimitry Andric   // block. It may also cause more padding to be required if it is more aligned
755*04eeddc0SDimitry Andric   // that the next block.
756*04eeddc0SDimitry Andric   if (CPEEnd > NextBlockOffset) {
757*04eeddc0SDimitry Andric     Growth = CPEEnd - NextBlockOffset;
758*04eeddc0SDimitry Andric     // Compute the padding that would go at the end of the CPE to align the next
759*04eeddc0SDimitry Andric     // block.
760*04eeddc0SDimitry Andric     Growth += offsetToAlignment(CPEEnd, NextBlockAlignment);
761*04eeddc0SDimitry Andric 
762*04eeddc0SDimitry Andric     // If the CPE is to be inserted before the instruction, that will raise
763*04eeddc0SDimitry Andric     // the offset of the instruction. Also account for unknown alignment padding
764*04eeddc0SDimitry Andric     // in blocks between CPE and the user.
765*04eeddc0SDimitry Andric     if (CPEOffset < UserOffset)
766*04eeddc0SDimitry Andric       UserOffset += Growth;
767*04eeddc0SDimitry Andric   } else
768*04eeddc0SDimitry Andric     // CPE fits in existing padding.
769*04eeddc0SDimitry Andric     Growth = 0;
770*04eeddc0SDimitry Andric 
771*04eeddc0SDimitry Andric   return isOffsetInRange(UserOffset, CPEOffset, U);
772*04eeddc0SDimitry Andric }
773*04eeddc0SDimitry Andric 
774*04eeddc0SDimitry Andric /// isCPEntryInRange - Returns true if the distance between specific MI and
775*04eeddc0SDimitry Andric /// specific ConstPool entry instruction can fit in MI's displacement field.
776*04eeddc0SDimitry Andric bool CSKYConstantIslands::isCPEntryInRange(MachineInstr *MI,
777*04eeddc0SDimitry Andric                                            unsigned UserOffset,
778*04eeddc0SDimitry Andric                                            MachineInstr *CPEMI,
779*04eeddc0SDimitry Andric                                            unsigned MaxDisp, bool NegOk,
780*04eeddc0SDimitry Andric                                            bool DoDump) {
781*04eeddc0SDimitry Andric   unsigned CPEOffset = getOffsetOf(CPEMI);
782*04eeddc0SDimitry Andric 
783*04eeddc0SDimitry Andric   if (DoDump) {
784*04eeddc0SDimitry Andric     LLVM_DEBUG({
785*04eeddc0SDimitry Andric       unsigned Block = MI->getParent()->getNumber();
786*04eeddc0SDimitry Andric       const BasicBlockInfo &BBI = BBInfo[Block];
787*04eeddc0SDimitry Andric       dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm()
788*04eeddc0SDimitry Andric              << " max delta=" << MaxDisp
789*04eeddc0SDimitry Andric              << format(" insn address=%#x", UserOffset) << " in "
790*04eeddc0SDimitry Andric              << printMBBReference(*MI->getParent()) << ": "
791*04eeddc0SDimitry Andric              << format("%#x-%x\t", BBI.Offset, BBI.postOffset()) << *MI
792*04eeddc0SDimitry Andric              << format("CPE address=%#x offset=%+d: ", CPEOffset,
793*04eeddc0SDimitry Andric                        int(CPEOffset - UserOffset));
794*04eeddc0SDimitry Andric     });
795*04eeddc0SDimitry Andric   }
796*04eeddc0SDimitry Andric 
797*04eeddc0SDimitry Andric   return isOffsetInRange(UserOffset, CPEOffset, MaxDisp, NegOk);
798*04eeddc0SDimitry Andric }
799*04eeddc0SDimitry Andric 
800*04eeddc0SDimitry Andric #ifndef NDEBUG
801*04eeddc0SDimitry Andric /// BBIsJumpedOver - Return true of the specified basic block's only predecessor
802*04eeddc0SDimitry Andric /// unconditionally branches to its only successor.
803*04eeddc0SDimitry Andric static bool bbIsJumpedOver(MachineBasicBlock *MBB) {
804*04eeddc0SDimitry Andric   if (MBB->pred_size() != 1 || MBB->succ_size() != 1)
805*04eeddc0SDimitry Andric     return false;
806*04eeddc0SDimitry Andric   MachineBasicBlock *Succ = *MBB->succ_begin();
807*04eeddc0SDimitry Andric   MachineBasicBlock *Pred = *MBB->pred_begin();
808*04eeddc0SDimitry Andric   MachineInstr *PredMI = &Pred->back();
809*04eeddc0SDimitry Andric   if (PredMI->getOpcode() == CSKY::BR32 /*TODO: change to 16bit instr. */)
810*04eeddc0SDimitry Andric     return PredMI->getOperand(0).getMBB() == Succ;
811*04eeddc0SDimitry Andric   return false;
812*04eeddc0SDimitry Andric }
813*04eeddc0SDimitry Andric #endif
814*04eeddc0SDimitry Andric 
815*04eeddc0SDimitry Andric void CSKYConstantIslands::adjustBBOffsetsAfter(MachineBasicBlock *BB) {
816*04eeddc0SDimitry Andric   unsigned BBNum = BB->getNumber();
817*04eeddc0SDimitry Andric   for (unsigned I = BBNum + 1, E = MF->getNumBlockIDs(); I < E; ++I) {
818*04eeddc0SDimitry Andric     // Get the offset and known bits at the end of the layout predecessor.
819*04eeddc0SDimitry Andric     // Include the alignment of the current block.
820*04eeddc0SDimitry Andric     unsigned Offset = BBInfo[I - 1].Offset + BBInfo[I - 1].Size;
821*04eeddc0SDimitry Andric     BBInfo[I].Offset = Offset;
822*04eeddc0SDimitry Andric   }
823*04eeddc0SDimitry Andric }
824*04eeddc0SDimitry Andric 
825*04eeddc0SDimitry Andric /// decrementCPEReferenceCount - find the constant pool entry with index CPI
826*04eeddc0SDimitry Andric /// and instruction CPEMI, and decrement its refcount.  If the refcount
827*04eeddc0SDimitry Andric /// becomes 0 remove the entry and instruction.  Returns true if we removed
828*04eeddc0SDimitry Andric /// the entry, false if we didn't.
829*04eeddc0SDimitry Andric bool CSKYConstantIslands::decrementCPEReferenceCount(unsigned CPI,
830*04eeddc0SDimitry Andric                                                      MachineInstr *CPEMI) {
831*04eeddc0SDimitry Andric   // Find the old entry. Eliminate it if it is no longer used.
832*04eeddc0SDimitry Andric   CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
833*04eeddc0SDimitry Andric   assert(CPE && "Unexpected!");
834*04eeddc0SDimitry Andric   if (--CPE->RefCount == 0) {
835*04eeddc0SDimitry Andric     removeDeadCPEMI(CPEMI);
836*04eeddc0SDimitry Andric     CPE->CPEMI = nullptr;
837*04eeddc0SDimitry Andric     --NumCPEs;
838*04eeddc0SDimitry Andric     return true;
839*04eeddc0SDimitry Andric   }
840*04eeddc0SDimitry Andric   return false;
841*04eeddc0SDimitry Andric }
842*04eeddc0SDimitry Andric 
843*04eeddc0SDimitry Andric /// LookForCPEntryInRange - see if the currently referenced CPE is in range;
844*04eeddc0SDimitry Andric /// if not, see if an in-range clone of the CPE is in range, and if so,
845*04eeddc0SDimitry Andric /// change the data structures so the user references the clone.  Returns:
846*04eeddc0SDimitry Andric /// 0 = no existing entry found
847*04eeddc0SDimitry Andric /// 1 = entry found, and there were no code insertions or deletions
848*04eeddc0SDimitry Andric /// 2 = entry found, and there were code insertions or deletions
849*04eeddc0SDimitry Andric int CSKYConstantIslands::findInRangeCPEntry(CPUser &U, unsigned UserOffset) {
850*04eeddc0SDimitry Andric   MachineInstr *UserMI = U.MI;
851*04eeddc0SDimitry Andric   MachineInstr *CPEMI = U.CPEMI;
852*04eeddc0SDimitry Andric 
853*04eeddc0SDimitry Andric   // Check to see if the CPE is already in-range.
854*04eeddc0SDimitry Andric   if (isCPEntryInRange(UserMI, UserOffset, CPEMI, U.getMaxDisp(), U.NegOk,
855*04eeddc0SDimitry Andric                        true)) {
856*04eeddc0SDimitry Andric     LLVM_DEBUG(dbgs() << "In range\n");
857*04eeddc0SDimitry Andric     return 1;
858*04eeddc0SDimitry Andric   }
859*04eeddc0SDimitry Andric 
860*04eeddc0SDimitry Andric   // No.  Look for previously created clones of the CPE that are in range.
861*04eeddc0SDimitry Andric   unsigned CPI = CPEMI->getOperand(1).getIndex();
862*04eeddc0SDimitry Andric   std::vector<CPEntry> &CPEs = CPEntries[CPI];
863*04eeddc0SDimitry Andric   for (unsigned I = 0, E = CPEs.size(); I != E; ++I) {
864*04eeddc0SDimitry Andric     // We already tried this one
865*04eeddc0SDimitry Andric     if (CPEs[I].CPEMI == CPEMI)
866*04eeddc0SDimitry Andric       continue;
867*04eeddc0SDimitry Andric     // Removing CPEs can leave empty entries, skip
868*04eeddc0SDimitry Andric     if (CPEs[I].CPEMI == nullptr)
869*04eeddc0SDimitry Andric       continue;
870*04eeddc0SDimitry Andric     if (isCPEntryInRange(UserMI, UserOffset, CPEs[I].CPEMI, U.getMaxDisp(),
871*04eeddc0SDimitry Andric                          U.NegOk)) {
872*04eeddc0SDimitry Andric       LLVM_DEBUG(dbgs() << "Replacing CPE#" << CPI << " with CPE#"
873*04eeddc0SDimitry Andric                         << CPEs[I].CPI << "\n");
874*04eeddc0SDimitry Andric       // Point the CPUser node to the replacement
875*04eeddc0SDimitry Andric       U.CPEMI = CPEs[I].CPEMI;
876*04eeddc0SDimitry Andric       // Change the CPI in the instruction operand to refer to the clone.
877*04eeddc0SDimitry Andric       for (unsigned J = 0, E = UserMI->getNumOperands(); J != E; ++J)
878*04eeddc0SDimitry Andric         if (UserMI->getOperand(J).isCPI()) {
879*04eeddc0SDimitry Andric           UserMI->getOperand(J).setIndex(CPEs[I].CPI);
880*04eeddc0SDimitry Andric           break;
881*04eeddc0SDimitry Andric         }
882*04eeddc0SDimitry Andric       // Adjust the refcount of the clone...
883*04eeddc0SDimitry Andric       CPEs[I].RefCount++;
884*04eeddc0SDimitry Andric       // ...and the original.  If we didn't remove the old entry, none of the
885*04eeddc0SDimitry Andric       // addresses changed, so we don't need another pass.
886*04eeddc0SDimitry Andric       return decrementCPEReferenceCount(CPI, CPEMI) ? 2 : 1;
887*04eeddc0SDimitry Andric     }
888*04eeddc0SDimitry Andric   }
889*04eeddc0SDimitry Andric   return 0;
890*04eeddc0SDimitry Andric }
891*04eeddc0SDimitry Andric 
892*04eeddc0SDimitry Andric /// getUnconditionalBrDisp - Returns the maximum displacement that can fit in
893*04eeddc0SDimitry Andric /// the specific unconditional branch instruction.
894*04eeddc0SDimitry Andric static inline unsigned getUnconditionalBrDisp(int Opc) {
895*04eeddc0SDimitry Andric   unsigned Bits, Scale;
896*04eeddc0SDimitry Andric 
897*04eeddc0SDimitry Andric   switch (Opc) {
898*04eeddc0SDimitry Andric   case CSKY::BR16:
899*04eeddc0SDimitry Andric     Bits = 10;
900*04eeddc0SDimitry Andric     Scale = 2;
901*04eeddc0SDimitry Andric     break;
902*04eeddc0SDimitry Andric   case CSKY::BR32:
903*04eeddc0SDimitry Andric     Bits = 16;
904*04eeddc0SDimitry Andric     Scale = 2;
905*04eeddc0SDimitry Andric     break;
906*04eeddc0SDimitry Andric   default:
907*04eeddc0SDimitry Andric     assert(0);
908*04eeddc0SDimitry Andric     break;
909*04eeddc0SDimitry Andric   }
910*04eeddc0SDimitry Andric 
911*04eeddc0SDimitry Andric   unsigned MaxOffs = ((1 << (Bits - 1)) - 1) * Scale;
912*04eeddc0SDimitry Andric   return MaxOffs;
913*04eeddc0SDimitry Andric }
914*04eeddc0SDimitry Andric 
915*04eeddc0SDimitry Andric /// findAvailableWater - Look for an existing entry in the WaterList in which
916*04eeddc0SDimitry Andric /// we can place the CPE referenced from U so it's within range of U's MI.
917*04eeddc0SDimitry Andric /// Returns true if found, false if not.  If it returns true, WaterIter
918*04eeddc0SDimitry Andric /// is set to the WaterList entry.
919*04eeddc0SDimitry Andric /// To ensure that this pass
920*04eeddc0SDimitry Andric /// terminates, the CPE location for a particular CPUser is only allowed to
921*04eeddc0SDimitry Andric /// move to a lower address, so search backward from the end of the list and
922*04eeddc0SDimitry Andric /// prefer the first water that is in range.
923*04eeddc0SDimitry Andric bool CSKYConstantIslands::findAvailableWater(CPUser &U, unsigned UserOffset,
924*04eeddc0SDimitry Andric                                              water_iterator &WaterIter) {
925*04eeddc0SDimitry Andric   if (WaterList.empty())
926*04eeddc0SDimitry Andric     return false;
927*04eeddc0SDimitry Andric 
928*04eeddc0SDimitry Andric   unsigned BestGrowth = ~0u;
929*04eeddc0SDimitry Andric   for (water_iterator IP = std::prev(WaterList.end()), B = WaterList.begin();;
930*04eeddc0SDimitry Andric        --IP) {
931*04eeddc0SDimitry Andric     MachineBasicBlock *WaterBB = *IP;
932*04eeddc0SDimitry Andric     // Check if water is in range and is either at a lower address than the
933*04eeddc0SDimitry Andric     // current "high water mark" or a new water block that was created since
934*04eeddc0SDimitry Andric     // the previous iteration by inserting an unconditional branch.  In the
935*04eeddc0SDimitry Andric     // latter case, we want to allow resetting the high water mark back to
936*04eeddc0SDimitry Andric     // this new water since we haven't seen it before.  Inserting branches
937*04eeddc0SDimitry Andric     // should be relatively uncommon and when it does happen, we want to be
938*04eeddc0SDimitry Andric     // sure to take advantage of it for all the CPEs near that block, so that
939*04eeddc0SDimitry Andric     // we don't insert more branches than necessary.
940*04eeddc0SDimitry Andric     unsigned Growth;
941*04eeddc0SDimitry Andric     if (isWaterInRange(UserOffset, WaterBB, U, Growth) &&
942*04eeddc0SDimitry Andric         (WaterBB->getNumber() < U.HighWaterMark->getNumber() ||
943*04eeddc0SDimitry Andric          NewWaterList.count(WaterBB)) &&
944*04eeddc0SDimitry Andric         Growth < BestGrowth) {
945*04eeddc0SDimitry Andric       // This is the least amount of required padding seen so far.
946*04eeddc0SDimitry Andric       BestGrowth = Growth;
947*04eeddc0SDimitry Andric       WaterIter = IP;
948*04eeddc0SDimitry Andric       LLVM_DEBUG(dbgs() << "Found water after " << printMBBReference(*WaterBB)
949*04eeddc0SDimitry Andric                         << " Growth=" << Growth << '\n');
950*04eeddc0SDimitry Andric 
951*04eeddc0SDimitry Andric       // Keep looking unless it is perfect.
952*04eeddc0SDimitry Andric       if (BestGrowth == 0)
953*04eeddc0SDimitry Andric         return true;
954*04eeddc0SDimitry Andric     }
955*04eeddc0SDimitry Andric     if (IP == B)
956*04eeddc0SDimitry Andric       break;
957*04eeddc0SDimitry Andric   }
958*04eeddc0SDimitry Andric   return BestGrowth != ~0u;
959*04eeddc0SDimitry Andric }
960*04eeddc0SDimitry Andric 
961*04eeddc0SDimitry Andric /// createNewWater - No existing WaterList entry will work for
962*04eeddc0SDimitry Andric /// CPUsers[CPUserIndex], so create a place to put the CPE.  The end of the
963*04eeddc0SDimitry Andric /// block is used if in range, and the conditional branch munged so control
964*04eeddc0SDimitry Andric /// flow is correct.  Otherwise the block is split to create a hole with an
965*04eeddc0SDimitry Andric /// unconditional branch around it.  In either case NewMBB is set to a
966*04eeddc0SDimitry Andric /// block following which the new island can be inserted (the WaterList
967*04eeddc0SDimitry Andric /// is not adjusted).
968*04eeddc0SDimitry Andric void CSKYConstantIslands::createNewWater(unsigned CPUserIndex,
969*04eeddc0SDimitry Andric                                          unsigned UserOffset,
970*04eeddc0SDimitry Andric                                          MachineBasicBlock *&NewMBB) {
971*04eeddc0SDimitry Andric   CPUser &U = CPUsers[CPUserIndex];
972*04eeddc0SDimitry Andric   MachineInstr *UserMI = U.MI;
973*04eeddc0SDimitry Andric   MachineInstr *CPEMI = U.CPEMI;
974*04eeddc0SDimitry Andric   MachineBasicBlock *UserMBB = UserMI->getParent();
975*04eeddc0SDimitry Andric   const BasicBlockInfo &UserBBI = BBInfo[UserMBB->getNumber()];
976*04eeddc0SDimitry Andric 
977*04eeddc0SDimitry Andric   // If the block does not end in an unconditional branch already, and if the
978*04eeddc0SDimitry Andric   // end of the block is within range, make new water there.
979*04eeddc0SDimitry Andric   if (bbHasFallthrough(UserMBB)) {
980*04eeddc0SDimitry Andric     // Size of branch to insert.
981*04eeddc0SDimitry Andric     unsigned Delta = 4;
982*04eeddc0SDimitry Andric     // Compute the offset where the CPE will begin.
983*04eeddc0SDimitry Andric     unsigned CPEOffset = UserBBI.postOffset() + Delta;
984*04eeddc0SDimitry Andric 
985*04eeddc0SDimitry Andric     if (isOffsetInRange(UserOffset, CPEOffset, U)) {
986*04eeddc0SDimitry Andric       LLVM_DEBUG(dbgs() << "Split at end of " << printMBBReference(*UserMBB)
987*04eeddc0SDimitry Andric                         << format(", expected CPE offset %#x\n", CPEOffset));
988*04eeddc0SDimitry Andric       NewMBB = &*++UserMBB->getIterator();
989*04eeddc0SDimitry Andric       // Add an unconditional branch from UserMBB to fallthrough block.  Record
990*04eeddc0SDimitry Andric       // it for branch lengthening; this new branch will not get out of range,
991*04eeddc0SDimitry Andric       // but if the preceding conditional branch is out of range, the targets
992*04eeddc0SDimitry Andric       // will be exchanged, and the altered branch may be out of range, so the
993*04eeddc0SDimitry Andric       // machinery has to know about it.
994*04eeddc0SDimitry Andric 
995*04eeddc0SDimitry Andric       // TODO: Add support for 16bit instr.
996*04eeddc0SDimitry Andric       int UncondBr = CSKY::BR32;
997*04eeddc0SDimitry Andric       auto *NewMI = BuildMI(UserMBB, DebugLoc(), TII->get(UncondBr))
998*04eeddc0SDimitry Andric                         .addMBB(NewMBB)
999*04eeddc0SDimitry Andric                         .getInstr();
1000*04eeddc0SDimitry Andric       unsigned MaxDisp = getUnconditionalBrDisp(UncondBr);
1001*04eeddc0SDimitry Andric       ImmBranches.push_back(
1002*04eeddc0SDimitry Andric           ImmBranch(&UserMBB->back(), MaxDisp, false, UncondBr));
1003*04eeddc0SDimitry Andric       BBInfo[UserMBB->getNumber()].Size += TII->getInstSizeInBytes(*NewMI);
1004*04eeddc0SDimitry Andric       adjustBBOffsetsAfter(UserMBB);
1005*04eeddc0SDimitry Andric       return;
1006*04eeddc0SDimitry Andric     }
1007*04eeddc0SDimitry Andric   }
1008*04eeddc0SDimitry Andric 
1009*04eeddc0SDimitry Andric   // What a big block.  Find a place within the block to split it.
1010*04eeddc0SDimitry Andric 
1011*04eeddc0SDimitry Andric   // Try to split the block so it's fully aligned.  Compute the latest split
1012*04eeddc0SDimitry Andric   // point where we can add a 4-byte branch instruction, and then align to
1013*04eeddc0SDimitry Andric   // Align which is the largest possible alignment in the function.
1014*04eeddc0SDimitry Andric   const Align Align = MF->getAlignment();
1015*04eeddc0SDimitry Andric   unsigned BaseInsertOffset = UserOffset + U.getMaxDisp();
1016*04eeddc0SDimitry Andric   LLVM_DEBUG(dbgs() << format("Split in middle of big block before %#x",
1017*04eeddc0SDimitry Andric                               BaseInsertOffset));
1018*04eeddc0SDimitry Andric 
1019*04eeddc0SDimitry Andric   // The 4 in the following is for the unconditional branch we'll be inserting
1020*04eeddc0SDimitry Andric   // Alignment of the island is handled
1021*04eeddc0SDimitry Andric   // inside isOffsetInRange.
1022*04eeddc0SDimitry Andric   BaseInsertOffset -= 4;
1023*04eeddc0SDimitry Andric 
1024*04eeddc0SDimitry Andric   LLVM_DEBUG(dbgs() << format(", adjusted to %#x", BaseInsertOffset)
1025*04eeddc0SDimitry Andric                     << " la=" << Log2(Align) << '\n');
1026*04eeddc0SDimitry Andric 
1027*04eeddc0SDimitry Andric   // This could point off the end of the block if we've already got constant
1028*04eeddc0SDimitry Andric   // pool entries following this block; only the last one is in the water list.
1029*04eeddc0SDimitry Andric   // Back past any possible branches (allow for a conditional and a maximally
1030*04eeddc0SDimitry Andric   // long unconditional).
1031*04eeddc0SDimitry Andric   if (BaseInsertOffset + 8 >= UserBBI.postOffset()) {
1032*04eeddc0SDimitry Andric     BaseInsertOffset = UserBBI.postOffset() - 8;
1033*04eeddc0SDimitry Andric     LLVM_DEBUG(dbgs() << format("Move inside block: %#x\n", BaseInsertOffset));
1034*04eeddc0SDimitry Andric   }
1035*04eeddc0SDimitry Andric   unsigned EndInsertOffset =
1036*04eeddc0SDimitry Andric       BaseInsertOffset + 4 + CPEMI->getOperand(2).getImm();
1037*04eeddc0SDimitry Andric   MachineBasicBlock::iterator MI = UserMI;
1038*04eeddc0SDimitry Andric   ++MI;
1039*04eeddc0SDimitry Andric   unsigned CPUIndex = CPUserIndex + 1;
1040*04eeddc0SDimitry Andric   unsigned NumCPUsers = CPUsers.size();
1041*04eeddc0SDimitry Andric   for (unsigned Offset = UserOffset + TII->getInstSizeInBytes(*UserMI);
1042*04eeddc0SDimitry Andric        Offset < BaseInsertOffset;
1043*04eeddc0SDimitry Andric        Offset += TII->getInstSizeInBytes(*MI), MI = std::next(MI)) {
1044*04eeddc0SDimitry Andric     assert(MI != UserMBB->end() && "Fell off end of block");
1045*04eeddc0SDimitry Andric     if (CPUIndex < NumCPUsers && CPUsers[CPUIndex].MI == MI) {
1046*04eeddc0SDimitry Andric       CPUser &U = CPUsers[CPUIndex];
1047*04eeddc0SDimitry Andric       if (!isOffsetInRange(Offset, EndInsertOffset, U)) {
1048*04eeddc0SDimitry Andric         // Shift intertion point by one unit of alignment so it is within reach.
1049*04eeddc0SDimitry Andric         BaseInsertOffset -= Align.value();
1050*04eeddc0SDimitry Andric         EndInsertOffset -= Align.value();
1051*04eeddc0SDimitry Andric       }
1052*04eeddc0SDimitry Andric       // This is overly conservative, as we don't account for CPEMIs being
1053*04eeddc0SDimitry Andric       // reused within the block, but it doesn't matter much.  Also assume CPEs
1054*04eeddc0SDimitry Andric       // are added in order with alignment padding.  We may eventually be able
1055*04eeddc0SDimitry Andric       // to pack the aligned CPEs better.
1056*04eeddc0SDimitry Andric       EndInsertOffset += U.CPEMI->getOperand(2).getImm();
1057*04eeddc0SDimitry Andric       CPUIndex++;
1058*04eeddc0SDimitry Andric     }
1059*04eeddc0SDimitry Andric   }
1060*04eeddc0SDimitry Andric 
1061*04eeddc0SDimitry Andric   NewMBB = splitBlockBeforeInstr(*--MI);
1062*04eeddc0SDimitry Andric }
1063*04eeddc0SDimitry Andric 
1064*04eeddc0SDimitry Andric /// handleConstantPoolUser - Analyze the specified user, checking to see if it
1065*04eeddc0SDimitry Andric /// is out-of-range.  If so, pick up the constant pool value and move it some
1066*04eeddc0SDimitry Andric /// place in-range.  Return true if we changed any addresses (thus must run
1067*04eeddc0SDimitry Andric /// another pass of branch lengthening), false otherwise.
1068*04eeddc0SDimitry Andric bool CSKYConstantIslands::handleConstantPoolUser(unsigned CPUserIndex) {
1069*04eeddc0SDimitry Andric   CPUser &U = CPUsers[CPUserIndex];
1070*04eeddc0SDimitry Andric   MachineInstr *UserMI = U.MI;
1071*04eeddc0SDimitry Andric   MachineInstr *CPEMI = U.CPEMI;
1072*04eeddc0SDimitry Andric   unsigned CPI = CPEMI->getOperand(1).getIndex();
1073*04eeddc0SDimitry Andric   unsigned Size = CPEMI->getOperand(2).getImm();
1074*04eeddc0SDimitry Andric   // Compute this only once, it's expensive.
1075*04eeddc0SDimitry Andric   unsigned UserOffset = getUserOffset(U);
1076*04eeddc0SDimitry Andric 
1077*04eeddc0SDimitry Andric   // See if the current entry is within range, or there is a clone of it
1078*04eeddc0SDimitry Andric   // in range.
1079*04eeddc0SDimitry Andric   int result = findInRangeCPEntry(U, UserOffset);
1080*04eeddc0SDimitry Andric   if (result == 1)
1081*04eeddc0SDimitry Andric     return false;
1082*04eeddc0SDimitry Andric   if (result == 2)
1083*04eeddc0SDimitry Andric     return true;
1084*04eeddc0SDimitry Andric 
1085*04eeddc0SDimitry Andric   // Look for water where we can place this CPE.
1086*04eeddc0SDimitry Andric   MachineBasicBlock *NewIsland = MF->CreateMachineBasicBlock();
1087*04eeddc0SDimitry Andric   MachineBasicBlock *NewMBB;
1088*04eeddc0SDimitry Andric   water_iterator IP;
1089*04eeddc0SDimitry Andric   if (findAvailableWater(U, UserOffset, IP)) {
1090*04eeddc0SDimitry Andric     LLVM_DEBUG(dbgs() << "Found water in range\n");
1091*04eeddc0SDimitry Andric     MachineBasicBlock *WaterBB = *IP;
1092*04eeddc0SDimitry Andric 
1093*04eeddc0SDimitry Andric     // If the original WaterList entry was "new water" on this iteration,
1094*04eeddc0SDimitry Andric     // propagate that to the new island.  This is just keeping NewWaterList
1095*04eeddc0SDimitry Andric     // updated to match the WaterList, which will be updated below.
1096*04eeddc0SDimitry Andric     if (NewWaterList.erase(WaterBB))
1097*04eeddc0SDimitry Andric       NewWaterList.insert(NewIsland);
1098*04eeddc0SDimitry Andric 
1099*04eeddc0SDimitry Andric     // The new CPE goes before the following block (NewMBB).
1100*04eeddc0SDimitry Andric     NewMBB = &*++WaterBB->getIterator();
1101*04eeddc0SDimitry Andric   } else {
1102*04eeddc0SDimitry Andric     LLVM_DEBUG(dbgs() << "No water found\n");
1103*04eeddc0SDimitry Andric     createNewWater(CPUserIndex, UserOffset, NewMBB);
1104*04eeddc0SDimitry Andric 
1105*04eeddc0SDimitry Andric     // splitBlockBeforeInstr adds to WaterList, which is important when it is
1106*04eeddc0SDimitry Andric     // called while handling branches so that the water will be seen on the
1107*04eeddc0SDimitry Andric     // next iteration for constant pools, but in this context, we don't want
1108*04eeddc0SDimitry Andric     // it.  Check for this so it will be removed from the WaterList.
1109*04eeddc0SDimitry Andric     // Also remove any entry from NewWaterList.
1110*04eeddc0SDimitry Andric     MachineBasicBlock *WaterBB = &*--NewMBB->getIterator();
1111*04eeddc0SDimitry Andric     IP = llvm::find(WaterList, WaterBB);
1112*04eeddc0SDimitry Andric     if (IP != WaterList.end())
1113*04eeddc0SDimitry Andric       NewWaterList.erase(WaterBB);
1114*04eeddc0SDimitry Andric 
1115*04eeddc0SDimitry Andric     // We are adding new water.  Update NewWaterList.
1116*04eeddc0SDimitry Andric     NewWaterList.insert(NewIsland);
1117*04eeddc0SDimitry Andric   }
1118*04eeddc0SDimitry Andric 
1119*04eeddc0SDimitry Andric   // Remove the original WaterList entry; we want subsequent insertions in
1120*04eeddc0SDimitry Andric   // this vicinity to go after the one we're about to insert.  This
1121*04eeddc0SDimitry Andric   // considerably reduces the number of times we have to move the same CPE
1122*04eeddc0SDimitry Andric   // more than once and is also important to ensure the algorithm terminates.
1123*04eeddc0SDimitry Andric   if (IP != WaterList.end())
1124*04eeddc0SDimitry Andric     WaterList.erase(IP);
1125*04eeddc0SDimitry Andric 
1126*04eeddc0SDimitry Andric   // Okay, we know we can put an island before NewMBB now, do it!
1127*04eeddc0SDimitry Andric   MF->insert(NewMBB->getIterator(), NewIsland);
1128*04eeddc0SDimitry Andric 
1129*04eeddc0SDimitry Andric   // Update internal data structures to account for the newly inserted MBB.
1130*04eeddc0SDimitry Andric   updateForInsertedWaterBlock(NewIsland);
1131*04eeddc0SDimitry Andric 
1132*04eeddc0SDimitry Andric   // Decrement the old entry, and remove it if refcount becomes 0.
1133*04eeddc0SDimitry Andric   decrementCPEReferenceCount(CPI, CPEMI);
1134*04eeddc0SDimitry Andric 
1135*04eeddc0SDimitry Andric   // No existing clone of this CPE is within range.
1136*04eeddc0SDimitry Andric   // We will be generating a new clone.  Get a UID for it.
1137*04eeddc0SDimitry Andric   unsigned ID = createPICLabelUId();
1138*04eeddc0SDimitry Andric 
1139*04eeddc0SDimitry Andric   // Now that we have an island to add the CPE to, clone the original CPE and
1140*04eeddc0SDimitry Andric   // add it to the island.
1141*04eeddc0SDimitry Andric   U.HighWaterMark = NewIsland;
1142*04eeddc0SDimitry Andric   U.CPEMI = BuildMI(NewIsland, DebugLoc(), TII->get(CSKY::CONSTPOOL_ENTRY))
1143*04eeddc0SDimitry Andric                 .addImm(ID)
1144*04eeddc0SDimitry Andric                 .addConstantPoolIndex(CPI)
1145*04eeddc0SDimitry Andric                 .addImm(Size);
1146*04eeddc0SDimitry Andric   CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1));
1147*04eeddc0SDimitry Andric   ++NumCPEs;
1148*04eeddc0SDimitry Andric 
1149*04eeddc0SDimitry Andric   // Mark the basic block as aligned as required by the const-pool entry.
1150*04eeddc0SDimitry Andric   NewIsland->setAlignment(getCPEAlign(*U.CPEMI));
1151*04eeddc0SDimitry Andric 
1152*04eeddc0SDimitry Andric   // Increase the size of the island block to account for the new entry.
1153*04eeddc0SDimitry Andric   BBInfo[NewIsland->getNumber()].Size += Size;
1154*04eeddc0SDimitry Andric   adjustBBOffsetsAfter(&*--NewIsland->getIterator());
1155*04eeddc0SDimitry Andric 
1156*04eeddc0SDimitry Andric   // Finally, change the CPI in the instruction operand to be ID.
1157*04eeddc0SDimitry Andric   for (unsigned I = 0, E = UserMI->getNumOperands(); I != E; ++I)
1158*04eeddc0SDimitry Andric     if (UserMI->getOperand(I).isCPI()) {
1159*04eeddc0SDimitry Andric       UserMI->getOperand(I).setIndex(ID);
1160*04eeddc0SDimitry Andric       break;
1161*04eeddc0SDimitry Andric     }
1162*04eeddc0SDimitry Andric 
1163*04eeddc0SDimitry Andric   LLVM_DEBUG(
1164*04eeddc0SDimitry Andric       dbgs() << "  Moved CPE to #" << ID << " CPI=" << CPI
1165*04eeddc0SDimitry Andric              << format(" offset=%#x\n", BBInfo[NewIsland->getNumber()].Offset));
1166*04eeddc0SDimitry Andric 
1167*04eeddc0SDimitry Andric   return true;
1168*04eeddc0SDimitry Andric }
1169*04eeddc0SDimitry Andric 
1170*04eeddc0SDimitry Andric /// removeDeadCPEMI - Remove a dead constant pool entry instruction. Update
1171*04eeddc0SDimitry Andric /// sizes and offsets of impacted basic blocks.
1172*04eeddc0SDimitry Andric void CSKYConstantIslands::removeDeadCPEMI(MachineInstr *CPEMI) {
1173*04eeddc0SDimitry Andric   MachineBasicBlock *CPEBB = CPEMI->getParent();
1174*04eeddc0SDimitry Andric   unsigned Size = CPEMI->getOperand(2).getImm();
1175*04eeddc0SDimitry Andric   CPEMI->eraseFromParent();
1176*04eeddc0SDimitry Andric   BBInfo[CPEBB->getNumber()].Size -= Size;
1177*04eeddc0SDimitry Andric   // All succeeding offsets have the current size value added in, fix this.
1178*04eeddc0SDimitry Andric   if (CPEBB->empty()) {
1179*04eeddc0SDimitry Andric     BBInfo[CPEBB->getNumber()].Size = 0;
1180*04eeddc0SDimitry Andric 
1181*04eeddc0SDimitry Andric     // This block no longer needs to be aligned.
1182*04eeddc0SDimitry Andric     CPEBB->setAlignment(Align(4));
1183*04eeddc0SDimitry Andric   } else {
1184*04eeddc0SDimitry Andric     // Entries are sorted by descending alignment, so realign from the front.
1185*04eeddc0SDimitry Andric     CPEBB->setAlignment(getCPEAlign(*CPEBB->begin()));
1186*04eeddc0SDimitry Andric   }
1187*04eeddc0SDimitry Andric 
1188*04eeddc0SDimitry Andric   adjustBBOffsetsAfter(CPEBB);
1189*04eeddc0SDimitry Andric   // An island has only one predecessor BB and one successor BB. Check if
1190*04eeddc0SDimitry Andric   // this BB's predecessor jumps directly to this BB's successor. This
1191*04eeddc0SDimitry Andric   // shouldn't happen currently.
1192*04eeddc0SDimitry Andric   assert(!bbIsJumpedOver(CPEBB) && "How did this happen?");
1193*04eeddc0SDimitry Andric   // FIXME: remove the empty blocks after all the work is done?
1194*04eeddc0SDimitry Andric }
1195*04eeddc0SDimitry Andric 
1196*04eeddc0SDimitry Andric /// removeUnusedCPEntries - Remove constant pool entries whose refcounts
1197*04eeddc0SDimitry Andric /// are zero.
1198*04eeddc0SDimitry Andric bool CSKYConstantIslands::removeUnusedCPEntries() {
1199*04eeddc0SDimitry Andric   unsigned MadeChange = false;
1200*04eeddc0SDimitry Andric   for (unsigned I = 0, E = CPEntries.size(); I != E; ++I) {
1201*04eeddc0SDimitry Andric     std::vector<CPEntry> &CPEs = CPEntries[I];
1202*04eeddc0SDimitry Andric     for (unsigned J = 0, Ee = CPEs.size(); J != Ee; ++J) {
1203*04eeddc0SDimitry Andric       if (CPEs[J].RefCount == 0 && CPEs[J].CPEMI) {
1204*04eeddc0SDimitry Andric         removeDeadCPEMI(CPEs[J].CPEMI);
1205*04eeddc0SDimitry Andric         CPEs[J].CPEMI = nullptr;
1206*04eeddc0SDimitry Andric         MadeChange = true;
1207*04eeddc0SDimitry Andric       }
1208*04eeddc0SDimitry Andric     }
1209*04eeddc0SDimitry Andric   }
1210*04eeddc0SDimitry Andric   return MadeChange;
1211*04eeddc0SDimitry Andric }
1212*04eeddc0SDimitry Andric 
1213*04eeddc0SDimitry Andric /// isBBInRange - Returns true if the distance between specific MI and
1214*04eeddc0SDimitry Andric /// specific BB can fit in MI's displacement field.
1215*04eeddc0SDimitry Andric bool CSKYConstantIslands::isBBInRange(MachineInstr *MI,
1216*04eeddc0SDimitry Andric                                       MachineBasicBlock *DestBB,
1217*04eeddc0SDimitry Andric                                       unsigned MaxDisp) {
1218*04eeddc0SDimitry Andric   unsigned BrOffset = getOffsetOf(MI);
1219*04eeddc0SDimitry Andric   unsigned DestOffset = BBInfo[DestBB->getNumber()].Offset;
1220*04eeddc0SDimitry Andric 
1221*04eeddc0SDimitry Andric   LLVM_DEBUG(dbgs() << "Branch of destination " << printMBBReference(*DestBB)
1222*04eeddc0SDimitry Andric                     << " from " << printMBBReference(*MI->getParent())
1223*04eeddc0SDimitry Andric                     << " max delta=" << MaxDisp << " from " << getOffsetOf(MI)
1224*04eeddc0SDimitry Andric                     << " to " << DestOffset << " offset "
1225*04eeddc0SDimitry Andric                     << int(DestOffset - BrOffset) << "\t" << *MI);
1226*04eeddc0SDimitry Andric 
1227*04eeddc0SDimitry Andric   if (BrOffset <= DestOffset) {
1228*04eeddc0SDimitry Andric     // Branch before the Dest.
1229*04eeddc0SDimitry Andric     if (DestOffset - BrOffset <= MaxDisp)
1230*04eeddc0SDimitry Andric       return true;
1231*04eeddc0SDimitry Andric   } else {
1232*04eeddc0SDimitry Andric     if (BrOffset - DestOffset <= MaxDisp)
1233*04eeddc0SDimitry Andric       return true;
1234*04eeddc0SDimitry Andric   }
1235*04eeddc0SDimitry Andric   return false;
1236*04eeddc0SDimitry Andric }
1237*04eeddc0SDimitry Andric 
1238*04eeddc0SDimitry Andric /// fixupImmediateBr - Fix up an immediate branch whose destination is too far
1239*04eeddc0SDimitry Andric /// away to fit in its displacement field.
1240*04eeddc0SDimitry Andric bool CSKYConstantIslands::fixupImmediateBr(ImmBranch &Br) {
1241*04eeddc0SDimitry Andric   MachineInstr *MI = Br.MI;
1242*04eeddc0SDimitry Andric   MachineBasicBlock *DestBB = TII->getBranchDestBlock(*MI);
1243*04eeddc0SDimitry Andric 
1244*04eeddc0SDimitry Andric   // Check to see if the DestBB is already in-range.
1245*04eeddc0SDimitry Andric   if (isBBInRange(MI, DestBB, Br.MaxDisp))
1246*04eeddc0SDimitry Andric     return false;
1247*04eeddc0SDimitry Andric 
1248*04eeddc0SDimitry Andric   if (!Br.IsCond)
1249*04eeddc0SDimitry Andric     return fixupUnconditionalBr(Br);
1250*04eeddc0SDimitry Andric   return fixupConditionalBr(Br);
1251*04eeddc0SDimitry Andric }
1252*04eeddc0SDimitry Andric 
1253*04eeddc0SDimitry Andric /// fixupUnconditionalBr - Fix up an unconditional branch whose destination is
1254*04eeddc0SDimitry Andric /// too far away to fit in its displacement field. If the LR register has been
1255*04eeddc0SDimitry Andric /// spilled in the epilogue, then we can use BSR to implement a far jump.
1256*04eeddc0SDimitry Andric /// Otherwise, add an intermediate branch instruction to a branch.
1257*04eeddc0SDimitry Andric bool CSKYConstantIslands::fixupUnconditionalBr(ImmBranch &Br) {
1258*04eeddc0SDimitry Andric   MachineInstr *MI = Br.MI;
1259*04eeddc0SDimitry Andric   MachineBasicBlock *MBB = MI->getParent();
1260*04eeddc0SDimitry Andric 
1261*04eeddc0SDimitry Andric   if (!MFI->isLRSpilled())
1262*04eeddc0SDimitry Andric     report_fatal_error("underestimated function size");
1263*04eeddc0SDimitry Andric 
1264*04eeddc0SDimitry Andric   // Use BSR to implement far jump.
1265*04eeddc0SDimitry Andric   Br.MaxDisp = ((1 << (26 - 1)) - 1) * 2;
1266*04eeddc0SDimitry Andric   MI->setDesc(TII->get(CSKY::BSR32_BR));
1267*04eeddc0SDimitry Andric   BBInfo[MBB->getNumber()].Size += 4;
1268*04eeddc0SDimitry Andric   adjustBBOffsetsAfter(MBB);
1269*04eeddc0SDimitry Andric   ++NumUBrFixed;
1270*04eeddc0SDimitry Andric 
1271*04eeddc0SDimitry Andric   LLVM_DEBUG(dbgs() << "  Changed B to long jump " << *MI);
1272*04eeddc0SDimitry Andric 
1273*04eeddc0SDimitry Andric   return true;
1274*04eeddc0SDimitry Andric }
1275*04eeddc0SDimitry Andric 
1276*04eeddc0SDimitry Andric /// fixupConditionalBr - Fix up a conditional branch whose destination is too
1277*04eeddc0SDimitry Andric /// far away to fit in its displacement field. It is converted to an inverse
1278*04eeddc0SDimitry Andric /// conditional branch + an unconditional branch to the destination.
1279*04eeddc0SDimitry Andric bool CSKYConstantIslands::fixupConditionalBr(ImmBranch &Br) {
1280*04eeddc0SDimitry Andric   MachineInstr *MI = Br.MI;
1281*04eeddc0SDimitry Andric   MachineBasicBlock *DestBB = TII->getBranchDestBlock(*MI);
1282*04eeddc0SDimitry Andric 
1283*04eeddc0SDimitry Andric   SmallVector<MachineOperand, 4> Cond;
1284*04eeddc0SDimitry Andric   Cond.push_back(MachineOperand::CreateImm(MI->getOpcode()));
1285*04eeddc0SDimitry Andric   Cond.push_back(MI->getOperand(0));
1286*04eeddc0SDimitry Andric   TII->reverseBranchCondition(Cond);
1287*04eeddc0SDimitry Andric 
1288*04eeddc0SDimitry Andric   // Add an unconditional branch to the destination and invert the branch
1289*04eeddc0SDimitry Andric   // condition to jump over it:
1290*04eeddc0SDimitry Andric   // bteqz L1
1291*04eeddc0SDimitry Andric   // =>
1292*04eeddc0SDimitry Andric   // bnez L2
1293*04eeddc0SDimitry Andric   // b   L1
1294*04eeddc0SDimitry Andric   // L2:
1295*04eeddc0SDimitry Andric 
1296*04eeddc0SDimitry Andric   // If the branch is at the end of its MBB and that has a fall-through block,
1297*04eeddc0SDimitry Andric   // direct the updated conditional branch to the fall-through block. Otherwise,
1298*04eeddc0SDimitry Andric   // split the MBB before the next instruction.
1299*04eeddc0SDimitry Andric   MachineBasicBlock *MBB = MI->getParent();
1300*04eeddc0SDimitry Andric   MachineInstr *BMI = &MBB->back();
1301*04eeddc0SDimitry Andric   bool NeedSplit = (BMI != MI) || !bbHasFallthrough(MBB);
1302*04eeddc0SDimitry Andric 
1303*04eeddc0SDimitry Andric   ++NumCBrFixed;
1304*04eeddc0SDimitry Andric   if (BMI != MI) {
1305*04eeddc0SDimitry Andric     if (std::next(MachineBasicBlock::iterator(MI)) == std::prev(MBB->end()) &&
1306*04eeddc0SDimitry Andric         BMI->isUnconditionalBranch()) {
1307*04eeddc0SDimitry Andric       // Last MI in the BB is an unconditional branch. Can we simply invert the
1308*04eeddc0SDimitry Andric       // condition and swap destinations:
1309*04eeddc0SDimitry Andric       // beqz L1
1310*04eeddc0SDimitry Andric       // b   L2
1311*04eeddc0SDimitry Andric       // =>
1312*04eeddc0SDimitry Andric       // bnez L2
1313*04eeddc0SDimitry Andric       // b   L1
1314*04eeddc0SDimitry Andric       MachineBasicBlock *NewDest = TII->getBranchDestBlock(*BMI);
1315*04eeddc0SDimitry Andric       if (isBBInRange(MI, NewDest, Br.MaxDisp)) {
1316*04eeddc0SDimitry Andric         LLVM_DEBUG(
1317*04eeddc0SDimitry Andric             dbgs() << "  Invert Bcc condition and swap its destination with "
1318*04eeddc0SDimitry Andric                    << *BMI);
1319*04eeddc0SDimitry Andric         BMI->getOperand(BMI->getNumExplicitOperands() - 1).setMBB(DestBB);
1320*04eeddc0SDimitry Andric         MI->getOperand(MI->getNumExplicitOperands() - 1).setMBB(NewDest);
1321*04eeddc0SDimitry Andric 
1322*04eeddc0SDimitry Andric         MI->setDesc(TII->get(Cond[0].getImm()));
1323*04eeddc0SDimitry Andric         return true;
1324*04eeddc0SDimitry Andric       }
1325*04eeddc0SDimitry Andric     }
1326*04eeddc0SDimitry Andric   }
1327*04eeddc0SDimitry Andric 
1328*04eeddc0SDimitry Andric   if (NeedSplit) {
1329*04eeddc0SDimitry Andric     splitBlockBeforeInstr(*MI);
1330*04eeddc0SDimitry Andric     // No need for the branch to the next block. We're adding an unconditional
1331*04eeddc0SDimitry Andric     // branch to the destination.
1332*04eeddc0SDimitry Andric     int Delta = TII->getInstSizeInBytes(MBB->back());
1333*04eeddc0SDimitry Andric     BBInfo[MBB->getNumber()].Size -= Delta;
1334*04eeddc0SDimitry Andric     MBB->back().eraseFromParent();
1335*04eeddc0SDimitry Andric     // BBInfo[SplitBB].Offset is wrong temporarily, fixed below
1336*04eeddc0SDimitry Andric 
1337*04eeddc0SDimitry Andric     // The conditional successor will be swapped between the BBs after this, so
1338*04eeddc0SDimitry Andric     // update CFG.
1339*04eeddc0SDimitry Andric     MBB->addSuccessor(DestBB);
1340*04eeddc0SDimitry Andric     std::next(MBB->getIterator())->removeSuccessor(DestBB);
1341*04eeddc0SDimitry Andric   }
1342*04eeddc0SDimitry Andric   MachineBasicBlock *NextBB = &*++MBB->getIterator();
1343*04eeddc0SDimitry Andric 
1344*04eeddc0SDimitry Andric   LLVM_DEBUG(dbgs() << "  Insert B to " << printMBBReference(*DestBB)
1345*04eeddc0SDimitry Andric                     << " also invert condition and change dest. to "
1346*04eeddc0SDimitry Andric                     << printMBBReference(*NextBB) << "\n");
1347*04eeddc0SDimitry Andric 
1348*04eeddc0SDimitry Andric   // Insert a new conditional branch and a new unconditional branch.
1349*04eeddc0SDimitry Andric   // Also update the ImmBranch as well as adding a new entry for the new branch.
1350*04eeddc0SDimitry Andric 
1351*04eeddc0SDimitry Andric   BuildMI(MBB, DebugLoc(), TII->get(Cond[0].getImm()))
1352*04eeddc0SDimitry Andric       .addReg(MI->getOperand(0).getReg())
1353*04eeddc0SDimitry Andric       .addMBB(NextBB);
1354*04eeddc0SDimitry Andric 
1355*04eeddc0SDimitry Andric   Br.MI = &MBB->back();
1356*04eeddc0SDimitry Andric   BBInfo[MBB->getNumber()].Size += TII->getInstSizeInBytes(MBB->back());
1357*04eeddc0SDimitry Andric   BuildMI(MBB, DebugLoc(), TII->get(Br.UncondBr)).addMBB(DestBB);
1358*04eeddc0SDimitry Andric   BBInfo[MBB->getNumber()].Size += TII->getInstSizeInBytes(MBB->back());
1359*04eeddc0SDimitry Andric   unsigned MaxDisp = getUnconditionalBrDisp(Br.UncondBr);
1360*04eeddc0SDimitry Andric   ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr));
1361*04eeddc0SDimitry Andric 
1362*04eeddc0SDimitry Andric   // Remove the old conditional branch.  It may or may not still be in MBB.
1363*04eeddc0SDimitry Andric   BBInfo[MI->getParent()->getNumber()].Size -= TII->getInstSizeInBytes(*MI);
1364*04eeddc0SDimitry Andric   MI->eraseFromParent();
1365*04eeddc0SDimitry Andric   adjustBBOffsetsAfter(MBB);
1366*04eeddc0SDimitry Andric   return true;
1367*04eeddc0SDimitry Andric }
1368*04eeddc0SDimitry Andric 
1369*04eeddc0SDimitry Andric /// Returns a pass that converts branches to long branches.
1370*04eeddc0SDimitry Andric FunctionPass *llvm::createCSKYConstantIslandPass() {
1371*04eeddc0SDimitry Andric   return new CSKYConstantIslands();
1372*04eeddc0SDimitry Andric }
1373*04eeddc0SDimitry Andric 
1374*04eeddc0SDimitry Andric INITIALIZE_PASS(CSKYConstantIslands, DEBUG_TYPE,
1375*04eeddc0SDimitry Andric                 "CSKY constant island placement and branch shortening pass",
1376*04eeddc0SDimitry Andric                 false, false)
1377