RDFGraph.cpp | Explore in Territory

//===- RDFGraph.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
//
//===----------------------------------------------------------------------===//
//
// Target-independent, SSA-based data flow graph for register data flow (RDF).
//
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineDominanceFrontier.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/RDFGraph.h"
#include "llvm/CodeGen/RDFRegisters.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetLowering.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/IR/Function.h"
#include "llvm/MC/LaneBitmask.h"
#include "llvm/MC/MCInstrDesc.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <cstring>
#include <iterator>
#include <set>
#include <utility>
#include <vector>

// Printing functions. Have them here first, so that the rest of the code
// can use them.
namespace llvm::rdf {

raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterRef> &P) { … }

raw_ostream &operator<<(raw_ostream &OS, const Print<NodeId> &P) { … }

static void printRefHeader(raw_ostream &OS, const Ref RA,
                           const DataFlowGraph &G) { … }

raw_ostream &operator<<(raw_ostream &OS, const Print<Def> &P) { … }

raw_ostream &operator<<(raw_ostream &OS, const Print<Use> &P) { … }

raw_ostream &operator<<(raw_ostream &OS, const Print<PhiUse> &P) { … }

raw_ostream &operator<<(raw_ostream &OS, const Print<Ref> &P) { … }

raw_ostream &operator<<(raw_ostream &OS, const Print<NodeList> &P) { … }

raw_ostream &operator<<(raw_ostream &OS, const Print<NodeSet> &P) { … }

namespace {

template <typename T> struct PrintListV { … };

template <typename T>
raw_ostream &operator<<(raw_ostream &OS, const PrintListV<T> &P) { … }

} // end anonymous namespace

raw_ostream &operator<<(raw_ostream &OS, const Print<Phi> &P) { … }

raw_ostream &operator<<(raw_ostream &OS, const Print<Stmt> &P) { … }

raw_ostream &operator<<(raw_ostream &OS, const Print<Instr> &P) { … }

raw_ostream &operator<<(raw_ostream &OS, const Print<Block> &P) { … }

raw_ostream &operator<<(raw_ostream &OS, const Print<Func> &P) { … }

raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterSet> &P) { … }

raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterAggr> &P) { … }

raw_ostream &operator<<(raw_ostream &OS,
                        const Print<DataFlowGraph::DefStack> &P) { … }

// Node allocation functions.
//
// Node allocator is like a slab memory allocator: it allocates blocks of
// memory in sizes that are multiples of the size of a node. Each block has
// the same size. Nodes are allocated from the currently active block, and
// when it becomes full, a new one is created.
// There is a mapping scheme between node id and its location in a block,
// and within that block is described in the header file.
//
void NodeAllocator::startNewBlock() { … }

bool NodeAllocator::needNewBlock() { … }

Node NodeAllocator::New() { … }

NodeId NodeAllocator::id(const NodeBase *P) const { … }

void NodeAllocator::clear() { … }

// Insert node NA after "this" in the circular chain.
void NodeBase::append(Node NA) { … }

// Fundamental node manipulator functions.

// Obtain the register reference from a reference node.
RegisterRef RefNode::getRegRef(const DataFlowGraph &G) const { … }

// Set the register reference in the reference node directly (for references
// in phi nodes).
void RefNode::setRegRef(RegisterRef RR, DataFlowGraph &G) { … }

// Set the register reference in the reference node based on a machine
// operand (for references in statement nodes).
void RefNode::setRegRef(MachineOperand *Op, DataFlowGraph &G) { … }

// Get the owner of a given reference node.
Node RefNode::getOwner(const DataFlowGraph &G) { … }

// Connect the def node to the reaching def node.
void DefNode::linkToDef(NodeId Self, Def DA) { … }

// Connect the use node to the reaching def node.
void UseNode::linkToDef(NodeId Self, Def DA) { … }

// Get the first member of the code node.
Node CodeNode::getFirstMember(const DataFlowGraph &G) const { … }

// Get the last member of the code node.
Node CodeNode::getLastMember(const DataFlowGraph &G) const { … }

// Add node NA at the end of the member list of the given code node.
void CodeNode::addMember(Node NA, const DataFlowGraph &G) { … }

// Add node NA after member node MA in the given code node.
void CodeNode::addMemberAfter(Node MA, Node NA, const DataFlowGraph &G) { … }

