HexagonGenInsert.cpp | Explore in Territory

//===- HexagonGenInsert.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
//
//===----------------------------------------------------------------------===//

#include "BitTracker.h"
#include "HexagonBitTracker.h"
#include "HexagonInstrInfo.h"
#include "HexagonRegisterInfo.h"
#include "HexagonSubtarget.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineDominators.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/TargetRegisterInfo.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/Timer.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <utility>
#include <vector>

#define DEBUG_TYPE …

usingnamespacellvm;

static cl::opt<unsigned>
    VRegIndexCutoff("insert-vreg-cutoff", cl::init(~0U), cl::Hidden,
                    cl::desc("Vreg# cutoff for insert generation."));
// The distance cutoff is selected based on the precheckin-perf results:
// cutoffs 20, 25, 35, and 40 are worse than 30.
static cl::opt<unsigned>
    VRegDistCutoff("insert-dist-cutoff", cl::init(30U), cl::Hidden,
                   cl::desc("Vreg distance cutoff for insert "
                            "generation."));

// Limit the container sizes for extreme cases where we run out of memory.
static cl::opt<unsigned>
    MaxORLSize("insert-max-orl", cl::init(4096), cl::Hidden,
               cl::desc("Maximum size of OrderedRegisterList"));
static cl::opt<unsigned> MaxIFMSize("insert-max-ifmap", cl::init(1024),
                                    cl::Hidden,
                                    cl::desc("Maximum size of IFMap"));

static cl::opt<bool> OptTiming("insert-timing", cl::Hidden,
                               cl::desc("Enable timing of insert generation"));
static cl::opt<bool>
    OptTimingDetail("insert-timing-detail", cl::Hidden,
                    cl::desc("Enable detailed timing of insert "
                             "generation"));

static cl::opt<bool> OptSelectAll0("insert-all0", cl::init(false), cl::Hidden);
static cl::opt<bool> OptSelectHas0("insert-has0", cl::init(false), cl::Hidden);
// Whether to construct constant values via "insert". Could eliminate constant
// extenders, but often not practical.
static cl::opt<bool> OptConst("insert-const", cl::init(false), cl::Hidden);

// The preprocessor gets confused when the DEBUG macro is passed larger
// chunks of code. Use this function to detect debugging.
inline static bool isDebug() { … }

namespace {

  // Set of virtual registers, based on BitVector.
  struct RegisterSet : private BitVector { … };

  struct PrintRegSet { … };

  raw_ostream &operator<< (raw_ostream &OS, const PrintRegSet &P) { … }

  // A convenience class to associate unsigned numbers (such as virtual
  // registers) with unsigned numbers.
  struct UnsignedMap : public DenseMap<unsigned,unsigned> { … };

  // A utility to establish an ordering between virtual registers:
  // VRegA < VRegB  <=>  RegisterOrdering[VRegA] < RegisterOrdering[VRegB]
  // This is meant as a cache for the ordering of virtual registers defined
  // by a potentially expensive comparison function, or obtained by a proce-
  // dure that should not be repeated each time two registers are compared.
  struct RegisterOrdering : public UnsignedMap { … };

  // Ordering of bit values. This class does not have operator[], but
  // is supplies a comparison operator() for use in std:: algorithms.
  // The order is as follows:
  // - 0 < 1 < ref
  // - ref1 < ref2, if ord(ref1.Reg) < ord(ref2.Reg),
  //   or ord(ref1.Reg) == ord(ref2.Reg), and ref1.Pos < ref2.Pos.
  struct BitValueOrdering { … };

} // end anonymous namespace

bool BitValueOrdering::operator() (const BitTracker::BitValue &V1,
      const BitTracker::BitValue &V2) const { … }

namespace {

  // Cache for the BitTracker's cell map. Map lookup has a logarithmic
  // complexity, this class will memoize the lookup results to reduce
  // the access time for repeated lookups of the same cell.
  struct CellMapShadow { … };

  // Comparator class for lexicographic ordering of virtual registers
  // according to the corresponding BitTracker::RegisterCell objects.
  struct RegisterCellLexCompare { … };

  // Comparator class for lexicographic ordering of virtual registers
  // according to the specified bits of the corresponding BitTracker::
  // RegisterCell objects.
  // Specifically, this class will be used to compare bit B of a register
  // cell for a selected virtual register R with bit N of any register
  // other than R.
  struct RegisterCellBitCompareSel { … };

} // end anonymous namespace

bool RegisterCellLexCompare::operator() (unsigned VR1, unsigned VR2) const { … }

bool RegisterCellBitCompareSel::operator() (unsigned VR1, unsigned VR2) const { … }

namespace {

  class OrderedRegisterList { … };

  struct PrintORL { … };

  raw_ostream &operator<< (raw_ostream &OS, const PrintORL &P) { … }

} // end anonymous namespace

