HexagonConstPropagation.cpp | Explore in Territory

//===- HexagonConstPropagation.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 "HexagonInstrInfo.h"
#include "HexagonRegisterInfo.h"
#include "HexagonSubtarget.h"
#include "llvm/ADT/APFloat.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.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/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Type.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <cstdint>
#include <cstring>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <utility>
#include <vector>

#define DEBUG_TYPE …

usingnamespacellvm;

namespace {

  // Properties of a value that are tracked by the propagation.
  // A property that is marked as present (i.e. bit is set) dentes that the
  // value is known (proven) to have this property. Not all combinations
  // of bits make sense, for example Zero and NonZero are mutually exclusive,
  // but on the other hand, Zero implies Finite. In this case, whenever
  // the Zero property is present, Finite should also be present.
  class ConstantProperties { … };

  // A representation of a register as it can appear in a MachineOperand,
  // i.e. a pair register:subregister.

  // FIXME: Use TargetInstrInfo::RegSubRegPair. Also duplicated in
  // HexagonGenPredicate
  struct RegisterSubReg { … };

  // Lattice cell, based on that was described in the W-Z paper on constant
  // propagation.
  // Latice cell will be allowed to hold multiple constant values. While
  // multiple values would normally indicate "bottom", we can still derive
  // some useful information from them. For example, comparison X > 0
  // could be folded if all the values in the cell associated with X are
  // positive.
  class LatticeCell { … };

#ifndef NDEBUG
  raw_ostream &operator<< (raw_ostream &os, const LatticeCell &L) {
    L.print(os);
    return os;
  }
#endif

  class MachineConstEvaluator;

  class MachineConstPropagator { … };

  // The "evaluator/rewriter" of machine instructions. This is an abstract
  // base class that provides the interface that the propagator will use,
  // as well as some helper functions that are target-independent.
  class MachineConstEvaluator { … };

} // end anonymous namespace

uint32_t ConstantProperties::deduce(const Constant *C) { … }

// Convert a cell from a set of specific values to a cell that tracks
// properties.
bool LatticeCell::convertToProperty() { … }

#ifndef NDEBUG
void LatticeCell::print(raw_ostream &os) const {
  if (isProperty()) {
    os << "{ ";
    uint32_t Ps = properties();
    if (Ps & ConstantProperties::Zero)
      os << "zero ";
    if (Ps & ConstantProperties::NonZero)
      os << "nonzero ";
    if (Ps & ConstantProperties::Finite)
      os << "finite ";
    if (Ps & ConstantProperties::Infinity)
      os << "infinity ";
    if (Ps & ConstantProperties::NaN)
      os << "nan ";
    if (Ps & ConstantProperties::PosOrZero)
      os << "poz ";
    if (Ps & ConstantProperties::NegOrZero)
      os << "nez ";
    os << '}';
    return;
  }

  os << "{ ";
  if (isBottom()) {
    os << "bottom";
  } else if (isTop()) {
    os << "top";
  } else {
    for (unsigned i = 0; i < size(); ++i) {
      const Constant *C = Values[i];
      if (i != 0)
        os << ", ";
      C->print(os);
    }
  }
  os << " }";
}
#endif

// "Meet" operation on two cells. This is the key of the propagation
// algorithm.
bool LatticeCell::meet(const LatticeCell &L) { … }

// Add a new constant to the cell. This is actually where the cell update
// happens. If a cell has room for more constants, the new constant is added.
// Otherwise, the cell is converted to a "property" cell (i.e. a cell that
// will track properties of the associated values, and not the values
// themselves. Care is taken to handle special cases, like "bottom", etc.
bool LatticeCell::add(const Constant *LC) { … }

// Add a property to the cell. This will force the cell to become a property-
// tracking cell.
bool LatticeCell::add(uint32_t Property) { … }

// Return the properties of the values in the cell. This is valid for any
// cell, and does not alter the cell itself.
uint32_t LatticeCell::properties() const { … }

#ifndef NDEBUG
void MachineConstPropagator::CellMap::print(raw_ostream &os,
      const TargetRegisterInfo &TRI) const {
  for (auto &I : Map)
    dbgs() << "  " << printReg(I.first, &TRI) << " -> " << I.second << '\n';
}
#endif

void MachineConstPropagator::visitPHI(const MachineInstr &PN) { … }

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

// Starting at a given branch, visit remaining branches in the block.
// Traverse over the subsequent branches for as long as the preceding one
// can fall through. Add all the possible targets to the flow work queue,
// including the potential fall-through to the layout-successor block.
void MachineConstPropagator::visitBranchesFrom(const MachineInstr &BrI) { … }

