MipsDelaySlotFiller.cpp | Explore in Territory

//===- MipsDelaySlotFiller.cpp - Mips Delay Slot Filler -------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// Simple pass to fill delay slots with useful instructions.
//
//===----------------------------------------------------------------------===//

#include "MCTargetDesc/MipsMCNaCl.h"
#include "Mips.h"
#include "MipsInstrInfo.h"
#include "MipsRegisterInfo.h"
#include "MipsSubtarget.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PointerUnion.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/PseudoSourceValue.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/MC/MCInstrDesc.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CodeGen.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Target/TargetMachine.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <memory>
#include <utility>

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(FilledSlots, "Number of delay slots filled");
STATISTIC(UsefulSlots, "Number of delay slots filled with instructions that"
                       " are not NOP.");

static cl::opt<bool> DisableDelaySlotFiller(
  "disable-mips-delay-filler",
  cl::init(false),
  cl::desc("Fill all delay slots with NOPs."),
  cl::Hidden);

static cl::opt<bool> DisableForwardSearch(
  "disable-mips-df-forward-search",
  cl::init(true),
  cl::desc("Disallow MIPS delay filler to search forward."),
  cl::Hidden);

static cl::opt<bool> DisableSuccBBSearch(
  "disable-mips-df-succbb-search",
  cl::init(true),
  cl::desc("Disallow MIPS delay filler to search successor basic blocks."),
  cl::Hidden);

static cl::opt<bool> DisableBackwardSearch(
  "disable-mips-df-backward-search",
  cl::init(false),
  cl::desc("Disallow MIPS delay filler to search backward."),
  cl::Hidden);

enum CompactBranchPolicy { … };

static cl::opt<CompactBranchPolicy> MipsCompactBranchPolicy(
    "mips-compact-branches", cl::Optional, cl::init(CB_Optimal),
    cl::desc("MIPS Specific: Compact branch policy."),
    cl::values(clEnumValN(CB_Never, "never",
                          "Do not use compact branches if possible."),
               clEnumValN(CB_Optimal, "optimal",
                          "Use compact branches where appropriate (default)."),
               clEnumValN(CB_Always, "always",
                          "Always use compact branches if possible.")));

namespace {

  Iter;
  ReverseIter;
  BB2BrMap;

  class RegDefsUses { … };

  /// Base class for inspecting loads and stores.
  class InspectMemInstr { … };

  /// This subclass rejects any memory instructions.
  class NoMemInstr : public InspectMemInstr { … };

  /// This subclass accepts loads from stacks and constant loads.
  class LoadFromStackOrConst : public InspectMemInstr { … };

  /// This subclass uses memory dependence information to determine whether a
  /// memory instruction can be moved to a delay slot.
  class MemDefsUses : public InspectMemInstr { … };

  class MipsDelaySlotFiller : public MachineFunctionPass { … };

} // end anonymous namespace

char MipsDelaySlotFiller::ID = …;

static bool hasUnoccupiedSlot(const MachineInstr *MI) { … }

INITIALIZE_PASS(…)

/// This function inserts clones of Filler into predecessor blocks.
static void insertDelayFiller(Iter Filler, const BB2BrMap &BrMap) { … }

/// This function adds registers Filler defines to MBB's live-in register list.
static void addLiveInRegs(Iter Filler, MachineBasicBlock &MBB) { … }

RegDefsUses::RegDefsUses(const TargetRegisterInfo &TRI)
    : … { … }

void RegDefsUses::init(const MachineInstr &MI) { … }

void RegDefsUses::setCallerSaved(const MachineInstr &MI) { … }

void RegDefsUses::setUnallocatableRegs(const MachineFunction &MF) { … }

void RegDefsUses::addLiveOut(const MachineBasicBlock &MBB,
                             const MachineBasicBlock &SuccBB) { … }

bool RegDefsUses::update(const MachineInstr &MI, unsigned Begin, unsigned End) { … }

bool RegDefsUses::checkRegDefsUses(BitVector &NewDefs, BitVector &NewUses,
                                   unsigned Reg, bool IsDef) const { … }

bool RegDefsUses::isRegInSet(const BitVector &RegSet, unsigned Reg) const { … }

bool InspectMemInstr::hasHazard(const MachineInstr &MI) { … }

bool LoadFromStackOrConst::hasHazard_(const MachineInstr &MI) { … }

MemDefsUses::MemDefsUses(const MachineFrameInfo *MFI_)
    : … { … }

bool MemDefsUses::hasHazard_(const MachineInstr &MI) { … }

bool MemDefsUses::updateDefsUses(ValueType V, bool MayStore) { … }

bool MemDefsUses::
getUnderlyingObjects(const MachineInstr &MI,
                     SmallVectorImpl<ValueType> &Objects) const { … }

// Replace Branch with the compact branch instruction.
Iter MipsDelaySlotFiller::replaceWithCompactBranch(MachineBasicBlock &MBB,
                                                   Iter Branch,
                                                   const DebugLoc &DL) { … }

// For given opcode returns opcode of corresponding instruction with short
// delay slot.
// For the pseudo TAILCALL*_MM instructions return the short delay slot
// form. Unfortunately, TAILCALL<->b16 is denied as b16 has a limited range
// that is too short to make use of for tail calls.
static int getEquivalentCallShort(int Opcode) { … }

/// runOnMachineBasicBlock - Fill in delay slots for the given basic block.
/// We assume there is only one delay slot per delayed instruction.
bool MipsDelaySlotFiller::runOnMachineBasicBlock(MachineBasicBlock &MBB) { … }

template <typename IterTy>
bool MipsDelaySlotFiller::searchRange(MachineBasicBlock &MBB, IterTy Begin,
                                      IterTy End, RegDefsUses &RegDU,
                                      InspectMemInstr &IM, Iter Slot,
                                      IterTy &Filler) const { … }

bool MipsDelaySlotFiller::searchBackward(MachineBasicBlock &MBB,
                                         MachineInstr &Slot) const { … }

bool MipsDelaySlotFiller::searchForward(MachineBasicBlock &MBB,
                                        Iter Slot) const { … }

bool MipsDelaySlotFiller::searchSuccBBs(MachineBasicBlock &MBB,
                                        Iter Slot) const { … }

MachineBasicBlock *
MipsDelaySlotFiller::selectSuccBB(MachineBasicBlock &B) const { … }

std::pair<MipsInstrInfo::BranchType, MachineInstr *>
MipsDelaySlotFiller::getBranch(MachineBasicBlock &MBB,
                               const MachineBasicBlock &Dst) const { … }

bool MipsDelaySlotFiller::examinePred(MachineBasicBlock &Pred,
                                      const MachineBasicBlock &Succ,
                                      RegDefsUses &RegDU,
                                      bool &HasMultipleSuccs,
                                      BB2BrMap &BrMap) const { … }

bool MipsDelaySlotFiller::delayHasHazard(const MachineInstr &Candidate,
                                         RegDefsUses &RegDU,
                                         InspectMemInstr &IM) const { … }

bool MipsDelaySlotFiller::terminateSearch(const MachineInstr &Candidate) const { … }

/// createMipsDelaySlotFillerPass - Returns a pass that fills in delay
/// slots in Mips MachineFunctions
FunctionPass *llvm::createMipsDelaySlotFillerPass() { … }
llvm/llvm/lib/Target/Mips/MipsDelaySlotFiller.cpp
