blob: 8f1ba7863e583eec10eed3ed4575b668f28dc49d [file] [log] [blame]
//===- subzero/src/IceLiveness.h - Liveness analysis ------------*- C++ -*-===//
// The Subzero Code Generator
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
/// \file
/// \brief Declares the Liveness and LivenessNode classes, which are used for
/// liveness analysis.
/// The node-specific information tracked for each Variable includes whether it
/// is live on entry, whether it is live on exit, the instruction number that
/// starts its live range, and the instruction number that ends its live range.
/// At the Cfg level, the actual live intervals are recorded.
#include "IceBitVector.h"
#include "IceCfgNode.h"
#include "IceDefs.h"
#include "IceTLS.h"
#include "IceTypes.h"
#include <memory>
#include <utility>
namespace Ice {
class Liveness {
Liveness() = delete;
Liveness(const Liveness &) = delete;
Liveness &operator=(const Liveness &) = delete;
class LivenessNode {
LivenessNode &operator=(const LivenessNode &) = delete;
LivenessNode() = default;
LivenessNode(const LivenessNode &) = default;
/// NumLocals is the number of Variables local to this block.
SizeT NumLocals = 0;
/// NumNonDeadPhis tracks the number of Phi instructions that
/// Inst::liveness() identified as tentatively live. If NumNonDeadPhis
/// changes from the last liveness pass, then liveness has not yet
/// converged.
SizeT NumNonDeadPhis = 0;
// LiveToVarMap maps a liveness bitvector index to a Variable. This is
// generally just for printing/dumping. The index should be less than
// NumLocals + Liveness::NumGlobals.
LivenessVector<Variable *> LiveToVarMap;
// LiveIn and LiveOut track the in- and out-liveness of the global
// variables. The size of each vector is LivenessNode::NumGlobals.
LivenessBV LiveIn, LiveOut;
// LiveBegin and LiveEnd track the instruction numbers of the start and end
// of each variable's live range within this block. The index/key of each
// element is less than NumLocals + Liveness::NumGlobals.
LiveBeginEndMap LiveBegin, LiveEnd;
void init();
void initPhiEdgeSplits(NodeList::const_iterator FirstNode,
VarList::const_iterator FirstVar);
Cfg *getFunc() const { return Func; }
LivenessMode getMode() const { return Mode; }
Variable *getVariable(SizeT LiveIndex, const CfgNode *Node) const;
SizeT getLiveIndex(SizeT VarIndex) const {
const SizeT LiveIndex = VarToLiveMap[VarIndex];
assert(LiveIndex != InvalidLiveIndex);
return LiveIndex;
SizeT getNumGlobalVars() const { return NumGlobals; }
SizeT getNumVarsInNode(const CfgNode *Node) const {
return NumGlobals + Nodes[Node->getIndex()].NumLocals;
SizeT &getNumNonDeadPhis(const CfgNode *Node) {
return Nodes[Node->getIndex()].NumNonDeadPhis;
LivenessBV &getLiveIn(const CfgNode *Node) {
SizeT Index = Node->getIndex();
return Nodes[Index].LiveIn;
LivenessBV &getLiveOut(const CfgNode *Node) {
SizeT Index = Node->getIndex();
return Nodes[Index].LiveOut;
LivenessBV &getScratchBV() { return ScratchBV; }
LiveBeginEndMap *getLiveBegin(const CfgNode *Node) {
SizeT Index = Node->getIndex();
return &Nodes[Index].LiveBegin;
LiveBeginEndMap *getLiveEnd(const CfgNode *Node) {
SizeT Index = Node->getIndex();
return &Nodes[Index].LiveEnd;
bool getRangeMask(SizeT Index) const { return RangeMask[Index]; }
ArenaAllocator *getAllocator() const { return Alloc.get(); }
static std::unique_ptr<Liveness> create(Cfg *Func, LivenessMode Mode) {
return std::unique_ptr<Liveness>(new Liveness(Func, Mode));
static void TlsInit() { LivenessAllocatorTraits::init(); }
std::string dumpStr() const {
return "MaxLocals(" + std::to_string(MaxLocals) +
"), "
"NumGlobals(" +
std::to_string(NumGlobals) + ")";
Liveness(Cfg *Func, LivenessMode Mode)
: Alloc(new ArenaAllocator()), AllocScope(this), Func(Func), Mode(Mode) {}
void initInternal(NodeList::const_iterator FirstNode,
VarList::const_iterator FirstVar, bool IsFullInit);
/// Resize Nodes so that Nodes[Index] is valid.
void resize(SizeT Index) {
if (Index >= Nodes.size()) {
assert(false && "The Nodes array is not expected to be resized.");
Nodes.resize(Index + 1);
std::unique_ptr<ArenaAllocator> Alloc;
LivenessAllocatorScope AllocScope; // Must be declared after Alloc.
static constexpr SizeT InvalidLiveIndex = -1;
Cfg *Func;
LivenessMode Mode;
/// Size of Nodes is Cfg::Nodes.size().
LivenessVector<LivenessNode> Nodes;
/// VarToLiveMap maps a Variable's Variable::Number to its live index within
/// its basic block.
LivenessVector<SizeT> VarToLiveMap;
/// LiveToVarMap is analogous to LivenessNode::LiveToVarMap, but for non-local
/// variables.
LivenessVector<Variable *> LiveToVarMap;
/// RangeMask[Variable::Number] indicates whether we want to track that
/// Variable's live range.
LivenessBV RangeMask;
/// ScratchBV is a bitvector that can be reused across CfgNode passes, to
/// avoid having to allocate/deallocate memory so frequently.
LivenessBV ScratchBV;
/// MaxLocals indicates what is the maximum number of local variables in a
/// single basic block, across all blocks in a function.
SizeT MaxLocals = 0;
/// NumGlobals indicates how many global variables (i.e., Multi Block) exist
/// for a function.
SizeT NumGlobals = 0;
} // end of namespace Ice