X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTarget%2FMips%2FMipsConstantIslandPass.cpp;h=b864c5517bec2ddf581199b2a6ffcf671cef711c;hb=7225e27b4cd9a3e33478264caac765bf31e3179a;hp=b15ec06441fb9260f3346fd4ef00030460287338;hpb=a2e6e6bcf8cc37ad91b130b9d02d9fe951fbb4d1;p=oota-llvm.git diff --git a/lib/Target/Mips/MipsConstantIslandPass.cpp b/lib/Target/Mips/MipsConstantIslandPass.cpp index b15ec06441f..b864c5517be 100644 --- a/lib/Target/Mips/MipsConstantIslandPass.cpp +++ b/lib/Target/Mips/MipsConstantIslandPass.cpp @@ -17,7 +17,7 @@ // // The constants can be not just numbers but addresses of functions and labels. // This can be particularly helpful in static relocation mode for embedded -// non linux targets. +// non-linux targets. // // @@ -25,6 +25,7 @@ #include "Mips.h" #include "MCTargetDesc/MipsBaseInfo.h" +#include "Mips16InstrInfo.h" #include "MipsMachineFunction.h" #include "MipsTargetMachine.h" #include "llvm/ADT/Statistic.h" @@ -33,15 +34,15 @@ #include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/IR/Function.h" +#include "llvm/IR/InstIterator.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" -#include "llvm/Support/InstIterator.h" +#include "llvm/Support/Format.h" #include "llvm/Support/MathExtras.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetRegisterInfo.h" -#include "llvm/Support/Format.h" #include using namespace llvm; @@ -66,16 +67,122 @@ static cl::opt ConstantIslandsSmallOffset( cl::desc("Make small offsets be this amount for testing purposes"), cl::Hidden); -/// UnknownPadding - Return the worst case padding that could result from -/// unknown offset bits. This does not include alignment padding caused by -/// known offset bits. -/// -/// @param LogAlign log2(alignment) -/// @param KnownBits Number of known low offset bits. -static inline unsigned UnknownPadding(unsigned LogAlign, unsigned KnownBits) { - if (KnownBits < LogAlign) - return (1u << LogAlign) - (1u << KnownBits); - return 0; +// +// For testing purposes we tell it to not use relaxed load forms so that it +// will split blocks. +// +static cl::opt NoLoadRelaxation( + "mips-constant-islands-no-load-relaxation", + cl::init(false), + cl::desc("Don't relax loads to long loads - for testing purposes"), + cl::Hidden); + +static unsigned int branchTargetOperand(MachineInstr *MI) { + switch (MI->getOpcode()) { + case Mips::Bimm16: + case Mips::BimmX16: + case Mips::Bteqz16: + case Mips::BteqzX16: + case Mips::Btnez16: + case Mips::BtnezX16: + case Mips::JalB16: + return 0; + case Mips::BeqzRxImm16: + case Mips::BeqzRxImmX16: + case Mips::BnezRxImm16: + case Mips::BnezRxImmX16: + return 1; + } + llvm_unreachable("Unknown branch type"); +} + +static bool isUnconditionalBranch(unsigned int Opcode) { + switch (Opcode) { + default: return false; + case Mips::Bimm16: + case Mips::BimmX16: + case Mips::JalB16: + return true; + } +} + +static unsigned int longformBranchOpcode(unsigned int Opcode) { + switch (Opcode) { + case Mips::Bimm16: + case Mips::BimmX16: + return Mips::BimmX16; + case Mips::Bteqz16: + case Mips::BteqzX16: + return Mips::BteqzX16; + case Mips::Btnez16: + case Mips::BtnezX16: + return Mips::BtnezX16; + case Mips::JalB16: + return Mips::JalB16; + case Mips::BeqzRxImm16: + case Mips::BeqzRxImmX16: + return Mips::BeqzRxImmX16; + case Mips::BnezRxImm16: + case Mips::BnezRxImmX16: + return Mips::BnezRxImmX16; + } + llvm_unreachable("Unknown branch type"); +} + +// +// FIXME: need to go through this whole constant islands port and check the math +// for branch ranges and clean this up and make some functions to calculate things +// that are done many times identically. +// Need to refactor some of the code to call this routine. +// +static unsigned int branchMaxOffsets(unsigned int Opcode) { + unsigned Bits, Scale; + switch (Opcode) { + case Mips::Bimm16: + Bits = 11; + Scale = 2; + break; + case Mips::BimmX16: + Bits = 16; + Scale = 2; + break; + case Mips::BeqzRxImm16: + Bits = 8; + Scale = 2; + break; + case Mips::BeqzRxImmX16: + Bits = 16; + Scale = 2; + break; + case Mips::BnezRxImm16: + Bits = 8; + Scale = 2; + break; + case Mips::BnezRxImmX16: + Bits = 16; + Scale = 2; + break; + case Mips::Bteqz16: + Bits = 8; + Scale = 2; + break; + case Mips::BteqzX16: + Bits = 16; + Scale = 2; + break; + case Mips::Btnez16: + Bits = 8; + Scale = 2; + break; + case Mips::BtnezX16: + Bits = 16; + Scale = 2; + break; + default: + llvm_unreachable("Unknown branch type"); + } + unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale; + return MaxOffs; } namespace { @@ -119,52 +226,15 @@ namespace { /// beginning of the block, or from an aligned jump table at the end. unsigned Size; - /// KnownBits - The number of low bits in Offset that are known to be - /// exact. The remaining bits of Offset are an upper bound. - uint8_t KnownBits; - - /// Unalign - When non-zero, the block contains instructions (inline asm) - /// of unknown size. The real size may be smaller than Size bytes by a - /// multiple of 1 << Unalign. - uint8_t Unalign; - - /// PostAlign - When non-zero, the block terminator contains a .align - /// directive, so the end of the block is aligned to 1 << PostAlign - /// bytes. - uint8_t PostAlign; - - BasicBlockInfo() : Offset(0), Size(0), KnownBits(0), Unalign(0), - PostAlign(0) {} - - /// Compute the number of known offset bits internally to this block. - /// This number should be used to predict worst case padding when - /// splitting the block. - unsigned internalKnownBits() const { - unsigned Bits = Unalign ? Unalign : KnownBits; - // If the block size isn't a multiple of the known bits, assume the - // worst case padding. - if (Size & ((1u << Bits) - 1)) - Bits = countTrailingZeros(Size); - return Bits; - } - - /// Compute the offset immediately following this block. If LogAlign is - /// specified, return the offset the successor block will get if it has - /// this alignment. + // FIXME: ignore LogAlign for this patch + // unsigned postOffset(unsigned LogAlign = 0) const { unsigned PO = Offset + Size; return PO; } - /// Compute the number of known low bits of postOffset. If this block - /// contains inline asm, the number of known bits drops to the - /// instruction alignment. An aligned terminator may increase the number - /// of know bits. - /// If LogAlign is given, also consider the alignment of the next block. - unsigned postKnownBits(unsigned LogAlign = 0) const { - return std::max(std::max(unsigned(PostAlign), LogAlign), - internalKnownBits()); - } + BasicBlockInfo() : Offset(0), Size(0) {} + }; std::vector BBInfo; @@ -203,26 +273,25 @@ namespace { unsigned LongFormOpcode; public: bool NegOk; - bool IsSoImm; - bool KnownAlignment; CPUser(MachineInstr *mi, MachineInstr *cpemi, unsigned maxdisp, - bool neg, bool soimm, + bool neg, unsigned longformmaxdisp, unsigned longformopcode) : MI(mi), CPEMI(cpemi), MaxDisp(maxdisp), LongFormMaxDisp(longformmaxdisp), LongFormOpcode(longformopcode), - NegOk(neg), IsSoImm(soimm), KnownAlignment(false) { + NegOk(neg){ HighWaterMark = CPEMI->getParent(); } /// getMaxDisp - Returns the maximum displacement supported by MI. - /// Correct for unknown alignment. - /// Conservatively subtract 2 bytes to handle weird alignment effects. unsigned getMaxDisp() const { unsigned xMaxDisp = ConstantIslandsSmallOffset? ConstantIslandsSmallOffset: MaxDisp; - return (KnownAlignment ? xMaxDisp : xMaxDisp - 2) - 2; + return xMaxDisp; + } + void setMaxDisp(unsigned val) { + MaxDisp = val; } unsigned getLongFormMaxDisp() const { - return (KnownAlignment ? LongFormMaxDisp : LongFormMaxDisp - 2) - 2; + return LongFormMaxDisp; } unsigned getLongFormOpcode() const { return LongFormOpcode; @@ -276,7 +345,7 @@ namespace { bool IsPIC; unsigned ABI; const MipsSubtarget *STI; - const MipsInstrInfo *TII; + const Mips16InstrInfo *TII; MipsFunctionInfo *MFI; MachineFunction *MF; MachineConstantPool *MCP; @@ -318,7 +387,7 @@ namespace { void verify(); bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset, - unsigned Disp, bool NegativeOK, bool IsSoImm = false); + unsigned Disp, bool NegativeOK); bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset, const CPUser &U); @@ -363,14 +432,14 @@ bool MipsConstantIslands::isLongFormOffsetInRange (unsigned UserOffset, unsigned TrialOffset, const CPUser &U) { return isOffsetInRange(UserOffset, TrialOffset, - U.getLongFormMaxDisp(), U.NegOk, U.IsSoImm); + U.getLongFormMaxDisp(), U.NegOk); } bool MipsConstantIslands::isOffsetInRange (unsigned UserOffset, unsigned TrialOffset, const CPUser &U) { return isOffsetInRange(UserOffset, TrialOffset, - U.getMaxDisp(), U.NegOk, U.IsSoImm); + U.getMaxDisp(), U.NegOk); } /// print block size and offset information - debugging void MipsConstantIslands::dumpBBs() { @@ -378,9 +447,6 @@ void MipsConstantIslands::dumpBBs() { for (unsigned J = 0, E = BBInfo.size(); J !=E; ++J) { const BasicBlockInfo &BBI = BBInfo[J]; dbgs() << format("%08x BB#%u\t", BBI.Offset, J) - << " kb=" << unsigned(BBI.KnownBits) - << " ua=" << unsigned(BBI.Unalign) - << " pa=" << unsigned(BBI.PostAlign) << format(" size=%#x\n", BBInfo[J].Size); } }); @@ -401,7 +467,7 @@ bool MipsConstantIslands::runOnMachineFunction(MachineFunction &mf) { !MipsSubtarget::useConstantIslands()) { return false; } - TII = (const MipsInstrInfo*)MF->getTarget().getInstrInfo(); + TII = (const Mips16InstrInfo*)MF->getTarget().getInstrInfo(); MFI = MF->getInfo(); DEBUG(dbgs() << "constant island processing " << "\n"); // @@ -458,13 +524,11 @@ bool MipsConstantIslands::runOnMachineFunction(MachineFunction &mf) { DEBUG(dbgs() << "Beginning BR iteration #" << NoBRIters << '\n'); bool BRChange = false; -#ifdef IN_PROGRESS for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i) BRChange |= fixupImmediateBr(ImmBranches[i]); if (BRChange && ++NoBRIters > 30) report_fatal_error("Branch Fix Up pass failed to converge!"); DEBUG(dumpBBs()); -#endif if (!CPChange && !BRChange) break; MadeChange = true; @@ -552,10 +616,10 @@ static bool BBHasFallthrough(MachineBasicBlock *MBB) { // Get the next machine basic block in the function. MachineFunction::iterator MBBI = MBB; // Can't fall off end of function. - if (llvm::next(MBBI) == MBB->getParent()->end()) + if (std::next(MBBI) == MBB->getParent()->end()) return false; - MachineBasicBlock *NextBB = llvm::next(MBBI); + MachineBasicBlock *NextBB = std::next(MBBI); for (MachineBasicBlock::succ_iterator I = MBB->succ_begin(), E = MBB->succ_end(); I != E; ++I) if (*I == NextBB) @@ -610,9 +674,6 @@ initializeFunctionInfo(const std::vector &CPEMIs) { for (MachineFunction::iterator I = MF->begin(), E = MF->end(); I != E; ++I) computeBlockSize(I); - // The known bits of the entry block offset are determined by the function - // alignment. - BBInfo.front().KnownBits = MF->getAlignment(); // Compute block offsets. adjustBBOffsetsAfter(MF->begin()); @@ -637,18 +698,73 @@ initializeFunctionInfo(const std::vector &CPEMIs) { unsigned Bits = 0; unsigned Scale = 1; int UOpc = Opc; - switch (Opc) { default: - continue; // Ignore other JT branches + continue; // Ignore other branches for now + case Mips::Bimm16: + Bits = 11; + Scale = 2; + isCond = false; + break; + case Mips::BimmX16: + Bits = 16; + Scale = 2; + isCond = false; + break; + case Mips::BeqzRxImm16: + UOpc=Mips::Bimm16; + Bits = 8; + Scale = 2; + isCond = true; + break; + case Mips::BeqzRxImmX16: + UOpc=Mips::Bimm16; + Bits = 16; + Scale = 2; + isCond = true; + break; + case Mips::BnezRxImm16: + UOpc=Mips::Bimm16; + Bits = 8; + Scale = 2; + isCond = true; + break; + case Mips::BnezRxImmX16: + UOpc=Mips::Bimm16; + Bits = 16; + Scale = 2; + isCond = true; + break; + case Mips::Bteqz16: + UOpc=Mips::Bimm16; + Bits = 8; + Scale = 2; + isCond = true; + break; + case Mips::BteqzX16: + UOpc=Mips::Bimm16; + Bits = 16; + Scale = 2; + isCond = true; + break; + case Mips::Btnez16: + UOpc=Mips::Bimm16; + Bits = 8; + Scale = 2; + isCond = true; + break; + case Mips::BtnezX16: + UOpc=Mips::Bimm16; + Bits = 16; + Scale = 2; + isCond = true; + break; } // Record this immediate branch. unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale; ImmBranches.push_back(ImmBranch(I, MaxOffs, isCond, UOpc)); - } - if (Opc == Mips::CONSTPOOL_ENTRY) continue; @@ -664,7 +780,6 @@ initializeFunctionInfo(const std::vector &CPEMIs) { unsigned Bits = 0; unsigned Scale = 1; bool NegOk = false; - bool IsSoImm = false; unsigned LongFormBits = 0; unsigned LongFormScale = 0; unsigned LongFormOpcode = 0; @@ -673,12 +788,15 @@ initializeFunctionInfo(const std::vector &CPEMIs) { llvm_unreachable("Unknown addressing mode for CP reference!"); case Mips::LwRxPcTcp16: Bits = 8; - Scale = 2; + Scale = 4; LongFormOpcode = Mips::LwRxPcTcpX16; + LongFormBits = 14; + LongFormScale = 1; break; case Mips::LwRxPcTcpX16: - Bits = 16; - Scale = 2; + Bits = 14; + Scale = 1; + NegOk = true; break; } // Remember that this is a user of a CP entry. @@ -687,8 +805,7 @@ initializeFunctionInfo(const std::vector &CPEMIs) { unsigned MaxOffs = ((1 << Bits)-1) * Scale; unsigned LongFormMaxOffs = ((1 << LongFormBits)-1) * LongFormScale; CPUsers.push_back(CPUser(I, CPEMI, MaxOffs, NegOk, - IsSoImm, LongFormMaxOffs, - LongFormOpcode)); + LongFormMaxOffs, LongFormOpcode)); // Increment corresponding CPEntry reference count. CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); @@ -711,8 +828,6 @@ initializeFunctionInfo(const std::vector &CPEMIs) { void MipsConstantIslands::computeBlockSize(MachineBasicBlock *MBB) { BasicBlockInfo &BBI = BBInfo[MBB->getNumber()]; BBI.Size = 0; - BBI.Unalign = 0; - BBI.PostAlign = 0; for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ++I) @@ -766,23 +881,8 @@ void MipsConstantIslands::updateForInsertedWaterBlock WaterList.insert(IP, NewBB); } -/// getUserOffset - Compute the offset of U.MI as seen by the hardware -/// displacement computation. Update U.KnownAlignment to match its current -/// basic block location. unsigned MipsConstantIslands::getUserOffset(CPUser &U) const { - unsigned UserOffset = getOffsetOf(U.MI); - const BasicBlockInfo &BBI = BBInfo[U.MI->getParent()->getNumber()]; - unsigned KnownBits = BBI.internalKnownBits(); - - // The value read from PC is offset from the actual instruction address. - - - // Because of inline assembly, we may not know the alignment (mod 4) of U.MI. - // Make sure U.getMaxDisp() returns a constrained range. - U.KnownAlignment = (KnownBits >= 2); - - - return UserOffset; + return getOffsetOf(U.MI); } /// Split the basic block containing MI into two blocks, which are joined by @@ -805,7 +905,7 @@ MachineBasicBlock *MipsConstantIslands::splitBlockBeforeInstr // Note the new unconditional branch is not being recorded. // There doesn't seem to be meaningful DebugInfo available; this doesn't // correspond to anything in the source. - BuildMI(OrigBB, DebugLoc(), TII->get(Mips::BimmX16)).addMBB(NewBB); + BuildMI(OrigBB, DebugLoc(), TII->get(Mips::Bimm16)).addMBB(NewBB); ++NumSplit; // Update the CFG. All succs of OrigBB are now succs of NewBB. @@ -832,7 +932,7 @@ MachineBasicBlock *MipsConstantIslands::splitBlockBeforeInstr CompareMBBNumbers); MachineBasicBlock* WaterBB = *IP; if (WaterBB == OrigBB) - WaterList.insert(llvm::next(IP), NewBB); + WaterList.insert(std::next(IP), NewBB); else WaterList.insert(IP, OrigBB); NewWaterList.insert(OrigBB); @@ -859,21 +959,16 @@ MachineBasicBlock *MipsConstantIslands::splitBlockBeforeInstr /// isOffsetInRange - Checks whether UserOffset (the location of a constant pool /// reference) is within MaxDisp of TrialOffset (a proposed location of a /// constant pool entry). -/// UserOffset is computed by getUserOffset above to include PC adjustments. If -/// the mod 4 alignment of UserOffset is not known, the uncertainty must be -/// subtracted from MaxDisp instead. CPUser::getMaxDisp() does that. bool MipsConstantIslands::isOffsetInRange(unsigned UserOffset, unsigned TrialOffset, unsigned MaxDisp, - bool NegativeOK, bool IsSoImm) { + bool NegativeOK) { if (UserOffset <= TrialOffset) { // User before the Trial. if (TrialOffset - UserOffset <= MaxDisp) return true; - // FIXME: Make use full range of soimm values. } else if (NegativeOK) { if (UserOffset - TrialOffset <= MaxDisp) return true; - // FIXME: Make use full range of soimm values. } return false; } @@ -912,7 +1007,7 @@ bool MipsConstantIslands::isWaterInRange(unsigned UserOffset, // the offset of the instruction. Also account for unknown alignment padding // in blocks between CPE and the user. if (CPEOffset < UserOffset) - UserOffset += Growth + UnknownPadding(MF->getAlignment(), CPELogAlign); + UserOffset += Growth; } else // CPE fits in existing padding. Growth = 0; @@ -954,7 +1049,7 @@ static bool BBIsJumpedOver(MachineBasicBlock *MBB) { MachineBasicBlock *Succ = *MBB->succ_begin(); MachineBasicBlock *Pred = *MBB->pred_begin(); MachineInstr *PredMI = &Pred->back(); - if (PredMI->getOpcode() == Mips::BimmX16) + if (PredMI->getOpcode() == Mips::Bimm16) return PredMI->getOperand(0).getMBB() == Succ; return false; } @@ -965,7 +1060,7 @@ void MipsConstantIslands::adjustBBOffsetsAfter(MachineBasicBlock *BB) { for(unsigned i = BBNum + 1, e = MF->getNumBlockIDs(); i < e; ++i) { // Get the offset and known bits at the end of the layout predecessor. // Include the alignment of the current block. - unsigned Offset = BBInfo[i - 1].postOffset(); + unsigned Offset = BBInfo[i - 1].Offset + BBInfo[i - 1].Size; BBInfo[i].Offset = Offset; } } @@ -1059,6 +1154,7 @@ int MipsConstantIslands::findLongFormInRangeCPEntry true)) { DEBUG(dbgs() << "In range\n"); UserMI->setDesc(TII->get(U.getLongFormOpcode())); + U.setMaxDisp(U.getLongFormMaxDisp()); return 2; // instruction is longer length now } @@ -1098,6 +1194,8 @@ int MipsConstantIslands::findLongFormInRangeCPEntry /// the specific unconditional branch instruction. static inline unsigned getUnconditionalBrDisp(int Opc) { switch (Opc) { + case Mips::Bimm16: + return ((1<<10)-1)*2; case Mips::BimmX16: return ((1<<16)-1)*2; default: @@ -1120,7 +1218,7 @@ bool MipsConstantIslands::findAvailableWater(CPUser &U, unsigned UserOffset, return false; unsigned BestGrowth = ~0u; - for (water_iterator IP = prior(WaterList.end()), B = WaterList.begin();; + for (water_iterator IP = std::prev(WaterList.end()), B = WaterList.begin();; --IP) { MachineBasicBlock* WaterBB = *IP; // Check if water is in range and is either at a lower address than the @@ -1179,13 +1277,13 @@ void MipsConstantIslands::createNewWater(unsigned CPUserIndex, if (isOffsetInRange(UserOffset, CPEOffset, U)) { DEBUG(dbgs() << "Split at end of BB#" << UserMBB->getNumber() << format(", expected CPE offset %#x\n", CPEOffset)); - NewMBB = llvm::next(MachineFunction::iterator(UserMBB)); + NewMBB = std::next(MachineFunction::iterator(UserMBB)); // Add an unconditional branch from UserMBB to fallthrough block. Record // it for branch lengthening; this new branch will not get out of range, // but if the preceding conditional branch is out of range, the targets // will be exchanged, and the altered branch may be out of range, so the // machinery has to know about it. - int UncondBr = Mips::BimmX16; + int UncondBr = Mips::Bimm16; BuildMI(UserMBB, DebugLoc(), TII->get(UncondBr)).addMBB(NewMBB); unsigned MaxDisp = getUnconditionalBrDisp(UncondBr); ImmBranches.push_back(ImmBranch(&UserMBB->back(), @@ -1203,9 +1301,7 @@ void MipsConstantIslands::createNewWater(unsigned CPUserIndex, // LogAlign which is the largest possible alignment in the function. unsigned LogAlign = MF->getAlignment(); assert(LogAlign >= CPELogAlign && "Over-aligned constant pool entry"); - unsigned KnownBits = UserBBI.internalKnownBits(); - unsigned UPad = UnknownPadding(LogAlign, KnownBits); - unsigned BaseInsertOffset = UserOffset + U.getMaxDisp() - UPad; + unsigned BaseInsertOffset = UserOffset + U.getMaxDisp(); DEBUG(dbgs() << format("Split in middle of big block before %#x", BaseInsertOffset)); @@ -1215,19 +1311,17 @@ void MipsConstantIslands::createNewWater(unsigned CPUserIndex, BaseInsertOffset -= 4; DEBUG(dbgs() << format(", adjusted to %#x", BaseInsertOffset) - << " la=" << LogAlign - << " kb=" << KnownBits - << " up=" << UPad << '\n'); + << " la=" << LogAlign << '\n'); // This could point off the end of the block if we've already got constant // pool entries following this block; only the last one is in the water list. // Back past any possible branches (allow for a conditional and a maximally // long unconditional). if (BaseInsertOffset + 8 >= UserBBI.postOffset()) { - BaseInsertOffset = UserBBI.postOffset() - UPad - 8; + BaseInsertOffset = UserBBI.postOffset() - 8; DEBUG(dbgs() << format("Move inside block: %#x\n", BaseInsertOffset)); } - unsigned EndInsertOffset = BaseInsertOffset + 4 + UPad + + unsigned EndInsertOffset = BaseInsertOffset + 4 + CPEMI->getOperand(2).getImm(); MachineBasicBlock::iterator MI = UserMI; ++MI; @@ -1236,8 +1330,7 @@ void MipsConstantIslands::createNewWater(unsigned CPUserIndex, //MachineInstr *LastIT = 0; for (unsigned Offset = UserOffset+TII->GetInstSizeInBytes(UserMI); Offset < BaseInsertOffset; - Offset += TII->GetInstSizeInBytes(MI), - MI = llvm::next(MI)) { + Offset += TII->GetInstSizeInBytes(MI), MI = std::next(MI)) { assert(MI != UserMBB->end() && "Fell off end of block"); if (CPUIndex < NumCPUsers && CPUsers[CPUIndex].MI == MI) { CPUser &U = CPUsers[CPUIndex]; @@ -1294,15 +1387,16 @@ bool MipsConstantIslands::handleConstantPoolUser(unsigned CPUserIndex) { NewWaterList.insert(NewIsland); // The new CPE goes before the following block (NewMBB). - NewMBB = llvm::next(MachineFunction::iterator(WaterBB)); + NewMBB = std::next(MachineFunction::iterator(WaterBB)); } else { // No water found. // we first see if a longer form of the instrucion could have reached // the constant. in that case we won't bother to split -#ifdef IN_PROGRESS - result = findLongFormInRangeCPEntry(U, UserOffset); -#endif + if (!NoLoadRelaxation) { + result = findLongFormInRangeCPEntry(U, UserOffset); + if (result != 0) return true; + } DEBUG(dbgs() << "No water found\n"); createNewWater(CPUserIndex, UserOffset, NewMBB); @@ -1311,7 +1405,7 @@ bool MipsConstantIslands::handleConstantPoolUser(unsigned CPUserIndex) { // next iteration for constant pools, but in this context, we don't want // it. Check for this so it will be removed from the WaterList. // Also remove any entry from NewWaterList. - MachineBasicBlock *WaterBB = prior(MachineFunction::iterator(NewMBB)); + MachineBasicBlock *WaterBB = std::prev(MachineFunction::iterator(NewMBB)); IP = std::find(WaterList.begin(), WaterList.end(), WaterBB); if (IP != WaterList.end()) NewWaterList.erase(WaterBB); @@ -1336,6 +1430,10 @@ bool MipsConstantIslands::handleConstantPoolUser(unsigned CPUserIndex) { // Decrement the old entry, and remove it if refcount becomes 0. decrementCPEReferenceCount(CPI, CPEMI); + // No existing clone of this CPE is within range. + // We will be generating a new clone. Get a UID for it. + unsigned ID = createPICLabelUId(); + // Now that we have an island to add the CPE to, clone the original CPE and // add it to the island. U.HighWaterMark = NewIsland; @@ -1349,11 +1447,9 @@ bool MipsConstantIslands::handleConstantPoolUser(unsigned CPUserIndex) { // Increase the size of the island block to account for the new entry. BBInfo[NewIsland->getNumber()].Size += Size; - adjustBBOffsetsAfter(llvm::prior(MachineFunction::iterator(NewIsland))); + adjustBBOffsetsAfter(std::prev(MachineFunction::iterator(NewIsland))); + - // No existing clone of this CPE is within range. - // We will be generating a new clone. Get a UID for it. - unsigned ID = createPICLabelUId(); // Finally, change the CPI in the instruction operand to be ID. for (unsigned i = 0, e = UserMI->getNumOperands(); i != e; ++i) @@ -1441,7 +1537,8 @@ unsigned PCAdj = 4; /// away to fit in its displacement field. bool MipsConstantIslands::fixupImmediateBr(ImmBranch &Br) { MachineInstr *MI = Br.MI; - MachineBasicBlock *DestBB = MI->getOperand(0).getMBB(); + unsigned TargetOperand = branchTargetOperand(MI); + MachineBasicBlock *DestBB = MI->getOperand(TargetOperand).getMBB(); // Check to see if the DestBB is already in-range. if (isBBInRange(MI, DestBB, Br.MaxDisp)) @@ -1460,9 +1557,29 @@ bool MipsConstantIslands::fixupUnconditionalBr(ImmBranch &Br) { MachineInstr *MI = Br.MI; MachineBasicBlock *MBB = MI->getParent(); + MachineBasicBlock *DestBB = MI->getOperand(0).getMBB(); // Use BL to implement far jump. - Br.MaxDisp = ((1 << 16)-1) * 2; - MI->setDesc(TII->get(Mips::BimmX16)); + unsigned BimmX16MaxDisp = ((1 << 16)-1) * 2; + if (isBBInRange(MI, DestBB, BimmX16MaxDisp)) { + Br.MaxDisp = BimmX16MaxDisp; + MI->setDesc(TII->get(Mips::BimmX16)); + } + else { + // need to give the math a more careful look here + // this is really a segment address and not + // a PC relative address. FIXME. But I think that + // just reducing the bits by 1 as I've done is correct. + // The basic block we are branching too much be longword aligned. + // we know that RA is saved because we always save it right now. + // this requirement will be relaxed later but we also have an alternate + // way to implement this that I will implement that does not need jal. + // We should have a way to back out this alignment restriction if we "can" later. + // but it is not harmful. + // + DestBB->setAlignment(2); + Br.MaxDisp = ((1<<24)-1) * 2; + MI->setDesc(TII->get(Mips::JalB16)); + } BBInfo[MBB->getNumber()].Size += 2; adjustBBOffsetsAfter(MBB); HasFarJump = true; @@ -1473,23 +1590,33 @@ MipsConstantIslands::fixupUnconditionalBr(ImmBranch &Br) { return true; } + /// fixupConditionalBr - Fix up a conditional branch whose destination is too /// far away to fit in its displacement field. It is converted to an inverse /// conditional branch + an unconditional branch to the destination. bool MipsConstantIslands::fixupConditionalBr(ImmBranch &Br) { MachineInstr *MI = Br.MI; - MachineBasicBlock *DestBB = MI->getOperand(0).getMBB(); + unsigned TargetOperand = branchTargetOperand(MI); + MachineBasicBlock *DestBB = MI->getOperand(TargetOperand).getMBB(); + unsigned Opcode = MI->getOpcode(); + unsigned LongFormOpcode = longformBranchOpcode(Opcode); + unsigned LongFormMaxOff = branchMaxOffsets(LongFormOpcode); + + // Check to see if the DestBB is already in-range. + if (isBBInRange(MI, DestBB, LongFormMaxOff)) { + Br.MaxDisp = LongFormMaxOff; + MI->setDesc(TII->get(LongFormOpcode)); + return true; + } // Add an unconditional branch to the destination and invert the branch // condition to jump over it: - // blt L1 + // bteqz L1 // => - // bge L2 + // bnez L2 // b L1 // L2: - unsigned CCReg = 0; // FIXME - unsigned CC=0; //FIXME // If the branch is at the end of its MBB and that has a fall-through block, // direct the updated conditional branch to the fall-through block. Otherwise, @@ -1497,29 +1624,34 @@ MipsConstantIslands::fixupConditionalBr(ImmBranch &Br) { MachineBasicBlock *MBB = MI->getParent(); MachineInstr *BMI = &MBB->back(); bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB); - + unsigned OppositeBranchOpcode = TII->getOppositeBranchOpc(Opcode); + ++NumCBrFixed; if (BMI != MI) { - if (llvm::next(MachineBasicBlock::iterator(MI)) == prior(MBB->end()) && - BMI->getOpcode() == Br.UncondBr) { + if (std::next(MachineBasicBlock::iterator(MI)) == std::prev(MBB->end()) && + isUnconditionalBranch(BMI->getOpcode())) { // Last MI in the BB is an unconditional branch. Can we simply invert the // condition and swap destinations: - // beq L1 + // beqz L1 // b L2 // => - // bne L2 + // bnez L2 // b L1 - MachineBasicBlock *NewDest = BMI->getOperand(0).getMBB(); + unsigned BMITargetOperand = branchTargetOperand(BMI); + MachineBasicBlock *NewDest = + BMI->getOperand(BMITargetOperand).getMBB(); if (isBBInRange(MI, NewDest, Br.MaxDisp)) { DEBUG(dbgs() << " Invert Bcc condition and swap its destination with " << *BMI); - BMI->getOperand(0).setMBB(DestBB); - MI->getOperand(0).setMBB(NewDest); + MI->setDesc(TII->get(OppositeBranchOpcode)); + BMI->getOperand(BMITargetOperand).setMBB(DestBB); + MI->getOperand(TargetOperand).setMBB(NewDest); return true; } } } + if (NeedSplit) { splitBlockBeforeInstr(MI); // No need for the branch to the next block. We're adding an unconditional @@ -1529,7 +1661,7 @@ MipsConstantIslands::fixupConditionalBr(ImmBranch &Br) { MBB->back().eraseFromParent(); // BBInfo[SplitBB].Offset is wrong temporarily, fixed below } - MachineBasicBlock *NextBB = llvm::next(MachineFunction::iterator(MBB)); + MachineBasicBlock *NextBB = std::next(MachineFunction::iterator(MBB)); DEBUG(dbgs() << " Insert B to BB#" << DestBB->getNumber() << " also invert condition and change dest. to BB#" @@ -1537,8 +1669,14 @@ MipsConstantIslands::fixupConditionalBr(ImmBranch &Br) { // Insert a new conditional branch and a new unconditional branch. // Also update the ImmBranch as well as adding a new entry for the new branch. - BuildMI(MBB, DebugLoc(), TII->get(MI->getOpcode())) - .addMBB(NextBB).addImm(CC).addReg(CCReg); + if (MI->getNumExplicitOperands() == 2) { + BuildMI(MBB, DebugLoc(), TII->get(OppositeBranchOpcode)) + .addReg(MI->getOperand(0).getReg()) + .addMBB(NextBB); + } else { + BuildMI(MBB, DebugLoc(), TII->get(OppositeBranchOpcode)) + .addMBB(NextBB); + } Br.MI = &MBB->back(); BBInfo[MBB->getNumber()].Size += TII->GetInstSizeInBytes(&MBB->back()); BuildMI(MBB, DebugLoc(), TII->get(Br.UncondBr)).addMBB(DestBB); @@ -1557,13 +1695,13 @@ MipsConstantIslands::fixupConditionalBr(ImmBranch &Br) { void MipsConstantIslands::prescanForConstants() { unsigned J = 0; (void)J; - PrescannedForConstants = true; for (MachineFunction::iterator B = MF->begin(), E = MF->end(); B != E; ++B) { for (MachineBasicBlock::instr_iterator I = B->instr_begin(), EB = B->instr_end(); I != EB; ++I) { switch(I->getDesc().getOpcode()) { case Mips::LwConstant32: { + PrescannedForConstants = true; DEBUG(dbgs() << "constant island constant " << *I << "\n"); J = I->getNumOperands(); DEBUG(dbgs() << "num operands " << J << "\n");