X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTarget%2FMips%2FMipsLongBranch.cpp;h=71a6f4d4a11e074c9bccfaacd59764d44ddf169d;hb=d5dd8ce2a5336df4e4b4cc04d23e4018d93944f9;hp=f78203f705313c4926aec157fa473e35b5668c8e;hpb=0bc1adbbc4fdc6d85a671ed70a1bbd345dba445d;p=oota-llvm.git diff --git a/lib/Target/Mips/MipsLongBranch.cpp b/lib/Target/Mips/MipsLongBranch.cpp index f78203f7053..71a6f4d4a11 100644 --- a/lib/Target/Mips/MipsLongBranch.cpp +++ b/lib/Target/Mips/MipsLongBranch.cpp @@ -10,17 +10,18 @@ // This pass expands a branch or jump instruction into a long branch if its // offset is too large to fit into its immediate field. // +// FIXME: Fix pc-region jump instructions which cross 256MB segment boundaries. //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "mips-long-branch" - #include "Mips.h" -#include "MipsTargetMachine.h" #include "MCTargetDesc/MipsBaseInfo.h" +#include "MCTargetDesc/MipsMCNaCl.h" +#include "MipsMachineFunction.h" +#include "MipsTargetMachine.h" #include "llvm/ADT/Statistic.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstrBuilder.h" -#include "llvm/Function.h" +#include "llvm/IR/Function.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/MathExtras.h" #include "llvm/Target/TargetInstrInfo.h" @@ -29,6 +30,8 @@ using namespace llvm; +#define DEBUG_TYPE "mips-long-branch" + STATISTIC(LongBranches, "Number of long branches."); static cl::opt SkipLongBranch( @@ -48,11 +51,11 @@ namespace { typedef MachineBasicBlock::reverse_iterator ReverseIter; struct MBBInfo { - uint64_t Size; + uint64_t Size, Address; bool HasLongBranch; MachineInstr *Br; - MBBInfo() : Size(0), HasLongBranch(false), Br(0) {} + MBBInfo() : Size(0), HasLongBranch(false), Br(nullptr) {} }; class MipsLongBranch : public MachineFunctionPass { @@ -61,13 +64,16 @@ namespace { static char ID; MipsLongBranch(TargetMachine &tm) : MachineFunctionPass(ID), TM(tm), - TII(static_cast(tm.getInstrInfo())) {} + IsPIC(TM.getRelocationModel() == Reloc::PIC_), + ABI(TM.getSubtarget().getTargetABI()), + LongBranchSeqSize(!IsPIC ? 2 : (ABI == MipsSubtarget::N64 ? 10 : + (!TM.getSubtarget().isTargetNaCl() ? 9 : 10))) {} - virtual const char *getPassName() const { + const char *getPassName() const override { return "Mips Long Branch"; } - bool runOnMachineFunction(MachineFunction &F); + bool runOnMachineFunction(MachineFunction &F) override; private: void splitMBB(MachineBasicBlock *MBB); @@ -78,9 +84,11 @@ namespace { void expandToLongBranch(MBBInfo &Info); const TargetMachine &TM; - const MipsInstrInfo *TII; MachineFunction *MF; SmallVector MBBInfos; + bool IsPIC; + unsigned ABI; + unsigned LongBranchSeqSize; }; char MipsLongBranch::ID = 0; @@ -103,7 +111,7 @@ static MachineBasicBlock *getTargetMBB(const MachineInstr &Br) { } assert(false && "This instruction does not have an MBB operand."); - return 0; + return nullptr; } // Traverse the list of instructions backwards until a non-debug instruction is @@ -126,7 +134,7 @@ void MipsLongBranch::splitMBB(MachineBasicBlock *MBB) { (!LastBr->isConditionalBranch() && !LastBr->isUnconditionalBranch())) return; - ReverseIter FirstBr = getNonDebugInstr(llvm::next(LastBr), End); + ReverseIter FirstBr = getNonDebugInstr(std::next(LastBr), End); // MBB has only one branch instruction if FirstBr is not a branch // instruction. @@ -146,7 +154,7 @@ void MipsLongBranch::splitMBB(MachineBasicBlock *MBB) { NewMBB->removeSuccessor(Tgt); MBB->addSuccessor(NewMBB); MBB->addSuccessor(Tgt); - MF->insert(llvm::next(MachineFunction::iterator(MBB)), NewMBB); + MF->insert(std::next(MachineFunction::iterator(MBB)), NewMBB); NewMBB->splice(NewMBB->end(), MBB, (++LastBr).base(), MBB->end()); } @@ -162,6 +170,8 @@ void MipsLongBranch::initMBBInfo() { MBBInfos.clear(); MBBInfos.resize(MF->size()); + const MipsInstrInfo *TII = + static_cast(TM.getSubtargetImpl()->getInstrInfo()); for (unsigned I = 0, E = MBBInfos.size(); I < E; ++I) { MachineBasicBlock *MBB = MF->getBlockNumbered(I); @@ -207,7 +217,9 @@ int64_t MipsLongBranch::computeOffset(const MachineInstr *Br) { // MachineBasicBlock operand MBBOpnd. void MipsLongBranch::replaceBranch(MachineBasicBlock &MBB, Iter Br, DebugLoc DL, MachineBasicBlock *MBBOpnd) { - unsigned NewOpc = TII->GetOppositeBranchOpc(Br->getOpcode()); + const MipsInstrInfo *TII = + static_cast(TM.getSubtargetImpl()->getInstrInfo()); + unsigned NewOpc = TII->getOppositeBranchOpc(Br->getOpcode()); const MCInstrDesc &NewDesc = TII->get(NewOpc); MachineInstrBuilder MIB = BuildMI(MBB, Br, DL, NewDesc); @@ -225,17 +237,16 @@ void MipsLongBranch::replaceBranch(MachineBasicBlock &MBB, Iter Br, MIB.addMBB(MBBOpnd); + // Bundle the instruction in the delay slot to the newly created branch + // and erase the original branch. + assert(Br->isBundledWithSucc()); + MachineBasicBlock::instr_iterator II(Br); + MIBundleBuilder(&*MIB).append((++II)->removeFromBundle()); Br->eraseFromParent(); } // Expand branch instructions to long branches. void MipsLongBranch::expandToLongBranch(MBBInfo &I) { - I.HasLongBranch = true; - - bool IsPIC = TM.getRelocationModel() == Reloc::PIC_; - unsigned ABI = TM.getSubtarget().getTargetABI(); - bool N64 = ABI == MipsSubtarget::N64; - MachineBasicBlock::iterator Pos; MachineBasicBlock *MBB = I.Br->getParent(), *TgtMBB = getTargetMBB(*I.Br); DebugLoc DL = I.Br->getDebugLoc(); @@ -243,106 +254,162 @@ void MipsLongBranch::expandToLongBranch(MBBInfo &I) { MachineFunction::iterator FallThroughMBB = ++MachineFunction::iterator(MBB); MachineBasicBlock *LongBrMBB = MF->CreateMachineBasicBlock(BB); + const MipsInstrInfo *TII = + static_cast(TM.getSubtargetImpl()->getInstrInfo()); + MF->insert(FallThroughMBB, LongBrMBB); MBB->removeSuccessor(TgtMBB); MBB->addSuccessor(LongBrMBB); if (IsPIC) { - // $longbr: - // addiu $sp, $sp, -regsize * 2 - // sw $ra, 0($sp) - // bal $baltgt - // sw $a3, regsize($sp) - // $baltgt: - // lui $a3, %hi($baltgt) - // lui $at, %hi($tgt) - // addiu $a3, $a3, %lo($baltgt) - // addiu $at, $at, %lo($tgt) - // subu $at, $at, $a3 - // addu $at, $ra, $at - // - // if n64: - // lui $a3, %highest($baltgt) - // lui $ra, %highest($tgt) - // addiu $a3, $a3, %higher($baltgt) - // addiu $ra, $ra, %higher($tgt) - // dsll $a3, $a3, 32 - // dsll $ra, $ra, 32 - // subu $at, $at, $a3 - // addu $at, $at, $ra - // - // lw $ra, 0($sp) - // lw $a3, regsize($sp) - // jr $at - // addiu $sp, $sp, regsize * 2 - // $fallthrough: - // - MF->getInfo()->setEmitNOAT(); MachineBasicBlock *BalTgtMBB = MF->CreateMachineBasicBlock(BB); MF->insert(FallThroughMBB, BalTgtMBB); LongBrMBB->addSuccessor(BalTgtMBB); BalTgtMBB->addSuccessor(TgtMBB); - int RegSize = N64 ? 8 : 4; - unsigned AT = N64 ? Mips::AT_64 : Mips::AT; - unsigned A3 = N64 ? Mips::A3_64 : Mips::A3; - unsigned SP = N64 ? Mips::SP_64 : Mips::SP; - unsigned RA = N64 ? Mips::RA_64 : Mips::RA; - unsigned Load = N64 ? Mips::LD_P8 : Mips::LW; - unsigned Store = N64 ? Mips::SD_P8 : Mips::SW; - unsigned LUi = N64 ? Mips::LUi64 : Mips::LUi; - unsigned ADDiu = N64 ? Mips::DADDiu : Mips::ADDiu; - unsigned ADDu = N64 ? Mips::DADDu : Mips::ADDu; - unsigned SUBu = N64 ? Mips::SUBu : Mips::SUBu; - unsigned JR = N64 ? Mips::JR64 : Mips::JR; - - Pos = LongBrMBB->begin(); - - BuildMI(*LongBrMBB, Pos, DL, TII->get(ADDiu), SP).addReg(SP) - .addImm(-RegSize * 2); - BuildMI(*LongBrMBB, Pos, DL, TII->get(Store)).addReg(RA).addReg(SP) - .addImm(0); - BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::BAL_BR)).addMBB(BalTgtMBB); - BuildMI(*LongBrMBB, Pos, DL, TII->get(Store)).addReg(A3).addReg(SP) - .addImm(RegSize)->setIsInsideBundle(); - - Pos = BalTgtMBB->begin(); - - BuildMI(*BalTgtMBB, Pos, DL, TII->get(LUi), A3) - .addMBB(BalTgtMBB, MipsII::MO_ABS_HI); - BuildMI(*BalTgtMBB, Pos, DL, TII->get(LUi), AT) - .addMBB(TgtMBB, MipsII::MO_ABS_HI); - BuildMI(*BalTgtMBB, Pos, DL, TII->get(ADDiu), A3).addReg(A3) - .addMBB(BalTgtMBB, MipsII::MO_ABS_LO); - BuildMI(*BalTgtMBB, Pos, DL, TII->get(ADDiu), AT).addReg(AT) - .addMBB(TgtMBB, MipsII::MO_ABS_LO); - BuildMI(*BalTgtMBB, Pos, DL, TII->get(SUBu), AT).addReg(AT).addReg(A3); - BuildMI(*BalTgtMBB, Pos, DL, TII->get(ADDu), AT).addReg(RA).addReg(AT); - - if (N64) { - BuildMI(*BalTgtMBB, Pos, DL, TII->get(LUi), A3) - .addMBB(BalTgtMBB, MipsII::MO_HIGHEST); - BuildMI(*BalTgtMBB, Pos, DL, TII->get(LUi), RA) - .addMBB(TgtMBB, MipsII::MO_HIGHEST); - BuildMI(*BalTgtMBB, Pos, DL, TII->get(ADDiu), A3).addReg(A3) - .addMBB(BalTgtMBB, MipsII::MO_HIGHER); - BuildMI(*BalTgtMBB, Pos, DL, TII->get(ADDiu), RA).addReg(RA) - .addMBB(TgtMBB, MipsII::MO_HIGHER); - BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DSLL), A3).addReg(A3) - .addImm(32); - BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DSLL), RA).addReg(RA) - .addImm(32); - BuildMI(*BalTgtMBB, Pos, DL, TII->get(SUBu), AT).addReg(AT).addReg(A3); - BuildMI(*BalTgtMBB, Pos, DL, TII->get(ADDu), AT).addReg(AT).addReg(RA); - I.Size += 4 * 8; + // We must select between the MIPS32r6/MIPS64r6 BAL (which is a normal + // instruction) and the pre-MIPS32r6/MIPS64r6 definition (which is an + // pseudo-instruction wrapping BGEZAL). + + const MipsSubtarget &Subtarget = TM.getSubtarget(); + unsigned BalOp = Subtarget.hasMips32r6() ? Mips::BAL : Mips::BAL_BR; + + if (ABI != MipsSubtarget::N64) { + // $longbr: + // addiu $sp, $sp, -8 + // sw $ra, 0($sp) + // lui $at, %hi($tgt - $baltgt) + // bal $baltgt + // addiu $at, $at, %lo($tgt - $baltgt) + // $baltgt: + // addu $at, $ra, $at + // lw $ra, 0($sp) + // jr $at + // addiu $sp, $sp, 8 + // $fallthrough: + // + + Pos = LongBrMBB->begin(); + + BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP) + .addReg(Mips::SP).addImm(-8); + BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SW)).addReg(Mips::RA) + .addReg(Mips::SP).addImm(0); + + // LUi and ADDiu instructions create 32-bit offset of the target basic + // block from the target of BAL instruction. We cannot use immediate + // value for this offset because it cannot be determined accurately when + // the program has inline assembly statements. We therefore use the + // relocation expressions %hi($tgt-$baltgt) and %lo($tgt-$baltgt) which + // are resolved during the fixup, so the values will always be correct. + // + // Since we cannot create %hi($tgt-$baltgt) and %lo($tgt-$baltgt) + // expressions at this point (it is possible only at the MC layer), + // we replace LUi and ADDiu with pseudo instructions + // LONG_BRANCH_LUi and LONG_BRANCH_ADDiu, and add both basic + // blocks as operands to these instructions. When lowering these pseudo + // instructions to LUi and ADDiu in the MC layer, we will create + // %hi($tgt-$baltgt) and %lo($tgt-$baltgt) expressions and add them as + // operands to lowered instructions. + + BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_LUi), Mips::AT) + .addMBB(TgtMBB).addMBB(BalTgtMBB); + MIBundleBuilder(*LongBrMBB, Pos) + .append(BuildMI(*MF, DL, TII->get(BalOp)).addMBB(BalTgtMBB)) + .append(BuildMI(*MF, DL, TII->get(Mips::LONG_BRANCH_ADDiu), Mips::AT) + .addReg(Mips::AT) + .addMBB(TgtMBB) + .addMBB(BalTgtMBB)); + + Pos = BalTgtMBB->begin(); + + BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDu), Mips::AT) + .addReg(Mips::RA).addReg(Mips::AT); + BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LW), Mips::RA) + .addReg(Mips::SP).addImm(0); + + if (!TM.getSubtarget().isTargetNaCl()) { + MIBundleBuilder(*BalTgtMBB, Pos) + .append(BuildMI(*MF, DL, TII->get(Mips::JR)).addReg(Mips::AT)) + .append(BuildMI(*MF, DL, TII->get(Mips::ADDiu), Mips::SP) + .addReg(Mips::SP).addImm(8)); + } else { + // In NaCl, modifying the sp is not allowed in branch delay slot. + BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP) + .addReg(Mips::SP).addImm(8); + + MIBundleBuilder(*BalTgtMBB, Pos) + .append(BuildMI(*MF, DL, TII->get(Mips::JR)).addReg(Mips::AT)) + .append(BuildMI(*MF, DL, TII->get(Mips::NOP))); + + // Bundle-align the target of indirect branch JR. + TgtMBB->setAlignment(MIPS_NACL_BUNDLE_ALIGN); + } + } else { + // $longbr: + // daddiu $sp, $sp, -16 + // sd $ra, 0($sp) + // daddiu $at, $zero, %hi($tgt - $baltgt) + // dsll $at, $at, 16 + // bal $baltgt + // daddiu $at, $at, %lo($tgt - $baltgt) + // $baltgt: + // daddu $at, $ra, $at + // ld $ra, 0($sp) + // jr64 $at + // daddiu $sp, $sp, 16 + // $fallthrough: + // + + // We assume the branch is within-function, and that offset is within + // +/- 2GB. High 32 bits will therefore always be zero. + + // Note that this will work even if the offset is negative, because + // of the +1 modification that's added in that case. For example, if the + // offset is -1MB (0xFFFFFFFFFFF00000), the computation for %higher is + // + // 0xFFFFFFFFFFF00000 + 0x80008000 = 0x000000007FF08000 + // + // and the bits [47:32] are zero. For %highest + // + // 0xFFFFFFFFFFF00000 + 0x800080008000 = 0x000080007FF08000 + // + // and the bits [63:48] are zero. + + Pos = LongBrMBB->begin(); + + BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::SP_64) + .addReg(Mips::SP_64).addImm(-16); + BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SD)).addReg(Mips::RA_64) + .addReg(Mips::SP_64).addImm(0); + BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LONG_BRANCH_DADDiu), + Mips::AT_64).addReg(Mips::ZERO_64) + .addMBB(TgtMBB, MipsII::MO_ABS_HI).addMBB(BalTgtMBB); + BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64) + .addReg(Mips::AT_64).addImm(16); + + MIBundleBuilder(*LongBrMBB, Pos) + .append(BuildMI(*MF, DL, TII->get(BalOp)).addMBB(BalTgtMBB)) + .append( + BuildMI(*MF, DL, TII->get(Mips::LONG_BRANCH_DADDiu), Mips::AT_64) + .addReg(Mips::AT_64) + .addMBB(TgtMBB, MipsII::MO_ABS_LO) + .addMBB(BalTgtMBB)); + + Pos = BalTgtMBB->begin(); + + BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDu), Mips::AT_64) + .addReg(Mips::RA_64).addReg(Mips::AT_64); + BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::LD), Mips::RA_64) + .addReg(Mips::SP_64).addImm(0); + + MIBundleBuilder(*BalTgtMBB, Pos) + .append(BuildMI(*MF, DL, TII->get(Mips::JR64)).addReg(Mips::AT_64)) + .append(BuildMI(*MF, DL, TII->get(Mips::DADDiu), Mips::SP_64) + .addReg(Mips::SP_64).addImm(16)); } - BuildMI(*BalTgtMBB, Pos, DL, TII->get(Load), RA).addReg(SP).addImm(0); - BuildMI(*BalTgtMBB, Pos, DL, TII->get(Load), A3).addReg(SP).addImm(RegSize); - BuildMI(*BalTgtMBB, Pos, DL, TII->get(JR)).addReg(AT); - BuildMI(*BalTgtMBB, Pos, DL, TII->get(ADDiu), SP).addReg(SP) - .addImm(RegSize * 2)->setIsInsideBundle(); - I.Size += 4 * 14; + assert(LongBrMBB->size() + BalTgtMBB->size() == LongBranchSeqSize); } else { // $longbr: // j $tgt @@ -351,9 +418,11 @@ void MipsLongBranch::expandToLongBranch(MBBInfo &I) { // Pos = LongBrMBB->begin(); LongBrMBB->addSuccessor(TgtMBB); - BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::J)).addMBB(TgtMBB); - BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::NOP))->setIsInsideBundle(); - I.Size += 4 * 2; + MIBundleBuilder(*LongBrMBB, Pos) + .append(BuildMI(*MF, DL, TII->get(Mips::J)).addMBB(TgtMBB)) + .append(BuildMI(*MF, DL, TII->get(Mips::NOP))); + + assert(LongBrMBB->size() == LongBranchSeqSize); } if (I.Br->isUnconditionalBranch()) { @@ -378,6 +447,12 @@ static void emitGPDisp(MachineFunction &F, const MipsInstrInfo *TII) { } bool MipsLongBranch::runOnMachineFunction(MachineFunction &F) { + const MipsInstrInfo *TII = + static_cast(TM.getSubtargetImpl()->getInstrInfo()); + + const MipsSubtarget &STI = TM.getSubtarget(); + if (STI.inMips16Mode() || !STI.enableLongBranchPass()) + return false; if ((TM.getRelocationModel() == Reloc::PIC_) && TM.getSubtarget().isABI_O32() && F.getInfo()->globalBaseRegSet()) @@ -389,7 +464,7 @@ bool MipsLongBranch::runOnMachineFunction(MachineFunction &F) { MF = &F; initMBBInfo(); - SmallVector::iterator I, E = MBBInfos.end(); + SmallVectorImpl::iterator I, E = MBBInfos.end(); bool EverMadeChange = false, MadeChange = true; while (MadeChange) { @@ -401,19 +476,45 @@ bool MipsLongBranch::runOnMachineFunction(MachineFunction &F) { if (!I->Br || I->HasLongBranch) continue; - if (!ForceLongBranch) - // Check if offset fits into 16-bit immediate field of branches. - if (isInt<16>(computeOffset(I->Br) / 4)) - continue; + int ShVal = TM.getSubtarget().inMicroMipsMode() ? 2 : 4; + int64_t Offset = computeOffset(I->Br) / ShVal; - expandToLongBranch(*I); + if (TM.getSubtarget().isTargetNaCl()) { + // The offset calculation does not include sandboxing instructions + // that will be added later in the MC layer. Since at this point we + // don't know the exact amount of code that "sandboxing" will add, we + // conservatively estimate that code will not grow more than 100%. + Offset *= 2; + } + + // Check if offset fits into 16-bit immediate field of branches. + if (!ForceLongBranch && isInt<16>(Offset)) + continue; + + I->HasLongBranch = true; + I->Size += LongBranchSeqSize * 4; ++LongBranches; EverMadeChange = MadeChange = true; } } - if (EverMadeChange) - MF->RenumberBlocks(); + if (!EverMadeChange) + return true; + + // Compute basic block addresses. + if (TM.getRelocationModel() == Reloc::PIC_) { + uint64_t Address = 0; + + for (I = MBBInfos.begin(); I != E; Address += I->Size, ++I) + I->Address = Address; + } + + // Do the expansion. + for (I = MBBInfos.begin(); I != E; ++I) + if (I->HasLongBranch) + expandToLongBranch(*I); + + MF->RenumberBlocks(); return true; }