MipsConstantIslandPass.cpp | Explore in Territory

//===- MipsConstantIslandPass.cpp - Emit Pc Relative loads ----------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// This pass is used to make Pc relative loads of constants.
// For now, only Mips16 will use this.
//
// Loading constants inline is expensive on Mips16 and it's in general better
// to place the constant nearby in code space and then it can be loaded with a
// simple 16 bit load instruction.
//
// The constants can be not just numbers but addresses of functions and labels.
// This can be particularly helpful in static relocation mode for embedded
// non-linux targets.
//
//===----------------------------------------------------------------------===//

#include "Mips.h"
#include "Mips16InstrInfo.h"
#include "MipsMachineFunction.h"
#include "MipsSubtarget.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineConstantPool.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/Config/llvm-config.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Type.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/Format.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <vector>

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumCPEs,       "Number of constpool entries");
STATISTIC(NumSplit,      "Number of uncond branches inserted");
STATISTIC(NumCBrFixed,   "Number of cond branches fixed");
STATISTIC(NumUBrFixed,   "Number of uncond branches fixed");

// FIXME: This option should be removed once it has received sufficient testing.
static cl::opt<bool>
AlignConstantIslands("mips-align-constant-islands", cl::Hidden, cl::init(true),
          cl::desc("Align constant islands in code"));

// Rather than do make check tests with huge amounts of code, we force
// the test to use this amount.
static cl::opt<int> ConstantIslandsSmallOffset(
  "mips-constant-islands-small-offset",
  cl::init(0),
  cl::desc("Make small offsets be this amount for testing purposes"),
  cl::Hidden);

// For testing purposes we tell it to not use relaxed load forms so that it
// will split blocks.
static cl::opt<bool> NoLoadRelaxation(
  "mips-constant-islands-no-load-relaxation",
  cl::init(false),
  cl::desc("Don't relax loads to long loads - for testing purposes"),
  cl::Hidden);

static unsigned int branchTargetOperand(MachineInstr *MI) { … }

static unsigned int longformBranchOpcode(unsigned int Opcode) { … }

// FIXME: need to go through this whole constant islands port and check
// the math for branch ranges and clean this up and make some functions
// to calculate things that are done many times identically.
// Need to refactor some of the code to call this routine.
static unsigned int branchMaxOffsets(unsigned int Opcode) { … }

namespace {

  Iter;
  ReverseIter;

  /// MipsConstantIslands - Due to limited PC-relative displacements, Mips
  /// requires constant pool entries to be scattered among the instructions
  /// inside a function.  To do this, it completely ignores the normal LLVM
  /// constant pool; instead, it places constants wherever it feels like with
  /// special instructions.
  ///
  /// The terminology used in this pass includes:
  ///   Islands - Clumps of constants placed in the function.
  ///   Water   - Potential places where an island could be formed.
  ///   CPE     - A constant pool entry that has been placed somewhere, which
  ///             tracks a list of users.

  class MipsConstantIslands : public MachineFunctionPass { … };

} // end anonymous namespace

char MipsConstantIslands::ID = …;

bool MipsConstantIslands::isOffsetInRange
  (unsigned UserOffset, unsigned TrialOffset,
   const CPUser &U) { … }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
/// print block size and offset information - debugging
LLVM_DUMP_METHOD void MipsConstantIslands::dumpBBs() {
  for (unsigned J = 0, E = BBInfo.size(); J !=E; ++J) {
    const BasicBlockInfo &BBI = BBInfo[J];
    dbgs() << format("%08x %bb.%u\t", BBI.Offset, J)
           << format(" size=%#x\n", BBInfo[J].Size);
  }
}
#endif

bool MipsConstantIslands::runOnMachineFunction(MachineFunction &mf) { … }

/// doInitialPlacement - Perform the initial placement of the constant pool
/// entries.  To start with, we put them all at the end of the function.
void
MipsConstantIslands::doInitialPlacement(std::vector<MachineInstr*> &CPEMIs) { … }

/// BBHasFallthrough - Return true if the specified basic block can fallthrough
/// into the block immediately after it.
static bool BBHasFallthrough(MachineBasicBlock *MBB) { … }

