BitTracker.cpp | Explore in Territory

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

// SSA-based bit propagation.
//
// The purpose of this code is, for a given virtual register, to provide
// information about the value of each bit in the register. The values
// of bits are represented by the class BitValue, and take one of four
// cases: 0, 1, "ref" and "bottom". The 0 and 1 are rather clear, the
// "ref" value means that the bit is a copy of another bit (which itself
// cannot be a copy of yet another bit---such chains are not allowed).
// A "ref" value is associated with a BitRef structure, which indicates
// which virtual register, and which bit in that register is the origin
// of the value. For example, given an instruction
//   %2 = ASL %1, 1
// assuming that nothing is known about bits of %1, bit 1 of %2
// will be a "ref" to (%1, 0). If there is a subsequent instruction
//   %3 = ASL %2, 2
// then bit 3 of %3 will be a "ref" to (%1, 0) as well.
// The "bottom" case means that the bit's value cannot be determined,
// and that this virtual register actually defines it. The "bottom" case
// is discussed in detail in BitTracker.h. In fact, "bottom" is a "ref
// to self", so for the %1 above, the bit 0 of it will be a "ref" to
// (%1, 0), bit 1 will be a "ref" to (%1, 1), etc.
//
// The tracker implements the Wegman-Zadeck algorithm, originally developed
// for SSA-based constant propagation. Each register is represented as
// a sequence of bits, with the convention that bit 0 is the least signi-
// ficant bit. Each bit is propagated individually. The class RegisterCell
// implements the register's representation, and is also the subject of
// the lattice operations in the tracker.
//
// The intended usage of the bit tracker is to create a target-specific
// machine instruction evaluator, pass the evaluator to the BitTracker
// object, and run the tracker. The tracker will then collect the bit
// value information for a given machine function. After that, it can be
// queried for the cells for each virtual register.
// Sample code:
//   const TargetSpecificEvaluator TSE(TRI, MRI);
//   BitTracker BT(TSE, MF);
//   BT.run();
//   ...
//   unsigned Reg = interestingRegister();
//   RegisterCell RC = BT.get(Reg);
//   if (RC[3].is(1))
//      Reg0bit3 = 1;
//
// The code below is intended to be fully target-independent.

#include "BitTracker.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/IR/Constants.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <cstdint>
#include <iterator>

usingnamespacellvm;

BT;

namespace {

  // Local trickery to pretty print a register (without the whole "%number"
  // business).
  struct printv { … };

  raw_ostream &operator<< (raw_ostream &OS, const printv &PV) { … }

} // end anonymous namespace

namespace llvm {

  raw_ostream &operator<<(raw_ostream &OS, const BT::BitValue &BV) { … }

  raw_ostream &operator<<(raw_ostream &OS, const BT::RegisterCell &RC) { … }

} // end namespace llvm

void BitTracker::print_cells(raw_ostream &OS) const { … }

BitTracker::BitTracker(const MachineEvaluator &E, MachineFunction &F)
    : … { … }

BitTracker::~BitTracker() { … }

// If we were allowed to update a cell for a part of a register, the meet
// operation would need to be parametrized by the register number and the
// exact part of the register, so that the computer BitRefs correspond to
// the actual bits of the "self" register.
// While this cannot happen in the current implementation, I'm not sure
// if this should be ruled out in the future.
bool BT::RegisterCell::meet(const RegisterCell &RC, Register SelfR) { … }

// Insert the entire cell RC into the current cell at position given by M.
BT::RegisterCell &BT::RegisterCell::insert(const BT::RegisterCell &RC,
      const BitMask &M) { … }

BT::RegisterCell BT::RegisterCell::extract(const BitMask &M) const { … }

BT::RegisterCell &BT::RegisterCell::rol(uint16_t Sh) { … }

BT::RegisterCell &BT::RegisterCell::fill(uint16_t B, uint16_t E,
      const BitValue &V) { … }

BT::RegisterCell &BT::RegisterCell::cat(const RegisterCell &RC) { … }

uint16_t BT::RegisterCell::ct(bool B) const { … }

uint16_t BT::RegisterCell::cl(bool B) const { … }

bool BT::RegisterCell::operator== (const RegisterCell &RC) const { … }

BT::RegisterCell &BT::RegisterCell::regify(unsigned R) { … }

uint16_t BT::MachineEvaluator::getRegBitWidth(const RegisterRef &RR) const { … }

BT::RegisterCell BT::MachineEvaluator::getCell(const RegisterRef &RR,
      const CellMapType &M) const { … }

void BT::MachineEvaluator::putCell(const RegisterRef &RR, RegisterCell RC,
      CellMapType &M) const { … }

// Check if the cell represents a compile-time integer value.
bool BT::MachineEvaluator::isInt(const RegisterCell &A) const { … }