// Remove member node NA from the given code node.
void CodeNode::removeMember(Node NA, const DataFlowGraph &G) { … }

// Return the list of all members of the code node.
NodeList CodeNode::members(const DataFlowGraph &G) const { … }

// Return the owner of the given instr node.
Node InstrNode::getOwner(const DataFlowGraph &G) { … }

// Add the phi node PA to the given block node.
void BlockNode::addPhi(Phi PA, const DataFlowGraph &G) { … }

// Find the block node corresponding to the machine basic block BB in the
// given func node.
Block FuncNode::findBlock(const MachineBasicBlock *BB,
                          const DataFlowGraph &G) const { … }

// Get the block node for the entry block in the given function.
Block FuncNode::getEntryBlock(const DataFlowGraph &G) { … }

// Target operand information.
//

// For a given instruction, check if there are any bits of RR that can remain
// unchanged across this def.
bool TargetOperandInfo::isPreserving(const MachineInstr &In,
                                     unsigned OpNum) const { … }

// Check if the definition of RR produces an unspecified value.
bool TargetOperandInfo::isClobbering(const MachineInstr &In,
                                     unsigned OpNum) const { … }

// Check if the given instruction specifically requires
bool TargetOperandInfo::isFixedReg(const MachineInstr &In,
                                   unsigned OpNum) const { … }

//
// The data flow graph construction.
//

DataFlowGraph::DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii,
                             const TargetRegisterInfo &tri,
                             const MachineDominatorTree &mdt,
                             const MachineDominanceFrontier &mdf)
    : … { … }

DataFlowGraph::DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii,
                             const TargetRegisterInfo &tri,
                             const MachineDominatorTree &mdt,
                             const MachineDominanceFrontier &mdf,
                             const TargetOperandInfo &toi)
    : … { … }

// The implementation of the definition stack.
// Each register reference has its own definition stack. In particular,
// for a register references "Reg" and "Reg:subreg" will each have their
// own definition stacks.

// Construct a stack iterator.
DataFlowGraph::DefStack::Iterator::Iterator(const DataFlowGraph::DefStack &S,
                                            bool Top)
    : … { … }

// Return the size of the stack, including block delimiters.
unsigned DataFlowGraph::DefStack::size() const { … }

// Remove the top entry from the stack. Remove all intervening delimiters
// so that after this, the stack is either empty, or the top of the stack
// is a non-delimiter.
void DataFlowGraph::DefStack::pop() { … }

// Push a delimiter for block node N on the stack.
void DataFlowGraph::DefStack::start_block(NodeId N) { … }

// Remove all nodes from the top of the stack, until the delimited for
// block node N is encountered. Remove the delimiter as well. In effect,
// this will remove from the stack all definitions from block N.
void DataFlowGraph::DefStack::clear_block(NodeId N) { … }

// Move the stack iterator up by one.
unsigned DataFlowGraph::DefStack::nextUp(unsigned P) const { … }

// Move the stack iterator down by one.
unsigned DataFlowGraph::DefStack::nextDown(unsigned P) const { … }

// Register information.

RegisterAggr DataFlowGraph::getLandingPadLiveIns() const { … }

// Node management functions.

// Get the pointer to the node with the id N.
NodeBase *DataFlowGraph::ptr(NodeId N) const { … }

// Get the id of the node at the address P.
NodeId DataFlowGraph::id(const NodeBase *P) const { … }

// Allocate a new node and set the attributes to Attrs.
Node DataFlowGraph::newNode(uint16_t Attrs) { … }

// Make a copy of the given node B, except for the data-flow links, which
// are set to 0.
Node DataFlowGraph::cloneNode(const Node B) { … }

// Allocation routines for specific node types/kinds.

Use DataFlowGraph::newUse(Instr Owner, MachineOperand &Op, uint16_t Flags) { … }

PhiUse DataFlowGraph::newPhiUse(Phi Owner, RegisterRef RR, Block PredB,
                                uint16_t Flags) { … }

Def DataFlowGraph::newDef(Instr Owner, MachineOperand &Op, uint16_t Flags) { … }

Def DataFlowGraph::newDef(Instr Owner, RegisterRef RR, uint16_t Flags) { … }

Phi DataFlowGraph::newPhi(Block Owner) { … }

Stmt DataFlowGraph::newStmt(Block Owner, MachineInstr *MI) { … }

Block DataFlowGraph::newBlock(Func Owner, MachineBasicBlock *BB) { … }

