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