//===- LiveRegMatrix.cpp - Track register interference --------------------===//
//
// 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 file defines the LiveRegMatrix analysis pass.
//
//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/LiveRegMatrix.h"
#include "RegisterCoalescer.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/LiveInterval.h"
#include "llvm/CodeGen/LiveIntervalUnion.h"
#include "llvm/CodeGen/LiveIntervals.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/CodeGen/VirtRegMap.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/LaneBitmask.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>

using namespace llvm;

#define DEBUG_TYPE "regalloc"

STATISTIC(NumAssigned   , "Number of registers assigned");
STATISTIC(NumUnassigned , "Number of registers unassigned");

char LiveRegMatrix::ID = 0;
INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix",
                      "Live Register Matrix", false, false)
INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
INITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix",
                    "Live Register Matrix", false, false)

LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID) {}

void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const {
  AU.setPreservesAll();
  AU.addRequiredTransitive<LiveIntervals>();
  AU.addRequiredTransitive<VirtRegMap>();
  MachineFunctionPass::getAnalysisUsage(AU);
}

bool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) {
  TRI = MF.getSubtarget().getRegisterInfo();
  LIS = &getAnalysis<LiveIntervals>();
  VRM = &getAnalysis<VirtRegMap>();

  unsigned NumRegUnits = TRI->getNumRegUnits();
  if (NumRegUnits != Matrix.size())
    Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]);
  Matrix.init(LIUAlloc, NumRegUnits);

  // Make sure no stale queries get reused.
  invalidateVirtRegs();
  return false;
}

void LiveRegMatrix::releaseMemory() {
  for (unsigned i = 0, e = Matrix.size(); i != e; ++i) {
    Matrix[i].clear();
    // No need to clear Queries here, since LiveIntervalUnion::Query doesn't
    // have anything important to clear and LiveRegMatrix's runOnFunction()
    // does a std::unique_ptr::reset anyways.
  }
}

template <typename Callable>
static bool foreachUnit(const TargetRegisterInfo *TRI,
                        const LiveInterval &VRegInterval, MCRegister PhysReg,
                        Callable Func) {
  if (VRegInterval.hasSubRanges()) {
    for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
      unsigned Unit = (*Units).first;
      LaneBitmask Mask = (*Units).second;
      for (const LiveInterval::SubRange &S : VRegInterval.subranges()) {
        if ((S.LaneMask & Mask).any()) {
          if (Func(Unit, S))
            return true;
          break;
        }
      }
    }
  } else {
    for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
      if (Func(*Units, VRegInterval))
        return true;
    }
  }
  return false;
}

void LiveRegMatrix::assign(const LiveInterval &VirtReg, MCRegister PhysReg) {
  LLVM_DEBUG(dbgs() << "assigning " << printReg(VirtReg.reg(), TRI) << " to "
                    << printReg(PhysReg, TRI) << ':');
  assert(!VRM->hasPhys(VirtReg.reg()) && "Duplicate VirtReg assignment");
  VRM->assignVirt2Phys(VirtReg.reg(), PhysReg);

  foreachUnit(
      TRI, VirtReg, PhysReg, [&](unsigned Unit, const LiveRange &Range) {
        LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << ' ' << Range);
        Matrix[Unit].unify(VirtReg, Range);
        return false;
      });

  ++NumAssigned;
  LLVM_DEBUG(dbgs() << '\n');
}

void LiveRegMatrix::unassign(const LiveInterval &VirtReg) {
  Register PhysReg = VRM->getPhys(VirtReg.reg());
  LLVM_DEBUG(dbgs() << "unassigning " << printReg(VirtReg.reg(), TRI)
                    << " from " << printReg(PhysReg, TRI) << ':');
  VRM->clearVirt(VirtReg.reg());

  foreachUnit(TRI, VirtReg, PhysReg,
              [&](unsigned Unit, const LiveRange &Range) {
                LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI));
                Matrix[Unit].extract(VirtReg, Range);
                return false;
              });

  ++NumUnassigned;
  LLVM_DEBUG(dbgs() << '\n');
}