void MachineConstPropagator::visitUsesOf(unsigned Reg) { … }

bool MachineConstPropagator::computeBlockSuccessors(const MachineBasicBlock *MB,
      SetVector<const MachineBasicBlock*> &Targets) { … }

void MachineConstPropagator::removeCFGEdge(MachineBasicBlock *From,
      MachineBasicBlock *To) { … }

void MachineConstPropagator::propagate(MachineFunction &MF) { … }

bool MachineConstPropagator::rewrite(MachineFunction &MF) { … }

// This is the constant propagation algorithm as described by Wegman-Zadeck.
// Most of the terminology comes from there.
bool MachineConstPropagator::run(MachineFunction &MF) { … }

// --------------------------------------------------------------------
// Machine const evaluator.

bool MachineConstEvaluator::getCell(const RegisterSubReg &R, const CellMap &Inputs,
      LatticeCell &RC) { … }

bool MachineConstEvaluator::constToInt(const Constant *C,
      APInt &Val) const { … }

const ConstantInt *MachineConstEvaluator::intToConst(const APInt &Val) const { … }

bool MachineConstEvaluator::evaluateCMPrr(uint32_t Cmp, const RegisterSubReg &R1,
      const RegisterSubReg &R2, const CellMap &Inputs, bool &Result) { … }

bool MachineConstEvaluator::evaluateCMPri(uint32_t Cmp, const RegisterSubReg &R1,
      const APInt &A2, const CellMap &Inputs, bool &Result) { … }

bool MachineConstEvaluator::evaluateCMPrp(uint32_t Cmp, const RegisterSubReg &R1,
      uint64_t Props2, const CellMap &Inputs, bool &Result) { … }

bool MachineConstEvaluator::evaluateCMPii(uint32_t Cmp, const APInt &A1,
      const APInt &A2, bool &Result) { … }

bool MachineConstEvaluator::evaluateCMPpi(uint32_t Cmp, uint32_t Props,
      const APInt &A2, bool &Result) { … }

bool MachineConstEvaluator::evaluateCMPpp(uint32_t Cmp, uint32_t Props1,
      uint32_t Props2, bool &Result) { … }

bool MachineConstEvaluator::evaluateCOPY(const RegisterSubReg &R1,
      const CellMap &Inputs, LatticeCell &Result) { … }

bool MachineConstEvaluator::evaluateANDrr(const RegisterSubReg &R1,
      const RegisterSubReg &R2, const CellMap &Inputs, LatticeCell &Result) { … }

bool MachineConstEvaluator::evaluateANDri(const RegisterSubReg &R1,
      const APInt &A2, const CellMap &Inputs, LatticeCell &Result) { … }

bool MachineConstEvaluator::evaluateANDii(const APInt &A1,
      const APInt &A2, APInt &Result) { … }

bool MachineConstEvaluator::evaluateORrr(const RegisterSubReg &R1,
      const RegisterSubReg &R2, const CellMap &Inputs, LatticeCell &Result) { … }

bool MachineConstEvaluator::evaluateORri(const RegisterSubReg &R1,
      const APInt &A2, const CellMap &Inputs, LatticeCell &Result) { … }

bool MachineConstEvaluator::evaluateORii(const APInt &A1,
      const APInt &A2, APInt &Result) { … }

bool MachineConstEvaluator::evaluateXORrr(const RegisterSubReg &R1,
      const RegisterSubReg &R2, const CellMap &Inputs, LatticeCell &Result) { … }

bool MachineConstEvaluator::evaluateXORri(const RegisterSubReg &R1,
      const APInt &A2, const CellMap &Inputs, LatticeCell &Result) { … }

bool MachineConstEvaluator::evaluateXORii(const APInt &A1,
      const APInt &A2, APInt &Result) { … }

bool MachineConstEvaluator::evaluateZEXTr(const RegisterSubReg &R1, unsigned Width,
      unsigned Bits, const CellMap &Inputs, LatticeCell &Result) { … }

bool MachineConstEvaluator::evaluateZEXTi(const APInt &A1, unsigned Width,
      unsigned Bits, APInt &Result) { … }

bool MachineConstEvaluator::evaluateSEXTr(const RegisterSubReg &R1, unsigned Width,
      unsigned Bits, const CellMap &Inputs, LatticeCell &Result) { … }

bool MachineConstEvaluator::evaluateSEXTi(const APInt &A1, unsigned Width,
      unsigned Bits, APInt &Result) { … }

bool MachineConstEvaluator::evaluateCLBr(const RegisterSubReg &R1, bool Zeros,
      bool Ones, const CellMap &Inputs, LatticeCell &Result) { … }