// Convert a cell to the integer value. The result must fit in uint64_t.
uint64_t BT::MachineEvaluator::toInt(const RegisterCell &A) const { … }

// Evaluator helper functions. These implement some common operation on
// register cells that can be used to implement target-specific instructions
// in a target-specific evaluator.

BT::RegisterCell BT::MachineEvaluator::eIMM(int64_t V, uint16_t W) const { … }

BT::RegisterCell BT::MachineEvaluator::eIMM(const ConstantInt *CI) const { … }

BT::RegisterCell BT::MachineEvaluator::eADD(const RegisterCell &A1,
      const RegisterCell &A2) const { … }

BT::RegisterCell BT::MachineEvaluator::eSUB(const RegisterCell &A1,
      const RegisterCell &A2) const { … }

BT::RegisterCell BT::MachineEvaluator::eMLS(const RegisterCell &A1,
      const RegisterCell &A2) const { … }

BT::RegisterCell BT::MachineEvaluator::eMLU(const RegisterCell &A1,
      const RegisterCell &A2) const { … }

BT::RegisterCell BT::MachineEvaluator::eASL(const RegisterCell &A1,
      uint16_t Sh) const { … }

BT::RegisterCell BT::MachineEvaluator::eLSR(const RegisterCell &A1,
      uint16_t Sh) const { … }

BT::RegisterCell BT::MachineEvaluator::eASR(const RegisterCell &A1,
      uint16_t Sh) const { … }

BT::RegisterCell BT::MachineEvaluator::eAND(const RegisterCell &A1,
      const RegisterCell &A2) const { … }

BT::RegisterCell BT::MachineEvaluator::eORL(const RegisterCell &A1,
      const RegisterCell &A2) const { … }

BT::RegisterCell BT::MachineEvaluator::eXOR(const RegisterCell &A1,
      const RegisterCell &A2) const { … }

BT::RegisterCell BT::MachineEvaluator::eNOT(const RegisterCell &A1) const { … }

BT::RegisterCell BT::MachineEvaluator::eSET(const RegisterCell &A1,
      uint16_t BitN) const { … }

BT::RegisterCell BT::MachineEvaluator::eCLR(const RegisterCell &A1,
      uint16_t BitN) const { … }

BT::RegisterCell BT::MachineEvaluator::eCLB(const RegisterCell &A1, bool B,
      uint16_t W) const { … }

BT::RegisterCell BT::MachineEvaluator::eCTB(const RegisterCell &A1, bool B,
      uint16_t W) const { … }

BT::RegisterCell BT::MachineEvaluator::eSXT(const RegisterCell &A1,
      uint16_t FromN) const { … }

BT::RegisterCell BT::MachineEvaluator::eZXT(const RegisterCell &A1,
      uint16_t FromN) const { … }

BT::RegisterCell BT::MachineEvaluator::eXTR(const RegisterCell &A1,
      uint16_t B, uint16_t E) const { … }

BT::RegisterCell BT::MachineEvaluator::eINS(const RegisterCell &A1,
      const RegisterCell &A2, uint16_t AtN) const { … }

BT::BitMask BT::MachineEvaluator::mask(Register Reg, unsigned Sub) const { … }

uint16_t BT::MachineEvaluator::getPhysRegBitWidth(MCRegister Reg) const { … }

bool BT::MachineEvaluator::evaluate(const MachineInstr &MI,
                                    const CellMapType &Inputs,
                                    CellMapType &Outputs) const { … }

bool BT::UseQueueType::Cmp::operator()(const MachineInstr *InstA,
                                       const MachineInstr *InstB) const { … }

// Main W-Z implementation.

void BT::visitPHI(const MachineInstr &PI) { … }

void BT::visitNonBranch(const MachineInstr &MI) { … }

void BT::visitBranchesFrom(const MachineInstr &BI) { … }

void BT::visitUsesOf(Register Reg) { … }

BT::RegisterCell BT::get(RegisterRef RR) const { … }

void BT::put(RegisterRef RR, const RegisterCell &RC) { … }

// Replace all references to bits from OldRR with the corresponding bits
// in NewRR.
void BT::subst(RegisterRef OldRR, RegisterRef NewRR) { … }

// Check if the block has been "executed" during propagation. (If not, the
// block is dead, but it may still appear to be reachable.)
bool BT::reached(const MachineBasicBlock *B) const { … }

// Visit an individual instruction. This could be a newly added instruction,
// or one that has been modified by an optimization.
void BT::visit(const MachineInstr &MI) { … }

void BT::reset() { … }

void BT::runEdgeQueue(BitVector &BlockScanned) { … }

void BT::runUseQueue() { … }

void BT::run() { … }
llvm/llvm/lib/Target/Hexagon/BitTracker.cpp