bool LiveRegMatrix::isPhysRegUsed(MCRegister PhysReg) const {
  for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
    if (!Matrix[*Unit].empty())
      return true;
  }
  return false;
}

bool LiveRegMatrix::checkRegMaskInterference(const LiveInterval &VirtReg,
                                             MCRegister PhysReg) {
  // Check if the cached information is valid.
  // The same BitVector can be reused for all PhysRegs.
  // We could cache multiple VirtRegs if it becomes necessary.
  if (RegMaskVirtReg != VirtReg.reg() || RegMaskTag != UserTag) {
    RegMaskVirtReg = VirtReg.reg();
    RegMaskTag = UserTag;
    RegMaskUsable.clear();
    LIS->checkRegMaskInterference(VirtReg, RegMaskUsable);
  }

  // The BitVector is indexed by PhysReg, not register unit.
  // Regmask interference is more fine grained than regunits.
  // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8.
  return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg));
}

bool LiveRegMatrix::checkRegUnitInterference(const LiveInterval &VirtReg,
                                             MCRegister PhysReg) {
  if (VirtReg.empty())
    return false;
  CoalescerPair CP(VirtReg.reg(), PhysReg, *TRI);

  bool Result = foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
                                                       const LiveRange &Range) {
    const LiveRange &UnitRange = LIS->getRegUnit(Unit);
    return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes());
  });
  return Result;
}

LiveIntervalUnion::Query &LiveRegMatrix::query(const LiveRange &LR,
                                               MCRegister RegUnit) {
  LiveIntervalUnion::Query &Q = Queries[RegUnit];
  Q.init(UserTag, LR, Matrix[RegUnit]);
  return Q;
}

LiveRegMatrix::InterferenceKind
LiveRegMatrix::checkInterference(const LiveInterval &VirtReg,
                                 MCRegister PhysReg) {
  if (VirtReg.empty())
    return IK_Free;

  // Regmask interference is the fastest check.
  if (checkRegMaskInterference(VirtReg, PhysReg))
    return IK_RegMask;

  // Check for fixed interference.
  if (checkRegUnitInterference(VirtReg, PhysReg))
    return IK_RegUnit;

  // Check the matrix for virtual register interference.
  bool Interference = foreachUnit(TRI, VirtReg, PhysReg,
                                  [&](MCRegister Unit, const LiveRange &LR) {
                                    return query(LR, Unit).checkInterference();
                                  });
  if (Interference)
    return IK_VirtReg;

  return IK_Free;
}

bool LiveRegMatrix::checkInterference(SlotIndex Start, SlotIndex End,
                                      MCRegister PhysReg) {
  // Construct artificial live range containing only one segment [Start, End).
  VNInfo valno(0, Start);
  LiveRange::Segment Seg(Start, End, &valno);
  LiveRange LR;
  LR.addSegment(Seg);

  // Check for interference with that segment
  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
    // LR is stack-allocated. LiveRegMatrix caches queries by a key that
    // includes the address of the live range. If (for the same reg unit) this
    // checkInterference overload is called twice, without any other query()
    // calls in between (on heap-allocated LiveRanges)  - which would invalidate
    // the cached query - the LR address seen the second time may well be the
    // same as that seen the first time, while the Start/End/valno may not - yet
    // the same cached result would be fetched. To avoid that, we don't cache
    // this query.
    //
    // FIXME: the usability of the Query API needs to be improved to avoid
    // subtle bugs due to query identity. Avoiding caching, for example, would
    // greatly simplify things.
    LiveIntervalUnion::Query Q;
    Q.reset(UserTag, LR, Matrix[*Units]);
    if (Q.checkInterference())
      return true;
  }
  return false;
}

Register LiveRegMatrix::getOneVReg(unsigned PhysReg) const {
  const LiveInterval *VRegInterval = nullptr;
  for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
    if ((VRegInterval = Matrix[*Unit].getOneVReg()))
      return VRegInterval->reg();
  }

  return MCRegister::NoRegister;
}