/// findConstPoolEntry - Given the constpool index and CONSTPOOL_ENTRY MI,
/// look up the corresponding CPEntry.
MipsConstantIslands::CPEntry
*MipsConstantIslands::findConstPoolEntry(unsigned CPI,
                                        const MachineInstr *CPEMI) { … }

/// getCPEAlign - Returns the required alignment of the constant pool entry
/// represented by CPEMI.  Alignment is measured in log2(bytes) units.
Align MipsConstantIslands::getCPEAlign(const MachineInstr &CPEMI) { … }

/// initializeFunctionInfo - Do the initial scan of the function, building up
/// information about the sizes of each block, the location of all the water,
/// and finding all of the constant pool users.
void MipsConstantIslands::
initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs) { … }

/// computeBlockSize - Compute the size and some alignment information for MBB.
/// This function updates BBInfo directly.
void MipsConstantIslands::computeBlockSize(MachineBasicBlock *MBB) { … }

/// getOffsetOf - Return the current offset of the specified machine instruction
/// from the start of the function.  This offset changes as stuff is moved
/// around inside the function.
unsigned MipsConstantIslands::getOffsetOf(MachineInstr *MI) const { … }

/// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB
/// ID.
static bool CompareMBBNumbers(const MachineBasicBlock *LHS,
                              const MachineBasicBlock *RHS) { … }

/// updateForInsertedWaterBlock - When a block is newly inserted into the
/// machine function, it upsets all of the block numbers.  Renumber the blocks
/// and update the arrays that parallel this numbering.
void MipsConstantIslands::updateForInsertedWaterBlock
  (MachineBasicBlock *NewBB) { … }

unsigned MipsConstantIslands::getUserOffset(CPUser &U) const { … }

/// Split the basic block containing MI into two blocks, which are joined by
/// an unconditional branch.  Update data structures and renumber blocks to
/// account for this change and returns the newly created block.
MachineBasicBlock *
MipsConstantIslands::splitBlockBeforeInstr(MachineInstr &MI) { … }

/// isOffsetInRange - Checks whether UserOffset (the location of a constant pool
/// reference) is within MaxDisp of TrialOffset (a proposed location of a
/// constant pool entry).
bool MipsConstantIslands::isOffsetInRange(unsigned UserOffset,
                                         unsigned TrialOffset, unsigned MaxDisp,
                                         bool NegativeOK) { … }

/// isWaterInRange - Returns true if a CPE placed after the specified
/// Water (a basic block) will be in range for the specific MI.
///
/// Compute how much the function will grow by inserting a CPE after Water.
bool MipsConstantIslands::isWaterInRange(unsigned UserOffset,
                                        MachineBasicBlock* Water, CPUser &U,
                                        unsigned &Growth) { … }

/// isCPEntryInRange - Returns true if the distance between specific MI and
/// specific ConstPool entry instruction can fit in MI's displacement field.
bool MipsConstantIslands::isCPEntryInRange
  (MachineInstr *MI, unsigned UserOffset,
   MachineInstr *CPEMI, unsigned MaxDisp,
   bool NegOk, bool DoDump) { … }

#ifndef NDEBUG
/// BBIsJumpedOver - Return true of the specified basic block's only predecessor
/// unconditionally branches to its only successor.
static bool BBIsJumpedOver(MachineBasicBlock *MBB) {
  if (MBB->pred_size() != 1 || MBB->succ_size() != 1)
    return false;
  MachineBasicBlock *Succ = *MBB->succ_begin();
  MachineBasicBlock *Pred = *MBB->pred_begin();
  MachineInstr *PredMI = &Pred->back();
  if (PredMI->getOpcode() == Mips::Bimm16)
    return PredMI->getOperand(0).getMBB() == Succ;
  return false;
}
#endif

void MipsConstantIslands::adjustBBOffsetsAfter(MachineBasicBlock *BB) { … }

/// decrementCPEReferenceCount - find the constant pool entry with index CPI
/// and instruction CPEMI, and decrement its refcount.  If the refcount
/// becomes 0 remove the entry and instruction.  Returns true if we removed
/// the entry, false if we didn't.
bool MipsConstantIslands::decrementCPEReferenceCount(unsigned CPI,
                                                    MachineInstr *CPEMI) { … }

