llvm/llvm/lib/CodeGen/ScheduleDAG.cpp

//===- ScheduleDAG.cpp - Implement the ScheduleDAG class ------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
/// \file Implements the ScheduleDAG class, which is a base class used by
/// scheduling implementation classes.
//
//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
#include "llvm/CodeGen/SelectionDAGNodes.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <limits>
#include <utility>
#include <vector>

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumNewPredsAdded, "Number of times a  single predecessor was added");
STATISTIC(NumTopoInits,
          "Number of times the topological order has been recomputed");

#ifndef NDEBUG
static cl::opt<bool> StressSchedOpt(
  "stress-sched", cl::Hidden, cl::init(false),
  cl::desc("Stress test instruction scheduling"));
#endif

void SchedulingPriorityQueue::anchor() { … }

ScheduleDAG::ScheduleDAG(MachineFunction &mf)
    : … { … }

ScheduleDAG::~ScheduleDAG() = default;

void ScheduleDAG::clearDAG() { … }

const MCInstrDesc *ScheduleDAG::getNodeDesc(const SDNode *Node) const { … }

LLVM_DUMP_METHOD void SDep::dump(const TargetRegisterInfo *TRI) const { … }

bool SUnit::addPred(const SDep &D, bool Required) { … }

void SUnit::removePred(const SDep &D) { … }

void SUnit::setDepthDirty() { … }

void SUnit::setHeightDirty() { … }

void SUnit::setDepthToAtLeast(unsigned NewDepth) { … }

void SUnit::setHeightToAtLeast(unsigned NewHeight) { … }

/// Calculates the maximal path from the node to the exit.
void SUnit::ComputeDepth() { … }

/// Calculates the maximal path from the node to the entry.
void SUnit::ComputeHeight() { … }

void SUnit::biasCriticalPath() { … }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void SUnit::dumpAttributes() const {
  dbgs() << "  # preds left       : " << NumPredsLeft << "\n";
  dbgs() << "  # succs left       : " << NumSuccsLeft << "\n";
  if (WeakPredsLeft)
    dbgs() << "  # weak preds left  : " << WeakPredsLeft << "\n";
  if (WeakSuccsLeft)
    dbgs() << "  # weak succs left  : " << WeakSuccsLeft << "\n";
  dbgs() << "  # rdefs left       : " << NumRegDefsLeft << "\n";
  dbgs() << "  Latency            : " << Latency << "\n";
  dbgs() << "  Depth              : " << getDepth() << "\n";
  dbgs() << "  Height             : " << getHeight() << "\n";
}

LLVM_DUMP_METHOD void ScheduleDAG::dumpNodeName(const SUnit &SU) const {
  if (&SU == &EntrySU)
    dbgs() << "EntrySU";
  else if (&SU == &ExitSU)
    dbgs() << "ExitSU";
  else
    dbgs() << "SU(" << SU.NodeNum << ")";
}

LLVM_DUMP_METHOD void ScheduleDAG::dumpNodeAll(const SUnit &SU) const {
  dumpNode(SU);
  SU.dumpAttributes();
  if (SU.Preds.size() > 0) {
    dbgs() << "  Predecessors:\n";
    for (const SDep &Dep : SU.Preds) {
      dbgs() << "    ";
      dumpNodeName(*Dep.getSUnit());
      dbgs() << ": ";
      Dep.dump(TRI);
      dbgs() << '\n';
    }
  }
  if (SU.Succs.size() > 0) {
    dbgs() << "  Successors:\n";
    for (const SDep &Dep : SU.Succs) {
      dbgs() << "    ";
      dumpNodeName(*Dep.getSUnit());
      dbgs() << ": ";
      Dep.dump(TRI);
      dbgs() << '\n';
    }
  }
}
#endif

#ifndef NDEBUG
unsigned ScheduleDAG::VerifyScheduledDAG(bool isBottomUp) {
  bool AnyNotSched = false;
  unsigned DeadNodes = 0;
  for (const SUnit &SUnit : SUnits) {
    if (!SUnit.isScheduled) {
      if (SUnit.NumPreds == 0 && SUnit.NumSuccs == 0) {
        ++DeadNodes;
        continue;
      }
      if (!AnyNotSched)
        dbgs() << "*** Scheduling failed! ***\n";
      dumpNode(SUnit);
      dbgs() << "has not been scheduled!\n";
      AnyNotSched = true;
    }
    if (SUnit.isScheduled &&
        (isBottomUp ? SUnit.getHeight() : SUnit.getDepth()) >
          unsigned(std::numeric_limits<int>::max())) {
      if (!AnyNotSched)
        dbgs() << "*** Scheduling failed! ***\n";
      dumpNode(SUnit);
      dbgs() << "has an unexpected "
           << (isBottomUp ? "Height" : "Depth") << " value!\n";
      AnyNotSched = true;
    }
    if (isBottomUp) {
      if (SUnit.NumSuccsLeft != 0) {
        if (!AnyNotSched)
          dbgs() << "*** Scheduling failed! ***\n";
        dumpNode(SUnit);
        dbgs() << "has successors left!\n";
        AnyNotSched = true;
      }
    } else {
      if (SUnit.NumPredsLeft != 0) {
        if (!AnyNotSched)
          dbgs() << "*** Scheduling failed! ***\n";
        dumpNode(SUnit);
        dbgs() << "has predecessors left!\n";
        AnyNotSched = true;
      }
    }
  }
  assert(!AnyNotSched);
  return SUnits.size() - DeadNodes;
}
#endif

void ScheduleDAGTopologicalSort::InitDAGTopologicalSorting() { … }

void ScheduleDAGTopologicalSort::FixOrder() { … }

void ScheduleDAGTopologicalSort::AddPredQueued(SUnit *Y, SUnit *X) { … }

void ScheduleDAGTopologicalSort::AddPred(SUnit *Y, SUnit *X) { … }

void ScheduleDAGTopologicalSort::RemovePred(SUnit *M, SUnit *N) { … }

void ScheduleDAGTopologicalSort::DFS(const SUnit *SU, int UpperBound,
                                     bool &HasLoop) { … }

std::vector<int> ScheduleDAGTopologicalSort::GetSubGraph(const SUnit &StartSU,
                                                         const SUnit &TargetSU,
                                                         bool &Success) { … }

void ScheduleDAGTopologicalSort::Shift(BitVector& Visited, int LowerBound,
                                       int UpperBound) { … }

bool ScheduleDAGTopologicalSort::WillCreateCycle(SUnit *TargetSU, SUnit *SU) { … }

void ScheduleDAGTopologicalSort::AddSUnitWithoutPredecessors(const SUnit *SU) { … }

bool ScheduleDAGTopologicalSort::IsReachable(const SUnit *SU,
                                             const SUnit *TargetSU) { … }

void ScheduleDAGTopologicalSort::Allocate(int n, int index) { … }

ScheduleDAGTopologicalSort::
ScheduleDAGTopologicalSort(std::vector<SUnit> &sunits, SUnit *exitsu)
  : … { … }

ScheduleHazardRecognizer::~ScheduleHazardRecognizer() = default;