ScheduleDAGInstrs.cpp | Explore in Territory

//===---- ScheduleDAGInstrs.cpp - MachineInstr Rescheduling ---------------===//
//
// 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 This implements the ScheduleDAGInstrs class, which implements
/// re-scheduling of MachineInstrs.
//
//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/ScheduleDAGInstrs.h"

#include "llvm/ADT/IntEqClasses.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/SparseSet.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/CodeGen/LiveIntervals.h"
#include "llvm/CodeGen/LivePhysRegs.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBundle.h"
#include "llvm/CodeGen/MachineMemOperand.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/PseudoSourceValue.h"
#include "llvm/CodeGen/RegisterPressure.h"
#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/CodeGen/ScheduleDFS.h"
#include "llvm/CodeGen/SlotIndexes.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/MC/LaneBitmask.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/Format.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <utility>
#include <vector>

usingnamespacellvm;

#define DEBUG_TYPE …

static cl::opt<bool>
    EnableAASchedMI("enable-aa-sched-mi", cl::Hidden,
                    cl::desc("Enable use of AA during MI DAG construction"));

static cl::opt<bool> UseTBAA("use-tbaa-in-sched-mi", cl::Hidden,
    cl::init(true), cl::desc("Enable use of TBAA during MI DAG construction"));

// Note: the two options below might be used in tuning compile time vs
// output quality. Setting HugeRegion so large that it will never be
// reached means best-effort, but may be slow.

// When Stores and Loads maps (or NonAliasStores and NonAliasLoads)
// together hold this many SUs, a reduction of maps will be done.
static cl::opt<unsigned> HugeRegion("dag-maps-huge-region", cl::Hidden,
    cl::init(1000), cl::desc("The limit to use while constructing the DAG "
                             "prior to scheduling, at which point a trade-off "
                             "is made to avoid excessive compile time."));

static cl::opt<unsigned> ReductionSize(
    "dag-maps-reduction-size", cl::Hidden,
    cl::desc("A huge scheduling region will have maps reduced by this many "
             "nodes at a time. Defaults to HugeRegion / 2."));

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
static cl::opt<bool> SchedPrintCycles(
    "sched-print-cycles", cl::Hidden, cl::init(false),
    cl::desc("Report top/bottom cycles when dumping SUnit instances"));
#endif

static unsigned getReductionSize() { … }

static void dumpSUList(const ScheduleDAGInstrs::SUList &L) { … }

ScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf,
                                     const MachineLoopInfo *mli,
                                     bool RemoveKillFlags)
    : … { … }

/// If this machine instr has memory reference information and it can be
/// tracked to a normal reference to a known object, return the Value
/// for that object. This function returns false the memory location is
/// unknown or may alias anything.
static bool getUnderlyingObjectsForInstr(const MachineInstr *MI,
                                         const MachineFrameInfo &MFI,
                                         UnderlyingObjectsVector &Objects,
                                         const DataLayout &DL) { … }

void ScheduleDAGInstrs::startBlock(MachineBasicBlock *bb) { … }

void ScheduleDAGInstrs::finishBlock() { … }

void ScheduleDAGInstrs::enterRegion(MachineBasicBlock *bb,
                                    MachineBasicBlock::iterator begin,
                                    MachineBasicBlock::iterator end,
                                    unsigned regioninstrs) { … }

void ScheduleDAGInstrs::exitRegion() { … }

void ScheduleDAGInstrs::addSchedBarrierDeps() { … }

/// MO is an operand of SU's instruction that defines a physical register. Adds
/// data dependencies from SU to any uses of the physical register.
void ScheduleDAGInstrs::addPhysRegDataDeps(SUnit *SU, unsigned OperIdx) { … }

/// Adds register dependencies (data, anti, and output) from this SUnit
/// to following instructions in the same scheduling region that depend the
/// physical register referenced at OperIdx.
void ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) { … }

LaneBitmask ScheduleDAGInstrs::getLaneMaskForMO(const MachineOperand &MO) const
{ … }

bool ScheduleDAGInstrs::deadDefHasNoUse(const MachineOperand &MO) { … }

/// Adds register output and data dependencies from this SUnit to instructions
/// that occur later in the same scheduling region if they read from or write to
/// the virtual register defined at OperIdx.
///
/// TODO: Hoist loop induction variable increments. This has to be
/// reevaluated. Generally, IV scheduling should be done before coalescing.
void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned OperIdx) { … }

/// Adds a register data dependency if the instruction that defines the
/// virtual register used at OperIdx is mapped to an SUnit. Add a register
/// antidependency from this SUnit to instructions that occur later in the same
/// scheduling region if they write the virtual register.
///
/// TODO: Handle ExitSU "uses" properly.
void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) { … }

