106 using namespace llvm;
108 #define DEBUG_TYPE "mips-branch-expansion" 110 STATISTIC(NumInsertedNops,
"Number of nops inserted");
111 STATISTIC(LongBranches,
"Number of long branches.");
119 cl::desc(
"MIPS: Expand all branches to long format."),
129 bool HasLongBranch =
false;
144 return "Mips Branch Expansion Pass";
158 uint64_t computeOffsetFromTheBeginning(
int MBB);
163 void expandToLongBranch(MBBInfo &
Info);
164 bool handleForbiddenSlot();
165 bool handlePossibleLongBranch();
174 bool ForceLongBranchFirstPass =
false;
182 "Expand out of range branch instructions and fix forbidden" 188 return new MipsBranchExpansion();
194 Iter
I =
Position,
E = Position->getParent()->end();
196 [](
const Iter &Insn) {
return Insn->isTransient(); });
205 if (Position == Parent->
end()) {
208 if (Succ !=
nullptr && Parent->
isSuccessor(Succ)) {
209 Position = Succ->
begin();
212 return std::make_pair(Position,
true);
214 }
while (Parent->
empty());
218 if (Instr == Parent->
end()) {
221 return std::make_pair(Instr,
false);
241 if (!B->isDebugInstr())
249 ReverseIter End = MBB->
rend();
253 if ((LastBr == End) ||
254 (!LastBr->isConditionalBranch() && !LastBr->isUnconditionalBranch()))
261 if ((FirstBr == End) ||
262 (!FirstBr->isConditionalBranch() && !FirstBr->isUnconditionalBranch()))
265 assert(!FirstBr->isIndirectBranch() &&
"Unexpected indirect branch found.");
273 NewMBB->transferSuccessors(MBB);
275 NewMBB->removeSuccessor(Tgt,
true);
280 NewMBB->splice(NewMBB->end(), MBB, LastBr.getReverse(), MBB->
end());
284 void MipsBranchExpansion::initMBBInfo() {
287 for (
auto &MBB : *MFp)
290 MFp->RenumberBlocks();
292 MBBInfos.resize(MFp->size());
294 for (
unsigned I = 0,
E = MBBInfos.size();
I <
E; ++
I) {
300 MBBInfos[
I].
Size +=
TII->getInstSizeInBytes(*
MI);
305 int64_t MipsBranchExpansion::computeOffset(
const MachineInstr *Br) {
311 if (ThisMBB < TargetMBB) {
312 for (
int N = ThisMBB + 1;
N < TargetMBB; ++
N)
313 Offset += MBBInfos[
N].
Size;
319 for (
int N = ThisMBB;
N >= TargetMBB; --
N)
320 Offset += MBBInfos[
N].
Size;
326 uint64_t MipsBranchExpansion::computeOffsetFromTheBeginning(
int MBB) {
328 for (
int N = 0;
N < MBB; ++
N)
329 Offset += MBBInfos[
N].
Size;
338 unsigned NewOpc =
TII->getOppositeBranchOpc(Br->getOpcode());
343 for (
unsigned I = 0,
E = Br->getDesc().getNumOperands();
I <
E; ++
I) {
356 if (Br->hasDelaySlot()) {
359 assert(Br->isBundledWithSucc());
363 Br->eraseFromParent();
369 bool HasR6 = ABI.IsN64() ? STI->hasMips64r6() : STI->hasMips32r6();
370 bool AddImm = HasR6 && !STI->useIndirectJumpsHazard();
372 unsigned JR = ABI.IsN64() ? Mips::JR64 : Mips::JR;
373 unsigned JIC = ABI.IsN64() ? Mips::JIC64 : Mips::JIC;
374 unsigned JR_HB = ABI.IsN64() ? Mips::JR_HB64 : Mips::JR_HB;
375 unsigned JR_HB_R6 = ABI.IsN64() ? Mips::JR_HB64_R6 : Mips::JR_HB_R6;
378 if (STI->useIndirectJumpsHazard())
379 JumpOp = HasR6 ? JR_HB_R6 : JR_HB;
381 JumpOp = HasR6 ? JIC : JR;
383 if (JumpOp == Mips::JIC && STI->inMicroMipsMode())
384 JumpOp = Mips::JIC_MMR6;
386 unsigned ATReg = ABI.IsN64() ? Mips::AT_64 : Mips::AT;
388 BuildMI(*MBB, Pos, DL,
TII->get(JumpOp)).addReg(ATReg);
400 void MipsBranchExpansion::expandToLongBranch(MBBInfo &
I) {
408 MFp->
insert(FallThroughMBB, LongBrMBB);
413 MFp->
insert(FallThroughMBB, BalTgtMBB);
420 const unsigned BalOp =
422 ? STI->inMicroMipsMode() ? Mips::BALC_MMR6 : Mips::BALC
423 : STI->inMicroMipsMode() ? Mips::BAL_BR_MM : Mips::BAL_BR;
455 Pos = LongBrMBB->
begin();
457 BuildMI(*LongBrMBB, Pos, DL,
TII->get(Mips::ADDiu), Mips::SP)
460 BuildMI(*LongBrMBB, Pos, DL,
TII->get(Mips::SW))
481 BuildMI(*LongBrMBB, Pos, DL,
TII->get(Mips::LONG_BRANCH_LUi), Mips::AT)
486 BuildMI(*MFp, DL,
TII->get(BalOp)).addMBB(BalTgtMBB);
488 BuildMI(*MFp, DL,
TII->get(Mips::LONG_BRANCH_ADDiu), Mips::AT)
492 if (STI->hasMips32r6()) {
493 LongBrMBB->
insert(Pos, ADDiuInstr);
494 LongBrMBB->
insert(Pos, BalInstr);
496 LongBrMBB->
insert(Pos, BalInstr);
497 LongBrMBB->
insert(Pos, ADDiuInstr);
498 LongBrMBB->
rbegin()->bundleWithPred();
501 Pos = BalTgtMBB->
begin();
503 BuildMI(*BalTgtMBB, Pos, DL,
TII->get(Mips::ADDu), Mips::AT)
509 if (STI->isTargetNaCl())
515 bool hasDelaySlot = buildProperJumpMI(BalTgtMBB, Pos, DL);
517 if (STI->isTargetNaCl() || !hasDelaySlot) {
518 BuildMI(*BalTgtMBB, std::prev(Pos), DL,
TII->get(Mips::ADDiu), Mips::SP)
523 if (STI->isTargetNaCl()) {
524 BuildMI(*BalTgtMBB, Pos, DL,
TII->get(Mips::NOP));
526 BuildMI(*BalTgtMBB, Pos, DL,
TII->get(Mips::ADDiu), Mips::SP)
530 BalTgtMBB->
rbegin()->bundleWithPred();
578 Pos = LongBrMBB->
begin();
580 BuildMI(*LongBrMBB, Pos, DL,
TII->get(Mips::DADDiu), Mips::SP_64)
583 BuildMI(*LongBrMBB, Pos, DL,
TII->get(Mips::SD))
587 BuildMI(*LongBrMBB, Pos, DL,
TII->get(Mips::LONG_BRANCH_DADDiu),
589 .addReg(Mips::ZERO_64)
592 BuildMI(*LongBrMBB, Pos, DL,
TII->get(Mips::DSLL), Mips::AT_64)
597 BuildMI(*MFp, DL,
TII->get(BalOp)).addMBB(BalTgtMBB);
599 BuildMI(*MFp, DL,
TII->get(Mips::LONG_BRANCH_DADDiu), Mips::AT_64)
603 if (STI->hasMips32r6()) {
604 LongBrMBB->
insert(Pos, DADDiuInstr);
605 LongBrMBB->
insert(Pos, BalInstr);
607 LongBrMBB->
insert(Pos, BalInstr);
608 LongBrMBB->
insert(Pos, DADDiuInstr);
609 LongBrMBB->
rbegin()->bundleWithPred();
612 Pos = BalTgtMBB->
begin();
614 BuildMI(*BalTgtMBB, Pos, DL,
TII->get(Mips::DADDu), Mips::AT_64)
621 bool hasDelaySlot = buildProperJumpMI(BalTgtMBB, Pos, DL);
624 BuildMI(*BalTgtMBB, std::prev(Pos), DL,
TII->get(Mips::DADDiu),
629 BuildMI(*BalTgtMBB, Pos, DL,
TII->get(Mips::DADDiu), Mips::SP_64)
632 BalTgtMBB->
rbegin()->bundleWithPred();
636 Pos = LongBrMBB->
begin();
641 uint64_t JOffset = computeOffsetFromTheBeginning(MBB->
getNumber()) +
643 uint64_t TgtMBBOffset = computeOffsetFromTheBeginning(TgtMBB->getNumber());
646 if (JOffset < TgtMBBOffset)
647 TgtMBBOffset += 2 * 4;
649 bool SameSegmentJump = JOffset >> 28 == TgtMBBOffset >> 28;
651 if (STI->hasMips32r6() &&
TII->isBranchOffsetInRange(Mips::BC, I.Offset)) {
658 TII->get(STI->inMicroMipsMode() ? Mips::BC_MMR6 : Mips::BC))
660 }
else if (SameSegmentJump) {
677 BuildMI(*LongBrMBB, Pos, DL,
TII->get(Mips::LONG_BRANCH_LUi2Op_64),
680 BuildMI(*LongBrMBB, Pos, DL,
TII->get(Mips::LONG_BRANCH_DADDiu2Op),
684 BuildMI(*LongBrMBB, Pos, DL,
TII->get(Mips::DSLL), Mips::AT_64)
687 BuildMI(*LongBrMBB, Pos, DL,
TII->get(Mips::LONG_BRANCH_DADDiu2Op),
691 BuildMI(*LongBrMBB, Pos, DL,
TII->get(Mips::DSLL), Mips::AT_64)
694 BuildMI(*LongBrMBB, Pos, DL,
TII->get(Mips::LONG_BRANCH_DADDiu2Op),
699 BuildMI(*LongBrMBB, Pos, DL,
TII->get(Mips::LONG_BRANCH_LUi2Op),
702 BuildMI(*LongBrMBB, Pos, DL,
TII->get(Mips::LONG_BRANCH_ADDiu2Op),
707 buildProperJumpMI(LongBrMBB, Pos, DL);
711 if (I.Br->isUnconditionalBranch()) {
713 assert(I.Br->getDesc().getNumOperands() == 1);
714 I.Br->RemoveOperand(0);
718 replaceBranch(*MBB, I.Br, DL, &*FallThroughMBB);
725 BuildMI(MBB, I, DL, TII->get(Mips::LUi), Mips::V0)
727 BuildMI(MBB, I, DL, TII->get(Mips::ADDiu), Mips::V0)
733 bool MipsBranchExpansion::handleForbiddenSlot() {
735 if (!STI->hasMips32r6() || STI->inMicroMipsMode())
738 bool Changed =
false;
741 for (Iter I = FI->begin(); I != FI->end(); ++
I) {
744 if (!
TII->HasForbiddenSlot(*I))
748 bool LastInstInFunction =
749 std::next(I) == FI->end() && std::next(FI) == MFp->end();
750 if (!LastInstInFunction) {
752 LastInstInFunction |= Res.second;
756 if (LastInstInFunction || !
TII->SafeInForbiddenSlot(*Inst)) {
759 if (std::next(Iit) == FI->end() ||
760 std::next(Iit)->getOpcode() != Mips::NOP) {
763 BuildMI(*MFp, I->getDebugLoc(),
TII->get(Mips::NOP)));
773 bool MipsBranchExpansion::handlePossibleLongBranch() {
774 if (STI->inMips16Mode() || !STI->enableLongBranchPass())
780 bool EverMadeChange =
false, MadeChange =
true;
787 for (
unsigned I = 0,
E = MBBInfos.size(); I <
E; ++
I) {
790 ReverseIter End = MBB->
rend();
793 if ((Br != End) && Br->isBranch() && !Br->isIndirectBranch() &&
794 (Br->isConditionalBranch() ||
795 (Br->isUnconditionalBranch() && IsPIC))) {
796 int64_t
Offset = computeOffset(&*Br);
798 if (STI->isTargetNaCl()) {
806 if (ForceLongBranchFirstPass ||
807 !
TII->isBranchOffsetInRange(Br->getOpcode(),
Offset)) {
809 MBBInfos[
I].Br = &*Br;
814 ForceLongBranchFirstPass =
false;
818 for (I = MBBInfos.
begin(); I !=
E; ++
I) {
824 expandToLongBranch(*I);
826 EverMadeChange = MadeChange =
true;
829 MFp->RenumberBlocks();
832 return EverMadeChange;
842 if (IsPIC && ABI.IsO32() &&
850 bool longBranchChanged = handlePossibleLongBranch();
851 bool forbiddenSlotChanged = handleForbiddenSlot();
853 bool Changed = longBranchChanged || forbiddenSlotChanged;
856 while (forbiddenSlotChanged) {
857 longBranchChanged = handlePossibleLongBranch();
858 if (!longBranchChanged)
860 forbiddenSlotChanged = handleForbiddenSlot();
void initializeMipsBranchExpansionPass(PassRegistry &)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
instr_iterator instr_begin()
instr_iterator instr_end()
MachineBasicBlock * getMBB() const
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
This class represents lattice values for constants.
static MachineBasicBlock * getTargetMBB(const MachineInstr &Br)
Iterate over list of Br's operands and search for a MachineBasicBlock operand.
MO_HIGHER/HIGHEST - Represents the highest or higher half word of a 64-bit symbol address...
FunctionPass * createMipsBranchExpansion()
Describe properties that are true of each instruction in the target description file.
unsigned getReg() const
getReg - Returns the register number.
static ReverseIter getNonDebugInstr(ReverseIter B, const ReverseIter &E)
static Iter getNextMachineInstrInBB(Iter Position)
STATISTIC(NumFunctions, "Total number of functions")
void removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll())
Remove the specified register from the live in set.
SI optimize exec mask operations pre RA
void append(SmallVectorImpl< char > &path, const Twine &a, const Twine &b="", const Twine &c="", const Twine &d="")
Append to path.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
const HexagonInstrInfo * TII
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Position
Position to insert a new instruction relative to an existing instruction.
MO_ABS_HI/LO - Represents the hi or low part of an absolute symbol address.
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
MachineInstrBundleIterator< MachineInstr, true > reverse_iterator
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
reverse_iterator rbegin()
Analysis containing CSE Info
BasicBlockListType::iterator iterator
static cl::opt< bool > ForceLongBranch("force-mips-long-branch", cl::init(false), cl::desc("MIPS: Expand all branches to long format."), cl::Hidden)
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
initializer< Ty > init(const Ty &Val)
MachineInstrBundleIterator< MachineInstr > iterator
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
LLVM Basic Block Representation.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
DebugLoc findDebugLoc(instr_iterator MBBI)
Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE and DBG_LABEL instructions...
Ty * getInfo()
getInfo - Keep track of various per-function pieces of information for backends that would like to do...
FunctionPass class - This class is used to implement most global optimizations.
auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
const MachineBasicBlock & front() const
static cl::opt< bool > SkipLongBranch("skip-mips-long-branch", cl::init(false), cl::desc("MIPS: Skip branch expansion pass."), cl::Hidden)
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Iterator for intrusive lists based on ilist_node.
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
MachineOperand class - Representation of each machine instruction operand.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
static std::pair< Iter, bool > getNextMachineInstr(Iter Position, MachineBasicBlock *Parent)
void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New)
Replace successor OLD with NEW and update probability info.
const MachineBasicBlock * getParent() const
MachineFunctionProperties & set(Property P)
static const unsigned MIPS_NACL_BUNDLE_ALIGN
Representation of each machine instruction.
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
static MachineOperand CreateMBB(MachineBasicBlock *MBB, unsigned char TargetFlags=0)
bool isPositionIndependent() const
const MachineInstrBuilder & addExternalSymbol(const char *FnName, unsigned char TargetFlags=0) const
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
MipsFunctionInfo - This class is derived from MachineFunction private Mips target-specific informatio...
INITIALIZE_PASS(MipsBranchExpansion, DEBUG_TYPE, "Expand out of range branch instructions and fix forbidden" " slot hazards", false, false) FunctionPass *llvm
Returns a pass that clears pipeline hazards.
const MachineInstrBuilder & addReg(unsigned RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
const LLVMTargetMachine & getTarget() const
getTarget - Return the target machine this machine code is compiled with
bool isReg() const
isReg - Tests if this is a MO_Register operand.
MIBundleBuilder & append(MachineInstr *MI)
Insert MI into MBB by appending it to the instructions in the bundle.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Primary interface to the complete machine description for the target machine.
StringRef - Represent a constant reference to a string, i.e.
bool isMBB() const
isMBB - Tests if this is a MO_MachineBasicBlock operand.
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned char TargetFlags=0) const
const MachineOperand & getOperand(unsigned i) const
static void emitGPDisp(MachineFunction &F, const MipsInstrInfo *TII)
static bool splitMBB(BlockSplitInfo &BSI)
Splits a MachineBasicBlock to branch before SplitBefore.
Properties which a MachineFunction may have at a given point in time.
Helper class for constructing bundles of MachineInstrs.