bool MachineConstEvaluator::evaluateCLBi(const APInt &A1, bool Zeros,
      bool Ones, APInt &Result) { … }

bool MachineConstEvaluator::evaluateCTBr(const RegisterSubReg &R1, bool Zeros,
      bool Ones, const CellMap &Inputs, LatticeCell &Result) { … }

bool MachineConstEvaluator::evaluateCTBi(const APInt &A1, bool Zeros,
      bool Ones, APInt &Result) { … }

bool MachineConstEvaluator::evaluateEXTRACTr(const RegisterSubReg &R1,
      unsigned Width, unsigned Bits, unsigned Offset, bool Signed,
      const CellMap &Inputs, LatticeCell &Result) { … }

bool MachineConstEvaluator::evaluateEXTRACTi(const APInt &A1, unsigned Bits,
      unsigned Offset, bool Signed, APInt &Result) { … }

bool MachineConstEvaluator::evaluateSplatr(const RegisterSubReg &R1,
      unsigned Bits, unsigned Count, const CellMap &Inputs,
      LatticeCell &Result) { … }

bool MachineConstEvaluator::evaluateSplati(const APInt &A1, unsigned Bits,
      unsigned Count, APInt &Result) { … }

// ----------------------------------------------------------------------
// Hexagon-specific code.

namespace llvm {

  FunctionPass *createHexagonConstPropagationPass();
  void initializeHexagonConstPropagationPass(PassRegistry &Registry);

} // end namespace llvm

namespace {

  class HexagonConstEvaluator : public MachineConstEvaluator { … };

  class HexagonConstPropagation : public MachineFunctionPass { … };

} // end anonymous namespace

char HexagonConstPropagation::ID = …;

INITIALIZE_PASS(…)

HexagonConstEvaluator::HexagonConstEvaluator(MachineFunction &Fn)
  : … { … }

bool HexagonConstEvaluator::evaluate(const MachineInstr &MI,
      const CellMap &Inputs, CellMap &Outputs) { … }

bool HexagonConstEvaluator::evaluate(const RegisterSubReg &R,
      const LatticeCell &Input, LatticeCell &Result) { … }

bool HexagonConstEvaluator::evaluate(const MachineInstr &BrI,
      const CellMap &Inputs, SetVector<const MachineBasicBlock*> &Targets,
      bool &FallsThru) { … }

bool HexagonConstEvaluator::rewrite(MachineInstr &MI, const CellMap &Inputs) { … }

unsigned HexagonConstEvaluator::getRegBitWidth(unsigned Reg) const { … }

uint32_t HexagonConstEvaluator::getCmp(unsigned Opc) { … }

APInt HexagonConstEvaluator::getCmpImm(unsigned Opc, unsigned OpX,
      const MachineOperand &MO) { … }

void HexagonConstEvaluator::replaceWithNop(MachineInstr &MI) { … }

bool HexagonConstEvaluator::evaluateHexRSEQ32(RegisterSubReg RL, RegisterSubReg RH,
      const CellMap &Inputs, LatticeCell &Result) { … }

bool HexagonConstEvaluator::evaluateHexCompare(const MachineInstr &MI,
      const CellMap &Inputs, CellMap &Outputs) { … }

bool HexagonConstEvaluator::evaluateHexCompare2(unsigned Opc,
      const MachineOperand &Src1, const MachineOperand &Src2,
      const CellMap &Inputs, bool &Result) { … }

bool HexagonConstEvaluator::evaluateHexLogical(const MachineInstr &MI,
      const CellMap &Inputs, CellMap &Outputs) { … }

bool HexagonConstEvaluator::evaluateHexCondMove(const MachineInstr &MI,
      const CellMap &Inputs, CellMap &Outputs) { … }

bool HexagonConstEvaluator::evaluateHexExt(const MachineInstr &MI,
      const CellMap &Inputs, CellMap &Outputs) { … }

bool HexagonConstEvaluator::evaluateHexVector1(const MachineInstr &MI,
      const CellMap &Inputs, CellMap &Outputs) { … }

bool HexagonConstEvaluator::rewriteHexConstDefs(MachineInstr &MI,
      const CellMap &Inputs, bool &AllDefs) { … }

bool HexagonConstEvaluator::rewriteHexConstUses(MachineInstr &MI,
      const CellMap &Inputs) { … }

void HexagonConstEvaluator::replaceAllRegUsesWith(Register FromReg,
                                                  Register ToReg) { … }

bool HexagonConstEvaluator::rewriteHexBranch(MachineInstr &BrI,
      const CellMap &Inputs) { … }

FunctionPass *llvm::createHexagonConstPropagationPass() { … }
llvm/llvm/lib/Target/Hexagon/HexagonConstPropagation.cpp