void OrderedRegisterList::insert(unsigned VR) { … }

void OrderedRegisterList::remove(unsigned VR) { … }

namespace {

  // A record of the insert form. The fields correspond to the operands
  // of the "insert" instruction:
  // ... = insert(SrcR, InsR, #Wdh, #Off)
  struct IFRecord { … };

  struct PrintIFR { … };

  raw_ostream &operator<< (raw_ostream &OS, const PrintIFR &P) { … }

  IFRecordWithRegSet;

} // end anonymous namespace

namespace llvm {

  void initializeHexagonGenInsertPass(PassRegistry&);
  FunctionPass *createHexagonGenInsert();

} // end namespace llvm

namespace {

  class HexagonGenInsert : public MachineFunctionPass { … };

} // end anonymous namespace

char HexagonGenInsert::ID = …;

void HexagonGenInsert::dump_map() const { … }

void HexagonGenInsert::buildOrderingMF(RegisterOrdering &RO) const { … }

void HexagonGenInsert::buildOrderingBT(RegisterOrdering &RB,
      RegisterOrdering &RO) const { … }

inline bool HexagonGenInsert::isIntClass(const TargetRegisterClass *RC) const { … }

bool HexagonGenInsert::isConstant(unsigned VR) const { … }

bool HexagonGenInsert::isSmallConstant(unsigned VR) const { … }

bool HexagonGenInsert::isValidInsertForm(unsigned DstR, unsigned SrcR,
      unsigned InsR, uint16_t L, uint16_t S) const { … }

bool HexagonGenInsert::findSelfReference(unsigned VR) const { … }

bool HexagonGenInsert::findNonSelfReference(unsigned VR) const { … }

void HexagonGenInsert::getInstrDefs(const MachineInstr *MI,
      RegisterSet &Defs) const { … }

void HexagonGenInsert::getInstrUses(const MachineInstr *MI,
      RegisterSet &Uses) const { … }

unsigned HexagonGenInsert::distance(const MachineBasicBlock *FromB,
      const MachineBasicBlock *ToB, const UnsignedMap &RPO,
      PairMapType &M) const { … }

unsigned HexagonGenInsert::distance(MachineBasicBlock::const_iterator FromI,
      MachineBasicBlock::const_iterator ToI, const UnsignedMap &RPO,
      PairMapType &M) const { … }

bool HexagonGenInsert::findRecordInsertForms(unsigned VR,
      OrderedRegisterList &AVs) { … }

void HexagonGenInsert::collectInBlock(MachineBasicBlock *B,
      OrderedRegisterList &AVs) { … }

void HexagonGenInsert::findRemovableRegisters(unsigned VR, IFRecord IF,
      RegisterSet &RMs) const { … }

void HexagonGenInsert::computeRemovableRegisters() { … }

void HexagonGenInsert::pruneEmptyLists() { … }

void HexagonGenInsert::pruneCoveredSets(unsigned VR) { … }

void HexagonGenInsert::pruneUsesTooFar(unsigned VR, const UnsignedMap &RPO,
      PairMapType &M) { … }

void HexagonGenInsert::pruneRegCopies(unsigned VR) { … }

void HexagonGenInsert::pruneCandidates() { … }

namespace {

  // Class for comparing IF candidates for registers that have multiple of
  // them. The smaller the candidate, according to this ordering, the better.
  // First, compare the number of zeros in the associated potentially remova-
  // ble register sets. "Zero" indicates that the register is very likely to
  // become dead after this transformation.
  // Second, compare "averages", i.e. use-count per size. The lower wins.
  // After that, it does not really matter which one is smaller. Resolve
  // the tie in some deterministic way.
  struct IFOrdering { … };

} // end anonymous namespace

bool IFOrdering::operator() (const IFRecordWithRegSet &A,
      const IFRecordWithRegSet &B) const { … }

void IFOrdering::stats(const RegisterSet &Rs, unsigned &Size, unsigned &Zero,
      unsigned &Sum) const { … }

void HexagonGenInsert::selectCandidates() { … }

bool HexagonGenInsert::generateInserts() { … }

bool HexagonGenInsert::removeDeadCode(MachineDomTreeNode *N) { … }

bool HexagonGenInsert::runOnMachineFunction(MachineFunction &MF) { … }

FunctionPass *llvm::createHexagonGenInsert() { … }

//===----------------------------------------------------------------------===//
//                         Public Constructor Functions
//===----------------------------------------------------------------------===//

INITIALIZE_PASS_BEGIN(HexagonGenInsert, "hexinsert",
  "Hexagon generate \"insert\" instructions", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
INITIALIZE_PASS_END(HexagonGenInsert, "hexinsert",
  "Hexagon generate \"insert\" instructions", false, false)
llvm/llvm/lib/Target/Hexagon/HexagonGenInsert.cpp