/// LookForCPEntryInRange - see if the currently referenced CPE is in range;
/// if not, see if an in-range clone of the CPE is in range, and if so,
/// change the data structures so the user references the clone.  Returns:
/// 0 = no existing entry found
/// 1 = entry found, and there were no code insertions or deletions
/// 2 = entry found, and there were code insertions or deletions
int MipsConstantIslands::findInRangeCPEntry(CPUser& U, unsigned UserOffset)
{ … }

/// LookForCPEntryInRange - see if the currently referenced CPE is in range;
/// This version checks if the longer form of the instruction can be used to
/// to satisfy things.
/// if not, see if an in-range clone of the CPE is in range, and if so,
/// change the data structures so the user references the clone.  Returns:
/// 0 = no existing entry found
/// 1 = entry found, and there were no code insertions or deletions
/// 2 = entry found, and there were code insertions or deletions
int MipsConstantIslands::findLongFormInRangeCPEntry
  (CPUser& U, unsigned UserOffset)
{ … }

/// getUnconditionalBrDisp - Returns the maximum displacement that can fit in
/// the specific unconditional branch instruction.
static inline unsigned getUnconditionalBrDisp(int Opc) { … }

/// findAvailableWater - Look for an existing entry in the WaterList in which
/// we can place the CPE referenced from U so it's within range of U's MI.
/// Returns true if found, false if not.  If it returns true, WaterIter
/// is set to the WaterList entry.
/// To ensure that this pass
/// terminates, the CPE location for a particular CPUser is only allowed to
/// move to a lower address, so search backward from the end of the list and
/// prefer the first water that is in range.
bool MipsConstantIslands::findAvailableWater(CPUser &U, unsigned UserOffset,
                                      water_iterator &WaterIter) { … }

/// createNewWater - No existing WaterList entry will work for
/// CPUsers[CPUserIndex], so create a place to put the CPE.  The end of the
/// block is used if in range, and the conditional branch munged so control
/// flow is correct.  Otherwise the block is split to create a hole with an
/// unconditional branch around it.  In either case NewMBB is set to a
/// block following which the new island can be inserted (the WaterList
/// is not adjusted).
void MipsConstantIslands::createNewWater(unsigned CPUserIndex,
                                        unsigned UserOffset,
                                        MachineBasicBlock *&NewMBB) { … }

/// handleConstantPoolUser - Analyze the specified user, checking to see if it
/// is out-of-range.  If so, pick up the constant pool value and move it some
/// place in-range.  Return true if we changed any addresses (thus must run
/// another pass of branch lengthening), false otherwise.
bool MipsConstantIslands::handleConstantPoolUser(unsigned CPUserIndex) { … }

/// removeDeadCPEMI - Remove a dead constant pool entry instruction. Update
/// sizes and offsets of impacted basic blocks.
void MipsConstantIslands::removeDeadCPEMI(MachineInstr *CPEMI) { … }

/// removeUnusedCPEntries - Remove constant pool entries whose refcounts
/// are zero.
bool MipsConstantIslands::removeUnusedCPEntries() { … }

/// isBBInRange - Returns true if the distance between specific MI and
/// specific BB can fit in MI's displacement field.
bool MipsConstantIslands::isBBInRange
  (MachineInstr *MI,MachineBasicBlock *DestBB, unsigned MaxDisp) { … }

/// fixupImmediateBr - Fix up an immediate branch whose destination is too far
/// away to fit in its displacement field.
bool MipsConstantIslands::fixupImmediateBr(ImmBranch &Br) { … }

/// fixupUnconditionalBr - Fix up an unconditional branch whose destination is
/// too far away to fit in its displacement field. If the LR register has been
/// spilled in the epilogue, then we can use BL to implement a far jump.
/// Otherwise, add an intermediate branch instruction to a branch.
bool
MipsConstantIslands::fixupUnconditionalBr(ImmBranch &Br) { … }

/// fixupConditionalBr - Fix up a conditional branch whose destination is too
/// far away to fit in its displacement field. It is converted to an inverse
/// conditional branch + an unconditional branch to the destination.
bool
MipsConstantIslands::fixupConditionalBr(ImmBranch &Br) { … }

void MipsConstantIslands::prescanForConstants() { … }

/// Returns a pass that converts branches to long branches.
FunctionPass *llvm::createMipsConstantIslandPass() { … }
llvm/llvm/lib/Target/Mips/MipsConstantIslandPass.cpp