Func DataFlowGraph::newFunc(MachineFunction *MF) { … }

// Build the data flow graph.
void DataFlowGraph::build(const Config &config) { … }

RegisterRef DataFlowGraph::makeRegRef(unsigned Reg, unsigned Sub) const { … }

RegisterRef DataFlowGraph::makeRegRef(const MachineOperand &Op) const { … }

// For each stack in the map DefM, push the delimiter for block B on it.
void DataFlowGraph::markBlock(NodeId B, DefStackMap &DefM) { … }

// Remove all definitions coming from block B from each stack in DefM.
void DataFlowGraph::releaseBlock(NodeId B, DefStackMap &DefM) { … }

// Push all definitions from the instruction node IA to an appropriate
// stack in DefM.
void DataFlowGraph::pushAllDefs(Instr IA, DefStackMap &DefM) { … }

// Push all definitions from the instruction node IA to an appropriate
// stack in DefM.
void DataFlowGraph::pushClobbers(Instr IA, DefStackMap &DefM) { … }

// Push all definitions from the instruction node IA to an appropriate
// stack in DefM.
void DataFlowGraph::pushDefs(Instr IA, DefStackMap &DefM) { … }

// Return the list of all reference nodes related to RA, including RA itself.
// See "getNextRelated" for the meaning of a "related reference".
NodeList DataFlowGraph::getRelatedRefs(Instr IA, Ref RA) const { … }

// Clear all information in the graph.
void DataFlowGraph::reset() { … }

// Return the next reference node in the instruction node IA that is related
// to RA. Conceptually, two reference nodes are related if they refer to the
// same instance of a register access, but differ in flags or other minor
// characteristics. Specific examples of related nodes are shadow reference
// nodes.
// Return the equivalent of nullptr if there are no more related references.
Ref DataFlowGraph::getNextRelated(Instr IA, Ref RA) const { … }

// Find the next node related to RA in IA that satisfies condition P.
// If such a node was found, return a pair where the second element is the
// located node. If such a node does not exist, return a pair where the
// first element is the element after which such a node should be inserted,
// and the second element is a null-address.
template <typename Predicate>
std::pair<Ref, Ref> DataFlowGraph::locateNextRef(Instr IA, Ref RA,
                                                 Predicate P) const { … }

// Get the next shadow node in IA corresponding to RA, and optionally create
// such a node if it does not exist.
Ref DataFlowGraph::getNextShadow(Instr IA, Ref RA, bool Create) { … }

// Create a new statement node in the block node BA that corresponds to
// the machine instruction MI.
void DataFlowGraph::buildStmt(Block BA, MachineInstr &In) { … }

// Scan all defs in the block node BA and record in PhiM the locations of
// phi nodes corresponding to these defs.
void DataFlowGraph::recordDefsForDF(BlockRefsMap &PhiM, Block BA) { … }

// Given the locations of phi nodes in the map PhiM, create the phi nodes
// that are located in the block node BA.
void DataFlowGraph::buildPhis(BlockRefsMap &PhiM, Block BA) { … }

// Remove any unneeded phi nodes that were created during the build process.
void DataFlowGraph::removeUnusedPhis() { … }

// For a given reference node TA in an instruction node IA, connect the
// reaching def of TA to the appropriate def node. Create any shadow nodes
// as appropriate.
template <typename T>
void DataFlowGraph::linkRefUp(Instr IA, NodeAddr<T> TA, DefStack &DS) { … }

// Create data-flow links for all reference nodes in the statement node SA.
template <typename Predicate>
void DataFlowGraph::linkStmtRefs(DefStackMap &DefM, Stmt SA, Predicate P) { … }

// Create data-flow links for all instructions in the block node BA. This
// will include updating any phi nodes in BA.
void DataFlowGraph::linkBlockRefs(DefStackMap &DefM, Block BA) { … }

// Remove the use node UA from any data-flow and structural links.
void DataFlowGraph::unlinkUseDF(Use UA) { … }

// Remove the def node DA from any data-flow and structural links.
void DataFlowGraph::unlinkDefDF(Def DA) { … }

bool DataFlowGraph::isTracked(RegisterRef RR) const { … }

bool DataFlowGraph::hasUntrackedRef(Stmt S, bool IgnoreReserved) const { … }

} // end namespace llvm::rdf
llvm/llvm/lib/CodeGen/RDFGraph.cpp