/// Returns true if MI is an instruction we are unable to reason about
/// (like a call or something with unmodeled side effects).
static inline bool isGlobalMemoryObject(MachineInstr *MI) { … }

void ScheduleDAGInstrs::addChainDependency (SUnit *SUa, SUnit *SUb,
                                            unsigned Latency) { … }

/// Creates an SUnit for each real instruction, numbered in top-down
/// topological order. The instruction order A < B, implies that no edge exists
/// from B to A.
///
/// Map each real instruction to its SUnit.
///
/// After initSUnits, the SUnits vector cannot be resized and the scheduler may
/// hang onto SUnit pointers. We may relax this in the future by using SUnit IDs
/// instead of pointers.
///
/// MachineScheduler relies on initSUnits numbering the nodes by their order in
/// the original instruction list.
void ScheduleDAGInstrs::initSUnits() { … }

class ScheduleDAGInstrs::Value2SUsMap
    : public SmallMapVector<ValueType, SUList, 4> { … };

void ScheduleDAGInstrs::addChainDependencies(SUnit *SU,
                                             Value2SUsMap &Val2SUsMap) { … }

void ScheduleDAGInstrs::addChainDependencies(SUnit *SU,
                                             Value2SUsMap &Val2SUsMap,
                                             ValueType V) { … }

void ScheduleDAGInstrs::addBarrierChain(Value2SUsMap &map) { … }

void ScheduleDAGInstrs::insertBarrierChain(Value2SUsMap &map) { … }

void ScheduleDAGInstrs::buildSchedGraph(AAResults *AA,
                                        RegPressureTracker *RPTracker,
                                        PressureDiffs *PDiffs,
                                        LiveIntervals *LIS,
                                        bool TrackLaneMasks) { … }

raw_ostream &llvm::operator<<(raw_ostream &OS, const PseudoSourceValue* PSV) { … }

void ScheduleDAGInstrs::Value2SUsMap::dump() { … }

void ScheduleDAGInstrs::reduceHugeMemNodeMaps(Value2SUsMap &stores,
                                              Value2SUsMap &loads, unsigned N) { … }

static void toggleKills(const MachineRegisterInfo &MRI, LiveRegUnits &LiveRegs,
                        MachineInstr &MI, bool addToLiveRegs) { … }

void ScheduleDAGInstrs::fixupKills(MachineBasicBlock &MBB) { … }

void ScheduleDAGInstrs::dumpNode(const SUnit &SU) const { … }

void ScheduleDAGInstrs::dump() const { … }

std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const { … }

/// Return the basic block label. It is not necessarilly unique because a block
/// contains multiple scheduling regions. But it is fine for visualization.
std::string ScheduleDAGInstrs::getDAGName() const { … }

bool ScheduleDAGInstrs::canAddEdge(SUnit *SuccSU, SUnit *PredSU) { … }

bool ScheduleDAGInstrs::addEdge(SUnit *SuccSU, const SDep &PredDep) { … }

//===----------------------------------------------------------------------===//
// SchedDFSResult Implementation
//===----------------------------------------------------------------------===//

namespace llvm {

/// Internal state used to compute SchedDFSResult.
class SchedDFSImpl { … };

} // end namespace llvm

namespace {

/// Manage the stack used by a reverse depth-first search over the DAG.
class SchedDAGReverseDFS { … };

} // end anonymous namespace

static bool hasDataSucc(const SUnit *SU) { … }

/// Computes an ILP metric for all nodes in the subDAG reachable via depth-first
/// search from this root.
void SchedDFSResult::compute(ArrayRef<SUnit> SUnits) { … }

/// The root of the given SubtreeID was just scheduled. For all subtrees
/// connected to this tree, record the depth of the connection so that the
/// nearest connected subtrees can be prioritized.
void SchedDFSResult::scheduleTree(unsigned SubtreeID) { … }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void ILPValue::print(raw_ostream &OS) const {
  OS << InstrCount << " / " << Length << " = ";
  if (!Length)
    OS << "BADILP";
  else
    OS << format("%g", ((double)InstrCount / Length));
}

LLVM_DUMP_METHOD void ILPValue::dump() const {
  dbgs() << *this << '\n';
}

namespace llvm {

LLVM_ATTRIBUTE_UNUSED
raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val) {
  Val.print(OS);
  return OS;
}

} // end namespace llvm

#endif
llvm/llvm/lib/CodeGen/ScheduleDAGInstrs.cpp
