MipsBranchExpansion.cpp | Explore in Territory

//===----------------------- MipsBranchExpansion.cpp ----------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
/// \file
///
/// This pass do two things:
/// - it expands a branch or jump instruction into a long branch if its offset
///   is too large to fit into its immediate field,
/// - it inserts nops to prevent forbidden slot hazards.
///
/// The reason why this pass combines these two tasks is that one of these two
/// tasks can break the result of the previous one.
///
/// Example of that is a situation where at first, no branch should be expanded,
/// but after adding at least one nop somewhere in the code to prevent a
/// forbidden slot hazard, offset of some branches may go out of range. In that
/// case it is necessary to check again if there is some branch that needs
/// expansion. On the other hand, expanding some branch may cause a control
/// transfer instruction to appear in the forbidden slot, which is a hazard that
/// should be fixed. This pass alternates between this two tasks untill no
/// changes are made. Only then we can be sure that all branches are expanded
/// properly, and no hazard situations exist.
///
/// Regarding branch expanding:
///
/// When branch instruction like beqzc or bnezc has offset that is too large
/// to fit into its immediate field, it has to be expanded to another
/// instruction or series of instructions.
///
/// FIXME: Fix pc-region jump instructions which cross 256MB segment boundaries.
/// TODO: Handle out of range bc, b (pseudo) instructions.
///
/// Regarding compact branch hazard prevention:
///
/// Hazards handled: forbidden slots for MIPSR6, FPU slots for MIPS3 and below,
/// load delay slots for MIPS1.
///
/// A forbidden slot hazard occurs when a compact branch instruction is executed
/// and the adjacent instruction in memory is a control transfer instruction
/// such as a branch or jump, ERET, ERETNC, DERET, WAIT and PAUSE.
///
/// For example:
///
/// 0x8004      bnec    a1,v0,<P+0x18>
/// 0x8008      beqc    a1,a2,<P+0x54>
///
/// In such cases, the processor is required to signal a Reserved Instruction
/// exception.
///
/// Here, if the instruction at 0x8004 is executed, the processor will raise an
/// exception as there is a control transfer instruction at 0x8008.
///
/// There are two sources of forbidden slot hazards:
///
/// A) A previous pass has created a compact branch directly.
/// B) Transforming a delay slot branch into compact branch. This case can be
///    difficult to process as lookahead for hazards is insufficient, as
///    backwards delay slot fillling can also produce hazards in previously
///    processed instuctions.
///
/// In future this pass can be extended (or new pass can be created) to handle
/// other pipeline hazards, such as various MIPS1 hazards, processor errata that
/// require instruction reorganization, etc.
///
/// This pass has to run after the delay slot filler as that pass can introduce
/// pipeline hazards such as compact branch hazard, hence the existing hazard
/// recognizer is not suitable.
///
//===----------------------------------------------------------------------===//

#include "MCTargetDesc/MipsABIInfo.h"
#include "MCTargetDesc/MipsBaseInfo.h"
#include "MCTargetDesc/MipsMCNaCl.h"
#include "MCTargetDesc/MipsMCTargetDesc.h"
#include "Mips.h"
#include "MipsInstrInfo.h"
#include "MipsMachineFunction.h"
#include "MipsSubtarget.h"
#include "MipsTargetMachine.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Target/TargetMachine.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <utility>

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumInsertedNops, "Number of nops inserted");
STATISTIC(LongBranches, "Number of long branches.");

static cl::opt<bool>
    SkipLongBranch("skip-mips-long-branch", cl::init(false),
                   cl::desc("MIPS: Skip branch expansion pass."), cl::Hidden);

static cl::opt<bool>
    ForceLongBranch("force-mips-long-branch", cl::init(false),
                    cl::desc("MIPS: Expand all branches to long format."),
                    cl::Hidden);

namespace {

Iter;
ReverseIter;

struct MBBInfo { … };

class MipsBranchExpansion : public MachineFunctionPass { … };

} // end of anonymous namespace

char MipsBranchExpansion::ID = …;

INITIALIZE_PASS(…)

/// Returns a pass that clears pipeline hazards.
FunctionPass *llvm::createMipsBranchExpansion() { … }

// Find the next real instruction from the current position in current basic
// block.
static Iter getNextMachineInstrInBB(Iter Position) { … }

// Find the next real instruction from the current position, looking through
// basic block boundaries.
static std::pair<Iter, bool> getNextMachineInstr(Iter Position,
                                                 MachineBasicBlock *Parent) { … }

/// Iterate over list of Br's operands and search for a MachineBasicBlock
/// operand.
static MachineBasicBlock *getTargetMBB(const MachineInstr &Br) { … }

// Traverse the list of instructions backwards until a non-debug instruction is
// found or it reaches E.
static ReverseIter getNonDebugInstr(ReverseIter B, const ReverseIter &E) { … }

// Split MBB if it has two direct jumps/branches.
void MipsBranchExpansion::splitMBB(MachineBasicBlock *MBB) { … }

// Fill MBBInfos.
void MipsBranchExpansion::initMBBInfo() { … }

// Compute offset of branch in number of bytes.
int64_t MipsBranchExpansion::computeOffset(const MachineInstr *Br) { … }

// Returns the distance in bytes up until MBB
uint64_t MipsBranchExpansion::computeOffsetFromTheBeginning(int MBB) { … }

// Replace Br with a branch which has the opposite condition code and a
// MachineBasicBlock operand MBBOpnd.
void MipsBranchExpansion::replaceBranch(MachineBasicBlock &MBB, Iter Br,
                                        const DebugLoc &DL,
                                        MachineBasicBlock *MBBOpnd) { … }

bool MipsBranchExpansion::buildProperJumpMI(MachineBasicBlock *MBB,
                                            MachineBasicBlock::iterator Pos,
                                            DebugLoc DL) { … }

// Expand branch instructions to long branches.
// TODO: This function has to be fixed for beqz16 and bnez16, because it
// currently assumes that all branches have 16-bit offsets, and will produce
// wrong code if branches whose allowed offsets are [-128, -126, ..., 126]
// are present.
void MipsBranchExpansion::expandToLongBranch(MBBInfo &I) { … }

static void emitGPDisp(MachineFunction &F, const MipsInstrInfo *TII) { … }

template <typename Pred, typename Safe>
bool MipsBranchExpansion::handleMFLOSlot(Pred Predicate, Safe SafeInSlot) { … }

template <typename Pred, typename Safe>
bool MipsBranchExpansion::handleSlot(Pred Predicate, Safe SafeInSlot) { … }

bool MipsBranchExpansion::handleMFLO() { … }

bool MipsBranchExpansion::handleForbiddenSlot() { … }

bool MipsBranchExpansion::handleFPUDelaySlot() { … }

bool MipsBranchExpansion::handleLoadDelaySlot() { … }

bool MipsBranchExpansion::handlePossibleLongBranch() { … }

bool MipsBranchExpansion::runOnMachineFunction(MachineFunction &MF) { … }
llvm/llvm/lib/Target/Mips/MipsBranchExpansion.cpp
