RDFLiveness.cpp | Explore in Territory

//===- RDFLiveness.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
//
//===----------------------------------------------------------------------===//
//
// Computation of the liveness information from the data-flow graph.
//
// The main functionality of this code is to compute block live-in
// information. With the live-in information in place, the placement
// of kill flags can also be recalculated.
//
// The block live-in calculation is based on the ideas from the following
// publication:
//
// Dibyendu Das, Ramakrishna Upadrasta, Benoit Dupont de Dinechin.
// "Efficient Liveness Computation Using Merge Sets and DJ-Graphs."
// ACM Transactions on Architecture and Code Optimization, Association for
// Computing Machinery, 2012, ACM TACO Special Issue on "High-Performance
// and Embedded Architectures and Compilers", 8 (4),
// <10.1145/2086696.2086706>. <hal-00647369>
//
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallSet.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/RDFGraph.h"
#include "llvm/CodeGen/RDFLiveness.h"
#include "llvm/CodeGen/RDFRegisters.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/MC/LaneBitmask.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <map>
#include <unordered_map>
#include <utility>
#include <vector>

usingnamespacellvm;

static cl::opt<unsigned> MaxRecNest("rdf-liveness-max-rec", cl::init(25),
                                    cl::Hidden,
                                    cl::desc("Maximum recursion level"));

namespace llvm::rdf {

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

// The order in the returned sequence is the order of reaching defs in the
// upward traversal: the first def is the closest to the given reference RefA,
// the next one is further up, and so on.
// The list ends at a reaching phi def, or when the reference from RefA is
// covered by the defs in the list (see FullChain).
// This function provides two modes of operation:
// (1) Returning the sequence of reaching defs for a particular reference
// node. This sequence will terminate at the first phi node [1].
// (2) Returning a partial sequence of reaching defs, where the final goal
// is to traverse past phi nodes to the actual defs arising from the code
// itself.
// In mode (2), the register reference for which the search was started
// may be different from the reference node RefA, for which this call was
// made, hence the argument RefRR, which holds the original register.
// Also, some definitions may have already been encountered in a previous
// call that will influence register covering. The register references
// already defined are passed in through DefRRs.
// In mode (1), the "continuation" considerations do not apply, and the
// RefRR is the same as the register in RefA, and the set DefRRs is empty.
//
// [1] It is possible for multiple phi nodes to be included in the returned
// sequence:
//   SubA = phi ...
//   SubB = phi ...
//   ...  = SuperAB(rdef:SubA), SuperAB"(rdef:SubB)
// However, these phi nodes are independent from one another in terms of
// the data-flow.

NodeList Liveness::getAllReachingDefs(RegisterRef RefRR,
                                      NodeAddr<RefNode *> RefA, bool TopShadows,
                                      bool FullChain,
                                      const RegisterAggr &DefRRs) { … }

std::pair<NodeSet, bool>
Liveness::getAllReachingDefsRec(RegisterRef RefRR, NodeAddr<RefNode *> RefA,
                                NodeSet &Visited, const NodeSet &Defs) { … }

std::pair<NodeSet, bool>
Liveness::getAllReachingDefsRecImpl(RegisterRef RefRR, NodeAddr<RefNode *> RefA,
                                    NodeSet &Visited, const NodeSet &Defs,
                                    unsigned Nest, unsigned MaxNest) { … }

/// Find the nearest ref node aliased to RefRR, going upwards in the data
/// flow, starting from the instruction immediately preceding Inst.
NodeAddr<RefNode *> Liveness::getNearestAliasedRef(RegisterRef RefRR,
                                                   NodeAddr<InstrNode *> IA) { … }

NodeSet Liveness::getAllReachedUses(RegisterRef RefRR, NodeAddr<DefNode *> DefA,
                                    const RegisterAggr &DefRRs) { … }

void Liveness::computePhiInfo() { … }

void Liveness::computeLiveIns() { … }

void Liveness::resetLiveIns() { … }

void Liveness::resetKills() { … }

void Liveness::resetKills(MachineBasicBlock *B) { … }

// Helper function to obtain the basic block containing the reaching def
// of the given use.
MachineBasicBlock *Liveness::getBlockWithRef(NodeId RN) const { … }

void Liveness::traverse(MachineBasicBlock *B, RefMap &LiveIn) { … }

void Liveness::emptify(RefMap &M) { … }

} // namespace llvm::rdf
llvm/llvm/lib/CodeGen/RDFLiveness.cpp
