X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTarget%2FMips%2FMipsLongBranch.cpp;h=71a6f4d4a11e074c9bccfaacd59764d44ddf169d;hb=d5dd8ce2a5336df4e4b4cc04d23e4018d93944f9;hp=b9dbd522b70ebdcf1de1d417fbba35d6b979376f;hpb=4fb08317af55c97f421047f0bdbfdd320ac76936;p=oota-llvm.git diff --git a/lib/Target/Mips/MipsLongBranch.cpp b/lib/Target/Mips/MipsLongBranch.cpp index b9dbd522b70..71a6f4d4a11 100644 --- a/lib/Target/Mips/MipsLongBranch.cpp +++ b/lib/Target/Mips/MipsLongBranch.cpp @@ -10,21 +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: -// 1. Fix pc-region jump instructions which cross 256MB segment boundaries. -// 2. If program has inline assembly statements whose size cannot be -// determined accurately, load branch target addresses from the GOT. +// 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" @@ -33,6 +30,8 @@ using namespace llvm; +#define DEBUG_TYPE "mips-long-branch" + STATISTIC(LongBranches, "Number of long branches."); static cl::opt SkipLongBranch( @@ -56,7 +55,7 @@ namespace { bool HasLongBranch; MachineInstr *Br; - MBBInfo() : Size(0), HasLongBranch(false), Br(0) {} + MBBInfo() : Size(0), HasLongBranch(false), Br(nullptr) {} }; class MipsLongBranch : public MachineFunctionPass { @@ -65,16 +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 ? 13 : 9)) {} + 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); @@ -85,7 +84,6 @@ namespace { void expandToLongBranch(MBBInfo &Info); const TargetMachine &TM; - const MipsInstrInfo *TII; MachineFunction *MF; SmallVector MBBInfos; bool IsPIC; @@ -113,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 @@ -136,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. @@ -156,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()); } @@ -172,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); @@ -217,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); @@ -235,6 +237,11 @@ 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(); } @@ -247,6 +254,9 @@ 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); @@ -257,19 +267,21 @@ void MipsLongBranch::expandToLongBranch(MBBInfo &I) { LongBrMBB->addSuccessor(BalTgtMBB); BalTgtMBB->addSuccessor(TgtMBB); - int64_t TgtAddress = MBBInfos[TgtMBB->getNumber()].Address; - int64_t Offset = TgtAddress - (I.Address + I.Size - 20); - int64_t Lo = SignExtend64<16>(Offset & 0xffff); - int64_t Hi = SignExtend64<16>(((Offset + 0x8000) >> 16) & 0xffff); + // 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) - // bal $baltgt // lui $at, %hi($tgt - $baltgt) - // $baltgt: + // bal $baltgt // addiu $at, $at, %lo($tgt - $baltgt) + // $baltgt: // addu $at, $ra, $at // lw $ra, 0($sp) // jr $at @@ -283,33 +295,65 @@ void MipsLongBranch::expandToLongBranch(MBBInfo &I) { .addReg(Mips::SP).addImm(-8); BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::SW)).addReg(Mips::RA) .addReg(Mips::SP).addImm(0); - BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::BAL_BR)).addMBB(BalTgtMBB); - BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::LUi), Mips::AT).addImm(Hi) - ->setIsInsideBundle(); + + // 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::ADDiu), Mips::AT) - .addReg(Mips::AT).addImm(Lo); 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); - BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::JR)).addReg(Mips::AT); - BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::ADDiu), Mips::SP) - .addReg(Mips::SP).addImm(8)->setIsInsideBundle(); + + 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) - // lui64 $at, %highest($tgt - $baltgt) - // daddiu $at, $at, %higher($tgt - $baltgt) + // daddiu $at, $zero, %hi($tgt - $baltgt) // dsll $at, $at, 16 - // daddiu $at, $at, %hi($tgt - $baltgt) // bal $baltgt - // dsll $at, $at, 16 - // $baltgt: // daddiu $at, $at, %lo($tgt - $baltgt) + // $baltgt: // daddu $at, $ra, $at // ld $ra, 0($sp) // jr64 $at @@ -317,9 +361,20 @@ void MipsLongBranch::expandToLongBranch(MBBInfo &I) { // $fallthrough: // - int64_t Higher = SignExtend64<16>(((Offset + 0x80008000) >> 32) & 0xffff); - int64_t Highest = - SignExtend64<16>(((Offset + 0x800080008000LL) >> 48) & 0xffff); + // 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(); @@ -327,30 +382,34 @@ void MipsLongBranch::expandToLongBranch(MBBInfo &I) { .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::LUi64), Mips::AT_64) - .addImm(Highest); - BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::AT_64) - .addReg(Mips::AT_64).addImm(Higher); + 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); - BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::AT_64) - .addReg(Mips::AT_64).addImm(Hi); - BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::BAL_BR)).addMBB(BalTgtMBB); - BuildMI(*LongBrMBB, Pos, DL, TII->get(Mips::DSLL), Mips::AT_64) - .addReg(Mips::AT_64).addImm(16)->setIsInsideBundle(); + + 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::DADDiu), Mips::AT_64) - .addReg(Mips::AT_64).addImm(Lo); 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); - BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::JR64)).addReg(Mips::AT_64); - BuildMI(*BalTgtMBB, Pos, DL, TII->get(Mips::DADDiu), Mips::SP_64) - .addReg(Mips::SP_64).addImm(16)->setIsInsideBundle(); + + 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)); } + + assert(LongBrMBB->size() + BalTgtMBB->size() == LongBranchSeqSize); } else { // $longbr: // j $tgt @@ -359,8 +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(); + 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()) { @@ -385,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()) @@ -396,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) { @@ -408,8 +476,19 @@ bool MipsLongBranch::runOnMachineFunction(MachineFunction &F) { if (!I->Br || I->HasLongBranch) continue; + int ShVal = TM.getSubtarget().inMicroMipsMode() ? 2 : 4; + int64_t Offset = computeOffset(I->Br) / ShVal; + + 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>(computeOffset(I->Br) / 4)) + if (!ForceLongBranch && isInt<16>(Offset)) continue; I->HasLongBranch = true; @@ -424,8 +503,6 @@ bool MipsLongBranch::runOnMachineFunction(MachineFunction &F) { // Compute basic block addresses. if (TM.getRelocationModel() == Reloc::PIC_) { - MF->getInfo()->setEmitNOAT(); - uint64_t Address = 0; for (I = MBBInfos.begin(); I != E; Address += I->Size, ++I)