diff options
Diffstat (limited to 'llvm/lib/CodeGen')
| -rw-r--r-- | llvm/lib/CodeGen/CMakeLists.txt | 3 | ||||
| -rw-r--r-- | llvm/lib/CodeGen/RDFGraph.cpp | 1837 | ||||
| -rw-r--r-- | llvm/lib/CodeGen/RDFLiveness.cpp | 1118 | ||||
| -rw-r--r-- | llvm/lib/CodeGen/RDFRegisters.cpp | 380 |
4 files changed, 3338 insertions, 0 deletions
diff --git a/llvm/lib/CodeGen/CMakeLists.txt b/llvm/lib/CodeGen/CMakeLists.txt index 470b027e38c..a3916b7c624 100644 --- a/llvm/lib/CodeGen/CMakeLists.txt +++ b/llvm/lib/CodeGen/CMakeLists.txt @@ -114,6 +114,9 @@ add_llvm_component_library(LLVMCodeGen ProcessImplicitDefs.cpp PrologEpilogInserter.cpp PseudoSourceValue.cpp + RDFGraph.cpp + RDFLiveness.cpp + RDFRegisters.cpp ReachingDefAnalysis.cpp RegAllocBase.cpp RegAllocBasic.cpp diff --git a/llvm/lib/CodeGen/RDFGraph.cpp b/llvm/lib/CodeGen/RDFGraph.cpp new file mode 100644 index 00000000000..437a6b03009 --- /dev/null +++ b/llvm/lib/CodeGen/RDFGraph.cpp @@ -0,0 +1,1837 @@ +//===- 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/MC/MCRegisterInfo.h" +#include "llvm/Support/Debug.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> + +using namespace llvm; +using namespace rdf; + +// Printing functions. Have them here first, so that the rest of the code +// can use them. +namespace llvm { +namespace rdf { + +raw_ostream &operator<< (raw_ostream &OS, const PrintLaneMaskOpt &P) { + if (!P.Mask.all()) + OS << ':' << PrintLaneMask(P.Mask); + return OS; +} + +raw_ostream &operator<< (raw_ostream &OS, const Print<RegisterRef> &P) { + auto &TRI = P.G.getTRI(); + if (P.Obj.Reg > 0 && P.Obj.Reg < TRI.getNumRegs()) + OS << TRI.getName(P.Obj.Reg); + else + OS << '#' << P.Obj.Reg; + OS << PrintLaneMaskOpt(P.Obj.Mask); + return OS; +} + +raw_ostream &operator<< (raw_ostream &OS, const Print<NodeId> &P) { + auto NA = P.G.addr<NodeBase*>(P.Obj); + uint16_t Attrs = NA.Addr->getAttrs(); + uint16_t Kind = NodeAttrs::kind(Attrs); + uint16_t Flags = NodeAttrs::flags(Attrs); + switch (NodeAttrs::type(Attrs)) { + case NodeAttrs::Code: + switch (Kind) { + case NodeAttrs::Func: OS << 'f'; break; + case NodeAttrs::Block: OS << 'b'; break; + case NodeAttrs::Stmt: OS << 's'; break; + case NodeAttrs::Phi: OS << 'p'; break; + default: OS << "c?"; break; + } + break; + case NodeAttrs::Ref: + if (Flags & NodeAttrs::Undef) + OS << '/'; + if (Flags & NodeAttrs::Dead) + OS << '\\'; + if (Flags & NodeAttrs::Preserving) + OS << '+'; + if (Flags & NodeAttrs::Clobbering) + OS << '~'; + switch (Kind) { + case NodeAttrs::Use: OS << 'u'; break; + case NodeAttrs::Def: OS << 'd'; break; + case NodeAttrs::Block: OS << 'b'; break; + default: OS << "r?"; break; + } + break; + default: + OS << '?'; + break; + } + OS << P.Obj; + if (Flags & NodeAttrs::Shadow) + OS << '"'; + return OS; +} + +static void printRefHeader(raw_ostream &OS, const NodeAddr<RefNode*> RA, + const DataFlowGraph &G) { + OS << Print<NodeId>(RA.Id, G) << '<' + << Print<RegisterRef>(RA.Addr->getRegRef(G), G) << '>'; + if (RA.Addr->getFlags() & NodeAttrs::Fixed) + OS << '!'; +} + +raw_ostream &operator<< (raw_ostream &OS, const Print<NodeAddr<DefNode*>> &P) { + printRefHeader(OS, P.Obj, P.G); + OS << '('; + if (NodeId N = P.Obj.Addr->getReachingDef()) + OS << Print<NodeId>(N, P.G); + OS << ','; + if (NodeId N = P.Obj.Addr->getReachedDef()) + OS << Print<NodeId>(N, P.G); + OS << ','; + if (NodeId N = P.Obj.Addr->getReachedUse()) + OS << Print<NodeId>(N, P.G); + OS << "):"; + if (NodeId N = P.Obj.Addr->getSibling()) + OS << Print<NodeId>(N, P.G); + return OS; +} + +raw_ostream &operator<< (raw_ostream &OS, const Print<NodeAddr<UseNode*>> &P) { + printRefHeader(OS, P.Obj, P.G); + OS << '('; + if (NodeId N = P.Obj.Addr->getReachingDef()) + OS << Print<NodeId>(N, P.G); + OS << "):"; + if (NodeId N = P.Obj.Addr->getSibling()) + OS << Print<NodeId>(N, P.G); + return OS; +} + +raw_ostream &operator<< (raw_ostream &OS, + const Print<NodeAddr<PhiUseNode*>> &P) { + printRefHeader(OS, P.Obj, P.G); + OS << '('; + if (NodeId N = P.Obj.Addr->getReachingDef()) + OS << Print<NodeId>(N, P.G); + OS << ','; + if (NodeId N = P.Obj.Addr->getPredecessor()) + OS << Print<NodeId>(N, P.G); + OS << "):"; + if (NodeId N = P.Obj.Addr->getSibling()) + OS << Print<NodeId>(N, P.G); + return OS; +} + +raw_ostream &operator<< (raw_ostream &OS, const Print<NodeAddr<RefNode*>> &P) { + switch (P.Obj.Addr->getKind()) { + case NodeAttrs::Def: + OS << PrintNode<DefNode*>(P.Obj, P.G); + break; + case NodeAttrs::Use: + if (P.Obj.Addr->getFlags() & NodeAttrs::PhiRef) + OS << PrintNode<PhiUseNode*>(P.Obj, P.G); + else + OS << PrintNode<UseNode*>(P.Obj, P.G); + break; + } + return OS; +} + +raw_ostream &operator<< (raw_ostream &OS, const Print<NodeList> &P) { + unsigned N = P.Obj.size(); + for (auto I : P.Obj) { + OS << Print<NodeId>(I.Id, P.G); + if (--N) + OS << ' '; + } + return OS; +} + +raw_ostream &operator<< (raw_ostream &OS, const Print<NodeSet> &P) { + unsigned N = P.Obj.size(); + for (auto I : P.Obj) { + OS << Print<NodeId>(I, P.G); + if (--N) + OS << ' '; + } + return OS; +} + +namespace { + + template <typename T> + struct PrintListV { + PrintListV(const NodeList &L, const DataFlowGraph &G) : List(L), G(G) {} + + using Type = T; + const NodeList &List; + const DataFlowGraph &G; + }; + + template <typename T> + raw_ostream &operator<< (raw_ostream &OS, const PrintListV<T> &P) { + unsigned N = P.List.size(); + for (NodeAddr<T> A : P.List) { + OS << PrintNode<T>(A, P.G); + if (--N) + OS << ", "; + } + return OS; + } + +} // end anonymous namespace + +raw_ostream &operator<< (raw_ostream &OS, const Print<NodeAddr<PhiNode*>> &P) { + OS << Print<NodeId>(P.Obj.Id, P.G) << ": phi [" + << PrintListV<RefNode*>(P.Obj.Addr->members(P.G), P.G) << ']'; + return OS; +} + +raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<StmtNode *>> &P) { + const MachineInstr &MI = *P.Obj.Addr->getCode(); + unsigned Opc = MI.getOpcode(); + OS << Print<NodeId>(P.Obj.Id, P.G) << ": " << P.G.getTII().getName(Opc); + // Print the target for calls and branches (for readability). + if (MI.isCall() || MI.isBranch()) { + MachineInstr::const_mop_iterator T = + llvm::find_if(MI.operands(), + [] (const MachineOperand &Op) -> bool { + return Op.isMBB() || Op.isGlobal() || Op.isSymbol(); + }); + if (T != MI.operands_end()) { + OS << ' '; + if (T->isMBB()) + OS << printMBBReference(*T->getMBB()); + else if (T->isGlobal()) + OS << T->getGlobal()->getName(); + else if (T->isSymbol()) + OS << T->getSymbolName(); + } + } + OS << " [" << PrintListV<RefNode*>(P.Obj.Addr->members(P.G), P.G) << ']'; + return OS; +} + +raw_ostream &operator<< (raw_ostream &OS, + const Print<NodeAddr<InstrNode*>> &P) { + switch (P.Obj.Addr->getKind()) { + case NodeAttrs::Phi: + OS << PrintNode<PhiNode*>(P.Obj, P.G); + break; + case NodeAttrs::Stmt: + OS << PrintNode<StmtNode*>(P.Obj, P.G); + break; + default: + OS << "instr? " << Print<NodeId>(P.Obj.Id, P.G); + break; + } + return OS; +} + +raw_ostream &operator<< (raw_ostream &OS, + const Print<NodeAddr<BlockNode*>> &P) { + MachineBasicBlock *BB = P.Obj.Addr->getCode(); + unsigned NP = BB->pred_size(); + std::vector<int> Ns; + auto PrintBBs = [&OS] (std::vector<int> Ns) -> void { + unsigned N = Ns.size(); + for (int I : Ns) { + OS << "%bb." << I; + if (--N) + OS << ", "; + } + }; + + OS << Print<NodeId>(P.Obj.Id, P.G) << ": --- " << printMBBReference(*BB) + << " --- preds(" << NP << "): "; + for (MachineBasicBlock *B : BB->predecessors()) + Ns.push_back(B->getNumber()); + PrintBBs(Ns); + + unsigned NS = BB->succ_size(); + OS << " succs(" << NS << "): "; + Ns.clear(); + for (MachineBasicBlock *B : BB->successors()) + Ns.push_back(B->getNumber()); + PrintBBs(Ns); + OS << '\n'; + + for (auto I : P.Obj.Addr->members(P.G)) + OS << PrintNode<InstrNode*>(I, P.G) << '\n'; + return OS; +} + +raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<FuncNode *>> &P) { + OS << "DFG dump:[\n" << Print<NodeId>(P.Obj.Id, P.G) << ": Function: " + << P.Obj.Addr->getCode()->getName() << '\n'; + for (auto I : P.Obj.Addr->members(P.G)) + OS << PrintNode<BlockNode*>(I, P.G) << '\n'; + OS << "]\n"; + return OS; +} + +raw_ostream &operator<< (raw_ostream &OS, const Print<RegisterSet> &P) { + OS << '{'; + for (auto I : P.Obj) + OS << ' ' << Print<RegisterRef>(I, P.G); + OS << " }"; + return OS; +} + +raw_ostream &operator<< (raw_ostream &OS, const Print<RegisterAggr> &P) { + P.Obj.print(OS); + return OS; +} + +raw_ostream &operator<< (raw_ostream &OS, + const Print<DataFlowGraph::DefStack> &P) { + for (auto I = P.Obj.top(), E = P.Obj.bottom(); I != E; ) { + OS << Print<NodeId>(I->Id, P.G) + << '<' << Print<RegisterRef>(I->Addr->getRegRef(P.G), P.G) << '>'; + I.down(); + if (I != E) + OS << ' '; + } + return OS; +} + +} // end namespace rdf +} // end namespace llvm + +// 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() { + void *T = MemPool.Allocate(NodesPerBlock*NodeMemSize, NodeMemSize); + char *P = static_cast<char*>(T); + Blocks.push_back(P); + // Check if the block index is still within the allowed range, i.e. less + // than 2^N, where N is the number of bits in NodeId for the block index. + // BitsPerIndex is the number of bits per node index. + assert((Blocks.size() < ((size_t)1 << (8*sizeof(NodeId)-BitsPerIndex))) && + "Out of bits for block index"); + ActiveEnd = P; +} + +bool NodeAllocator::needNewBlock() { + if (Blocks.empty()) + return true; + + char *ActiveBegin = Blocks.back(); + uint32_t Index = (ActiveEnd-ActiveBegin)/NodeMemSize; + return Index >= NodesPerBlock; +} + +NodeAddr<NodeBase*> NodeAllocator::New() { + if (needNewBlock()) + startNewBlock(); + + uint32_t ActiveB = Blocks.size()-1; + uint32_t Index = (ActiveEnd - Blocks[ActiveB])/NodeMemSize; + NodeAddr<NodeBase*> NA = { reinterpret_cast<NodeBase*>(ActiveEnd), + makeId(ActiveB, Index) }; + ActiveEnd += NodeMemSize; + return NA; +} + +NodeId NodeAllocator::id(const NodeBase *P) const { + uintptr_t A = reinterpret_cast<uintptr_t>(P); + for (unsigned i = 0, n = Blocks.size(); i != n; ++i) { + uintptr_t B = reinterpret_cast<uintptr_t>(Blocks[i]); + if (A < B || A >= B + NodesPerBlock*NodeMemSize) + continue; + uint32_t Idx = (A-B)/NodeMemSize; + return makeId(i, Idx); + } + llvm_unreachable("Invalid node address"); +} + +void NodeAllocator::clear() { + MemPool.Reset(); + Blocks.clear(); + ActiveEnd = nullptr; +} + +// Insert node NA after "this" in the circular chain. +void NodeBase::append(NodeAddr<NodeBase*> NA) { + NodeId Nx = Next; + // If NA is already "next", do nothing. + if (Next != NA.Id) { + Next = NA.Id; + NA.Addr->Next = Nx; + } +} + +// Fundamental node manipulator functions. + +// Obtain the register reference from a reference node. +RegisterRef RefNode::getRegRef(const DataFlowGraph &G) const { + assert(NodeAttrs::type(Attrs) == NodeAttrs::Ref); + if (NodeAttrs::flags(Attrs) & NodeAttrs::PhiRef) + return G.unpack(Ref.PR); + assert(Ref.Op != nullptr); + return G.makeRegRef(*Ref.Op); +} + +// Set the register reference in the reference node directly (for references +// in phi nodes). +void RefNode::setRegRef(RegisterRef RR, DataFlowGraph &G) { + assert(NodeAttrs::type(Attrs) == NodeAttrs::Ref); + assert(NodeAttrs::flags(Attrs) & NodeAttrs::PhiRef); + Ref.PR = G.pack(RR); +} + +// 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) { + assert(NodeAttrs::type(Attrs) == NodeAttrs::Ref); + assert(!(NodeAttrs::flags(Attrs) & NodeAttrs::PhiRef)); + (void)G; + Ref.Op = Op; +} + +// Get the owner of a given reference node. +NodeAddr<NodeBase*> RefNode::getOwner(const DataFlowGraph &G) { + NodeAddr<NodeBase*> NA = G.addr<NodeBase*>(getNext()); + + while (NA.Addr != this) { + if (NA.Addr->getType() == NodeAttrs::Code) + return NA; + NA = G.addr<NodeBase*>(NA.Addr->getNext()); + } + llvm_unreachable("No owner in circular list"); +} + +// Connect the def node to the reaching def node. +void DefNode::linkToDef(NodeId Self, NodeAddr<DefNode*> DA) { + Ref.RD = DA.Id; + Ref.Sib = DA.Addr->getReachedDef(); + DA.Addr->setReachedDef(Self); +} + +// Connect the use node to the reaching def node. +void UseNode::linkToDef(NodeId Self, NodeAddr<DefNode*> DA) { + Ref.RD = DA.Id; + Ref.Sib = DA.Addr->getReachedUse(); + DA.Addr->setReachedUse(Self); +} + +// Get the first member of the code node. +NodeAddr<NodeBase*> CodeNode::getFirstMember(const DataFlowGraph &G) const { + if (Code.FirstM == 0) + return NodeAddr<NodeBase*>(); + return G.addr<NodeBase*>(Code.FirstM); +} + +// Get the last member of the code node. +NodeAddr<NodeBase*> CodeNode::getLastMember(const DataFlowGraph &G) const { + if (Code.LastM == 0) + return NodeAddr<NodeBase*>(); + return G.addr<NodeBase*>(Code.LastM); +} + +// Add node NA at the end of the member list of the given code node. +void CodeNode::addMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G) { + NodeAddr<NodeBase*> ML = getLastMember(G); + if (ML.Id != 0) { + ML.Addr->append(NA); + } else { + Code.FirstM = NA.Id; + NodeId Self = G.id(this); + NA.Addr->setNext(Self); + } + Code.LastM = NA.Id; +} + +// Add node NA after member node MA in the given code node. +void CodeNode::addMemberAfter(NodeAddr<NodeBase*> MA, NodeAddr<NodeBase*> NA, + const DataFlowGraph &G) { + MA.Addr->append(NA); + if (Code.LastM == MA.Id) + Code.LastM = NA.Id; +} + +// Remove member node NA from the given code node. +void CodeNode::removeMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G) { + NodeAddr<NodeBase*> MA = getFirstMember(G); + assert(MA.Id != 0); + + // Special handling if the member to remove is the first member. + if (MA.Id == NA.Id) { + if (Code.LastM == MA.Id) { + // If it is the only member, set both first and last to 0. + Code.FirstM = Code.LastM = 0; + } else { + // Otherwise, advance the first member. + Code.FirstM = MA.Addr->getNext(); + } + return; + } + + while (MA.Addr != this) { + NodeId MX = MA.Addr->getNext(); + if (MX == NA.Id) { + MA.Addr->setNext(NA.Addr->getNext()); + // If the member to remove happens to be the last one, update the + // LastM indicator. + if (Code.LastM == NA.Id) + Code.LastM = MA.Id; + return; + } + MA = G.addr<NodeBase*>(MX); + } + llvm_unreachable("No such member"); +} + +// Return the list of all members of the code node. +NodeList CodeNode::members(const DataFlowGraph &G) const { + static auto True = [] (NodeAddr<NodeBase*>) -> bool { return true; }; + return members_if(True, G); +} + +// Return the owner of the given instr node. +NodeAddr<NodeBase*> InstrNode::getOwner(const DataFlowGraph &G) { + NodeAddr<NodeBase*> NA = G.addr<NodeBase*>(getNext()); + + while (NA.Addr != this) { + assert(NA.Addr->getType() == NodeAttrs::Code); + if (NA.Addr->getKind() == NodeAttrs::Block) + return NA; + NA = G.addr<NodeBase*>(NA.Addr->getNext()); + } + llvm_unreachable("No owner in circular list"); +} + +// Add the phi node PA to the given block node. +void BlockNode::addPhi(NodeAddr<PhiNode*> PA, const DataFlowGraph &G) { + NodeAddr<NodeBase*> M = getFirstMember(G); + if (M.Id == 0) { + addMember(PA, G); + return; + } + + assert(M.Addr->getType() == NodeAttrs::Code); + if (M.Addr->getKind() == NodeAttrs::Stmt) { + // If the first member of the block is a statement, insert the phi as + // the first member. + Code.FirstM = PA.Id; + PA.Addr->setNext(M.Id); + } else { + // If the first member is a phi, find the last phi, and append PA to it. + assert(M.Addr->getKind() == NodeAttrs::Phi); + NodeAddr<NodeBase*> MN = M; + do { + M = MN; + MN = G.addr<NodeBase*>(M.Addr->getNext()); + assert(MN.Addr->getType() == NodeAttrs::Code); + } while (MN.Addr->getKind() == NodeAttrs::Phi); + + // M is the last phi. + addMemberAfter(M, PA, G); + } +} + +// Find the block node corresponding to the machine basic block BB in the +// given func node. +NodeAddr<BlockNode*> FuncNode::findBlock(const MachineBasicBlock *BB, + const DataFlowGraph &G) const { + auto EqBB = [BB] (NodeAddr<NodeBase*> NA) -> bool { + return NodeAddr<BlockNode*>(NA).Addr->getCode() == BB; + }; + NodeList Ms = members_if(EqBB, G); + if (!Ms.empty()) + return Ms[0]; + return NodeAddr<BlockNode*>(); +} + +// Get the block node for the entry block in the given function. +NodeAddr<BlockNode*> FuncNode::getEntryBlock(const DataFlowGraph &G) { + MachineBasicBlock *EntryB = &getCode()->front(); + return findBlock(EntryB, 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 { + return TII.isPredicated(In); +} + +// Check if the definition of RR produces an unspecified value. +bool TargetOperandInfo::isClobbering(const MachineInstr &In, unsigned OpNum) + const { + const MachineOperand &Op = In.getOperand(OpNum); + if (Op.isRegMask()) + return true; + assert(Op.isReg()); + if (In.isCall()) + if (Op.isDef() && Op.isDead()) + return true; + return false; +} + +// Check if the given instruction specifically requires +bool TargetOperandInfo::isFixedReg(const MachineInstr &In, unsigned OpNum) + const { + if (In.isCall() || In.isReturn() || In.isInlineAsm()) + return true; + // Check for a tail call. + if (In.isBranch()) + for (const MachineOperand &O : In.operands()) + if (O.isGlobal() || O.isSymbol()) + return true; + + const MCInstrDesc &D = In.getDesc(); + if (!D.getImplicitDefs() && !D.getImplicitUses()) + return false; + const MachineOperand &Op = In.getOperand(OpNum); + // If there is a sub-register, treat the operand as non-fixed. Currently, + // fixed registers are those that are listed in the descriptor as implicit + // uses or defs, and those lists do not allow sub-registers. + if (Op.getSubReg() != 0) + return false; + Register Reg = Op.getReg(); + const MCPhysReg *ImpR = Op.isDef() ? D.getImplicitDefs() + : D.getImplicitUses(); + if (!ImpR) + return false; + while (*ImpR) + if (*ImpR++ == Reg) + return true; + return false; +} + +// +// The data flow graph construction. +// + +DataFlowGraph::DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii, + const TargetRegisterInfo &tri, const MachineDominatorTree &mdt, + const MachineDominanceFrontier &mdf, const TargetOperandInfo &toi) + : MF(mf), TII(tii), TRI(tri), PRI(tri, mf), MDT(mdt), MDF(mdf), TOI(toi), + LiveIns(PRI) { +} + +// 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) : DS(S) { + if (!Top) { + // Initialize to bottom. + Pos = 0; + return; + } + // Initialize to the top, i.e. top-most non-delimiter (or 0, if empty). + Pos = DS.Stack.size(); + while (Pos > 0 && DS.isDelimiter(DS.Stack[Pos-1])) + Pos--; +} + +// Return the size of the stack, including block delimiters. +unsigned DataFlowGraph::DefStack::size() const { + unsigned S = 0; + for (auto I = top(), E = bottom(); I != E; I.down()) + S++; + return S; +} + +// 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() { + assert(!empty()); + unsigned P = nextDown(Stack.size()); + Stack.resize(P); +} + +// Push a delimiter for block node N on the stack. +void DataFlowGraph::DefStack::start_block(NodeId N) { + assert(N != 0); + Stack.push_back(NodeAddr<DefNode*>(nullptr, 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) { + assert(N != 0); + unsigned P = Stack.size(); + while (P > 0) { + bool Found = isDelimiter(Stack[P-1], N); + P--; + if (Found) + break; + } + // This will also remove the delimiter, if found. + Stack.resize(P); +} + +// Move the stack iterator up by one. +unsigned DataFlowGraph::DefStack::nextUp(unsigned P) const { + // Get the next valid position after P (skipping all delimiters). + // The input position P does not have to point to a non-delimiter. + unsigned SS = Stack.size(); + bool IsDelim; + assert(P < SS); + do { + P++; + IsDelim = isDelimiter(Stack[P-1]); + } while (P < SS && IsDelim); + assert(!IsDelim); + return P; +} + +// Move the stack iterator down by one. +unsigned DataFlowGraph::DefStack::nextDown(unsigned P) const { + // Get the preceding valid position before P (skipping all delimiters). + // The input position P does not have to point to a non-delimiter. + assert(P > 0 && P <= Stack.size()); + bool IsDelim = isDelimiter(Stack[P-1]); + do { + if (--P == 0) + break; + IsDelim = isDelimiter(Stack[P-1]); + } while (P > 0 && IsDelim); + assert(!IsDelim); + return P; +} + +// Register information. + +RegisterSet DataFlowGraph::getLandingPadLiveIns() const { + RegisterSet LR; + const Function &F = MF.getFunction(); + const Constant *PF = F.hasPersonalityFn() ? F.getPersonalityFn() + : nullptr; + const TargetLowering &TLI = *MF.getSubtarget().getTargetLowering(); + if (RegisterId R = TLI.getExceptionPointerRegister(PF)) + LR.insert(RegisterRef(R)); + if (!isFuncletEHPersonality(classifyEHPersonality(PF))) { + if (RegisterId R = TLI.getExceptionSelectorRegister(PF)) + LR.insert(RegisterRef(R)); + } + return LR; +} + +// Node management functions. + +// Get the pointer to the node with the id N. +NodeBase *DataFlowGraph::ptr(NodeId N) const { + if (N == 0) + return nullptr; + return Memory.ptr(N); +} + +// Get the id of the node at the address P. +NodeId DataFlowGraph::id(const NodeBase *P) const { + if (P == nullptr) + return 0; + return Memory.id(P); +} + +// Allocate a new node and set the attributes to Attrs. +NodeAddr<NodeBase*> DataFlowGraph::newNode(uint16_t Attrs) { + NodeAddr<NodeBase*> P = Memory.New(); + P.Addr->init(); + P.Addr->setAttrs(Attrs); + return P; +} + +// Make a copy of the given node B, except for the data-flow links, which +// are set to 0. +NodeAddr<NodeBase*> DataFlowGraph::cloneNode(const NodeAddr<NodeBase*> B) { + NodeAddr<NodeBase*> NA = newNode(0); + memcpy(NA.Addr, B.Addr, sizeof(NodeBase)); + // Ref nodes need to have the data-flow links reset. + if (NA.Addr->getType() == NodeAttrs::Ref) { + NodeAddr<RefNode*> RA = NA; + RA.Addr->setReachingDef(0); + RA.Addr->setSibling(0); + if (NA.Addr->getKind() == NodeAttrs::Def) { + NodeAddr<DefNode*> DA = NA; + DA.Addr->setReachedDef(0); + DA.Addr->setReachedUse(0); + } + } + return NA; +} + +// Allocation routines for specific node types/kinds. + +NodeAddr<UseNode*> DataFlowGraph::newUse(NodeAddr<InstrNode*> Owner, + MachineOperand &Op, uint16_t Flags) { + NodeAddr<UseNode*> UA = newNode(NodeAttrs::Ref | NodeAttrs::Use | Flags); + UA.Addr->setRegRef(&Op, *this); + return UA; +} + +NodeAddr<PhiUseNode*> DataFlowGraph::newPhiUse(NodeAddr<PhiNode*> Owner, + RegisterRef RR, NodeAddr<BlockNode*> PredB, uint16_t Flags) { + NodeAddr<PhiUseNode*> PUA = newNode(NodeAttrs::Ref | NodeAttrs::Use | Flags); + assert(Flags & NodeAttrs::PhiRef); + PUA.Addr->setRegRef(RR, *this); + PUA.Addr->setPredecessor(PredB.Id); + return PUA; +} + +NodeAddr<DefNode*> DataFlowGraph::newDef(NodeAddr<InstrNode*> Owner, + MachineOperand &Op, uint16_t Flags) { + NodeAddr<DefNode*> DA = newNode(NodeAttrs::Ref | NodeAttrs::Def | Flags); + DA.Addr->setRegRef(&Op, *this); + return DA; +} + +NodeAddr<DefNode*> DataFlowGraph::newDef(NodeAddr<InstrNode*> Owner, + RegisterRef RR, uint16_t Flags) { + NodeAddr<DefNode*> DA = newNode(NodeAttrs::Ref | NodeAttrs::Def | Flags); + assert(Flags & NodeAttrs::PhiRef); + DA.Addr->setRegRef(RR, *this); + return DA; +} + +NodeAddr<PhiNode*> DataFlowGraph::newPhi(NodeAddr<BlockNode*> Owner) { + NodeAddr<PhiNode*> PA = newNode(NodeAttrs::Code | NodeAttrs::Phi); + Owner.Addr->addPhi(PA, *this); + return PA; +} + +NodeAddr<StmtNode*> DataFlowGraph::newStmt(NodeAddr<BlockNode*> Owner, + MachineInstr *MI) { + NodeAddr<StmtNode*> SA = newNode(NodeAttrs::Code | NodeAttrs::Stmt); + SA.Addr->setCode(MI); + Owner.Addr->addMember(SA, *this); + return SA; +} + +NodeAddr<BlockNode*> DataFlowGraph::newBlock(NodeAddr<FuncNode*> Owner, + MachineBasicBlock *BB) { + NodeAddr<BlockNode*> BA = newNode(NodeAttrs::Code | NodeAttrs::Block); + BA.Addr->setCode(BB); + Owner.Addr->addMember(BA, *this); + return BA; +} + +NodeAddr<FuncNode*> DataFlowGraph::newFunc(MachineFunction *MF) { + NodeAddr<FuncNode*> FA = newNode(NodeAttrs::Code | NodeAttrs::Func); + FA.Addr->setCode(MF); + return FA; +} + +// Build the data flow graph. +void DataFlowGraph::build(unsigned Options) { + reset(); + Func = newFunc(&MF); + + if (MF.empty()) + return; + + for (MachineBasicBlock &B : MF) { + NodeAddr<BlockNode*> BA = newBlock(Func, &B); + BlockNodes.insert(std::make_pair(&B, BA)); + for (MachineInstr &I : B) { + if (I.isDebugInstr()) + continue; + buildStmt(BA, I); + } + } + + NodeAddr<BlockNode*> EA = Func.Addr->getEntryBlock(*this); + NodeList Blocks = Func.Addr->members(*this); + + // Collect information about block references. + RegisterSet AllRefs; + for (NodeAddr<BlockNode*> BA : Blocks) + for (NodeAddr<InstrNode*> IA : BA.Addr->members(*this)) + for (NodeAddr<RefNode*> RA : IA.Addr->members(*this)) + AllRefs.insert(RA.Addr->getRegRef(*this)); + + // Collect function live-ins and entry block live-ins. + MachineRegisterInfo &MRI = MF.getRegInfo(); + MachineBasicBlock &EntryB = *EA.Addr->getCode(); + assert(EntryB.pred_empty() && "Function entry block has predecessors"); + for (std::pair<unsigned,unsigned> P : MRI.liveins()) + LiveIns.insert(RegisterRef(P.first)); + if (MRI.tracksLiveness()) { + for (auto I : EntryB.liveins()) + LiveIns.insert(RegisterRef(I.PhysReg, I.LaneMask)); + } + + // Add function-entry phi nodes for the live-in registers. + //for (std::pair<RegisterId,LaneBitmask> P : LiveIns) { + for (auto I = LiveIns.rr_begin(), E = LiveIns.rr_end(); I != E; ++I) { + RegisterRef RR = *I; + NodeAddr<PhiNode*> PA = newPhi(EA); + uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving; + NodeAddr<DefNode*> DA = newDef(PA, RR, PhiFlags); + PA.Addr->addMember(DA, *this); + } + + // Add phis for landing pads. + // Landing pads, unlike usual backs blocks, are not entered through + // branches in the program, or fall-throughs from other blocks. They + // are entered from the exception handling runtime and target's ABI + // may define certain registers as defined on entry to such a block. + RegisterSet EHRegs = getLandingPadLiveIns(); + if (!EHRegs.empty()) { + for (NodeAddr<BlockNode*> BA : Blocks) { + const MachineBasicBlock &B = *BA.Addr->getCode(); + if (!B.isEHPad()) + continue; + + // Prepare a list of NodeIds of the block's predecessors. + NodeList Preds; + for (MachineBasicBlock *PB : B.predecessors()) + Preds.push_back(findBlock(PB)); + + // Build phi nodes for each live-in. + for (RegisterRef RR : EHRegs) { + NodeAddr<PhiNode*> PA = newPhi(BA); + uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving; + // Add def: + NodeAddr<DefNode*> DA = newDef(PA, RR, PhiFlags); + PA.Addr->addMember(DA, *this); + // Add uses (no reaching defs for phi uses): + for (NodeAddr<BlockNode*> PBA : Preds) { + NodeAddr<PhiUseNode*> PUA = newPhiUse(PA, RR, PBA); + PA.Addr->addMember(PUA, *this); + } + } + } + } + + // Build a map "PhiM" which will contain, for each block, the set + // of references that will require phi definitions in that block. + BlockRefsMap PhiM; + for (NodeAddr<BlockNode*> BA : Blocks) + recordDefsForDF(PhiM, BA); + for (NodeAddr<BlockNode*> BA : Blocks) + buildPhis(PhiM, AllRefs, BA); + + // Link all the refs. This will recursively traverse the dominator tree. + DefStackMap DM; + linkBlockRefs(DM, EA); + + // Finally, remove all unused phi nodes. + if (!(Options & BuildOptions::KeepDeadPhis)) + removeUnusedPhis(); +} + +RegisterRef DataFlowGraph::makeRegRef(unsigned Reg, unsigned Sub) const { + assert(PhysicalRegisterInfo::isRegMaskId(Reg) || + Register::isPhysicalRegister(Reg)); + assert(Reg != 0); + if (Sub != 0) + Reg = TRI.getSubReg(Reg, Sub); + return RegisterRef(Reg); +} + +RegisterRef DataFlowGraph::makeRegRef(const MachineOperand &Op) const { + assert(Op.isReg() || Op.isRegMask()); + if (Op.isReg()) + return makeRegRef(Op.getReg(), Op.getSubReg()); + return RegisterRef(PRI.getRegMaskId(Op.getRegMask()), LaneBitmask::getAll()); +} + +RegisterRef DataFlowGraph::restrictRef(RegisterRef AR, RegisterRef BR) const { + if (AR.Reg == BR.Reg) { + LaneBitmask M = AR.Mask & BR.Mask; + return M.any() ? RegisterRef(AR.Reg, M) : RegisterRef(); + } +#ifndef NDEBUG +// RegisterRef NAR = PRI.normalize(AR); +// RegisterRef NBR = PRI.normalize(BR); +// assert(NAR.Reg != NBR.Reg); +#endif + // This isn't strictly correct, because the overlap may happen in the + // part masked out. + if (PRI.alias(AR, BR)) + return AR; + return RegisterRef(); +} + +// For each stack in the map DefM, push the delimiter for block B on it. +void DataFlowGraph::markBlock(NodeId B, DefStackMap &DefM) { + // Push block delimiters. + for (auto I = DefM.begin(), E = DefM.end(); I != E; ++I) + I->second.start_block(B); +} + +// Remove all definitions coming from block B from each stack in DefM. +void DataFlowGraph::releaseBlock(NodeId B, DefStackMap &DefM) { + // Pop all defs from this block from the definition stack. Defs that were + // added to the map during the traversal of instructions will not have a + // delimiter, but for those, the whole stack will be emptied. + for (auto I = DefM.begin(), E = DefM.end(); I != E; ++I) + I->second.clear_block(B); + + // Finally, remove empty stacks from the map. + for (auto I = DefM.begin(), E = DefM.end(), NextI = I; I != E; I = NextI) { + NextI = std::next(I); + // This preserves the validity of iterators other than I. + if (I->second.empty()) + DefM.erase(I); + } +} + +// Push all definitions from the instruction node IA to an appropriate +// stack in DefM. +void DataFlowGraph::pushAllDefs(NodeAddr<InstrNode*> IA, DefStackMap &DefM) { + pushClobbers(IA, DefM); + pushDefs(IA, DefM); +} + +// Push all definitions from the instruction node IA to an appropriate +// stack in DefM. +void DataFlowGraph::pushClobbers(NodeAddr<InstrNode*> IA, DefStackMap &DefM) { + NodeSet Visited; + std::set<RegisterId> Defined; + + // The important objectives of this function are: + // - to be able to handle instructions both while the graph is being + // constructed, and after the graph has been constructed, and + // - maintain proper ordering of definitions on the stack for each + // register reference: + // - if there are two or more related defs in IA (i.e. coming from + // the same machine operand), then only push one def on the stack, + // - if there are multiple unrelated defs of non-overlapping + // subregisters of S, then the stack for S will have both (in an + // unspecified order), but the order does not matter from the data- + // -flow perspective. + + for (NodeAddr<DefNode*> DA : IA.Addr->members_if(IsDef, *this)) { + if (Visited.count(DA.Id)) + continue; + if (!(DA.Addr->getFlags() & NodeAttrs::Clobbering)) + continue; + + NodeList Rel = getRelatedRefs(IA, DA); + NodeAddr<DefNode*> PDA = Rel.front(); + RegisterRef RR = PDA.Addr->getRegRef(*this); + + // Push the definition on the stack for the register and all aliases. + // The def stack traversal in linkNodeUp will check the exact aliasing. + DefM[RR.Reg].push(DA); + Defined.insert(RR.Reg); + for (RegisterId A : PRI.getAliasSet(RR.Reg)) { + // Check that we don't push the same def twice. + assert(A != RR.Reg); + if (!Defined.count(A)) + DefM[A].push(DA); + } + // Mark all the related defs as visited. + for (NodeAddr<NodeBase*> T : Rel) + Visited.insert(T.Id); + } +} + +// Push all definitions from the instruction node IA to an appropriate +// stack in DefM. +void DataFlowGraph::pushDefs(NodeAddr<InstrNode*> IA, DefStackMap &DefM) { + NodeSet Visited; +#ifndef NDEBUG + std::set<RegisterId> Defined; +#endif + + // The important objectives of this function are: + // - to be able to handle instructions both while the graph is being + // constructed, and after the graph has been constructed, and + // - maintain proper ordering of definitions on the stack for each + // register reference: + // - if there are two or more related defs in IA (i.e. coming from + // the same machine operand), then only push one def on the stack, + // - if there are multiple unrelated defs of non-overlapping + // subregisters of S, then the stack for S will have both (in an + // unspecified order), but the order does not matter from the data- + // -flow perspective. + + for (NodeAddr<DefNode*> DA : IA.Addr->members_if(IsDef, *this)) { + if (Visited.count(DA.Id)) + continue; + if (DA.Addr->getFlags() & NodeAttrs::Clobbering) + continue; + + NodeList Rel = getRelatedRefs(IA, DA); + NodeAddr<DefNode*> PDA = Rel.front(); + RegisterRef RR = PDA.Addr->getRegRef(*this); +#ifndef NDEBUG + // Assert if the register is defined in two or more unrelated defs. + // This could happen if there are two or more def operands defining it. + if (!Defined.insert(RR.Reg).second) { + MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode(); + dbgs() << "Multiple definitions of register: " + << Print<RegisterRef>(RR, *this) << " in\n " << *MI << "in " + << printMBBReference(*MI->getParent()) << '\n'; + llvm_unreachable(nullptr); + } +#endif + // Push the definition on the stack for the register and all aliases. + // The def stack traversal in linkNodeUp will check the exact aliasing. + DefM[RR.Reg].push(DA); + for (RegisterId A : PRI.getAliasSet(RR.Reg)) { + // Check that we don't push the same def twice. + assert(A != RR.Reg); + DefM[A].push(DA); + } + // Mark all the related defs as visited. + for (NodeAddr<NodeBase*> T : Rel) + Visited.insert(T.Id); + } +} + +// 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(NodeAddr<InstrNode*> IA, + NodeAddr<RefNode*> RA) const { + assert(IA.Id != 0 && RA.Id != 0); + + NodeList Refs; + NodeId Start = RA.Id; + do { + Refs.push_back(RA); + RA = getNextRelated(IA, RA); + } while (RA.Id != 0 && RA.Id != Start); + return Refs; +} + +// Clear all information in the graph. +void DataFlowGraph::reset() { + Memory.clear(); + BlockNodes.clear(); + Func = NodeAddr<FuncNode*>(); +} + +// 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. +NodeAddr<RefNode*> DataFlowGraph::getNextRelated(NodeAddr<InstrNode*> IA, + NodeAddr<RefNode*> RA) const { + assert(IA.Id != 0 && RA.Id != 0); + + auto Related = [this,RA](NodeAddr<RefNode*> TA) -> bool { + if (TA.Addr->getKind() != RA.Addr->getKind()) + return false; + if (TA.Addr->getRegRef(*this) != RA.Addr->getRegRef(*this)) + return false; + return true; + }; + auto RelatedStmt = [&Related,RA](NodeAddr<RefNode*> TA) -> bool { + return Related(TA) && + &RA.Addr->getOp() == &TA.Addr->getOp(); + }; + auto RelatedPhi = [&Related,RA](NodeAddr<RefNode*> TA) -> bool { + if (!Related(TA)) + return false; + if (TA.Addr->getKind() != NodeAttrs::Use) + return true; + // For phi uses, compare predecessor blocks. + const NodeAddr<const PhiUseNode*> TUA = TA; + const NodeAddr<const PhiUseNode*> RUA = RA; + return TUA.Addr->getPredecessor() == RUA.Addr->getPredecessor(); + }; + + RegisterRef RR = RA.Addr->getRegRef(*this); + if (IA.Addr->getKind() == NodeAttrs::Stmt) + return RA.Addr->getNextRef(RR, RelatedStmt, true, *this); + return RA.Addr->getNextRef(RR, RelatedPhi, true, *this); +} + +// 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<NodeAddr<RefNode*>,NodeAddr<RefNode*>> +DataFlowGraph::locateNextRef(NodeAddr<InstrNode*> IA, NodeAddr<RefNode*> RA, + Predicate P) const { + assert(IA.Id != 0 && RA.Id != 0); + + NodeAddr<RefNode*> NA; + NodeId Start = RA.Id; + while (true) { + NA = getNextRelated(IA, RA); + if (NA.Id == 0 || NA.Id == Start) + break; + if (P(NA)) + break; + RA = NA; + } + + if (NA.Id != 0 && NA.Id != Start) + return std::make_pair(RA, NA); + return std::make_pair(RA, NodeAddr<RefNode*>()); +} + +// Get the next shadow node in IA corresponding to RA, and optionally create +// such a node if it does not exist. +NodeAddr<RefNode*> DataFlowGraph::getNextShadow(NodeAddr<InstrNode*> IA, + NodeAddr<RefNode*> RA, bool Create) { + assert(IA.Id != 0 && RA.Id != 0); + + uint16_t Flags = RA.Addr->getFlags() | NodeAttrs::Shadow; + auto IsShadow = [Flags] (NodeAddr<RefNode*> TA) -> bool { + return TA.Addr->getFlags() == Flags; + }; + auto Loc = locateNextRef(IA, RA, IsShadow); + if (Loc.second.Id != 0 || !Create) + return Loc.second; + + // Create a copy of RA and mark is as shadow. + NodeAddr<RefNode*> NA = cloneNode(RA); + NA.Addr->setFlags(Flags | NodeAttrs::Shadow); + IA.Addr->addMemberAfter(Loc.first, NA, *this); + return NA; +} + +// Get the next shadow node in IA corresponding to RA. Return null-address +// if such a node does not exist. +NodeAddr<RefNode*> DataFlowGraph::getNextShadow(NodeAddr<InstrNode*> IA, + NodeAddr<RefNode*> RA) const { + assert(IA.Id != 0 && RA.Id != 0); + uint16_t Flags = RA.Addr->getFlags() | NodeAttrs::Shadow; + auto IsShadow = [Flags] (NodeAddr<RefNode*> TA) -> bool { + return TA.Addr->getFlags() == Flags; + }; + return locateNextRef(IA, RA, IsShadow).second; +} + +// Create a new statement node in the block node BA that corresponds to +// the machine instruction MI. +void DataFlowGraph::buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In) { + NodeAddr<StmtNode*> SA = newStmt(BA, &In); + + auto isCall = [] (const MachineInstr &In) -> bool { + if (In.isCall()) + return true; + // Is tail call? + if (In.isBranch()) { + for (const MachineOperand &Op : In.operands()) + if (Op.isGlobal() || Op.isSymbol()) + return true; + // Assume indirect branches are calls. This is for the purpose of + // keeping implicit operands, and so it won't hurt on intra-function + // indirect branches. + if (In.isIndirectBranch()) + return true; + } + return false; + }; + + auto isDefUndef = [this] (const MachineInstr &In, RegisterRef DR) -> bool { + // This instruction defines DR. Check if there is a use operand that + // would make DR live on entry to the instruction. + for (const MachineOperand &Op : In.operands()) { + if (!Op.isReg() || Op.getReg() == 0 || !Op.isUse() || Op.isUndef()) + continue; + RegisterRef UR = makeRegRef(Op); + if (PRI.alias(DR, UR)) + return false; + } + return true; + }; + + bool IsCall = isCall(In); + unsigned NumOps = In.getNumOperands(); + + // Avoid duplicate implicit defs. This will not detect cases of implicit + // defs that define registers that overlap, but it is not clear how to + // interpret that in the absence of explicit defs. Overlapping explicit + // defs are likely illegal already. + BitVector DoneDefs(TRI.getNumRegs()); + // Process explicit defs first. + for (unsigned OpN = 0; OpN < NumOps; ++OpN) { + MachineOperand &Op = In.getOperand(OpN); + if (!Op.isReg() || !Op.isDef() || Op.isImplicit()) + continue; + Register R = Op.getReg(); + if (!R || !Register::isPhysicalRegister(R)) + continue; + uint16_t Flags = NodeAttrs::None; + if (TOI.isPreserving(In, OpN)) { + Flags |= NodeAttrs::Preserving; + // If the def is preserving, check if it is also undefined. + if (isDefUndef(In, makeRegRef(Op))) + Flags |= NodeAttrs::Undef; + } + if (TOI.isClobbering(In, OpN)) + Flags |= NodeAttrs::Clobbering; + if (TOI.isFixedReg(In, OpN)) + Flags |= NodeAttrs::Fixed; + if (IsCall && Op.isDead()) + Flags |= NodeAttrs::Dead; + NodeAddr<DefNode*> DA = newDef(SA, Op, Flags); + SA.Addr->addMember(DA, *this); + assert(!DoneDefs.test(R)); + DoneDefs.set(R); + } + + // Process reg-masks (as clobbers). + BitVector DoneClobbers(TRI.getNumRegs()); + for (unsigned OpN = 0; OpN < NumOps; ++OpN) { + MachineOperand &Op = In.getOperand(OpN); + if (!Op.isRegMask()) + continue; + uint16_t Flags = NodeAttrs::Clobbering | NodeAttrs::Fixed | + NodeAttrs::Dead; + NodeAddr<DefNode*> DA = newDef(SA, Op, Flags); + SA.Addr->addMember(DA, *this); + // Record all clobbered registers in DoneDefs. + const uint32_t *RM = Op.getRegMask(); + for (unsigned i = 1, e = TRI.getNumRegs(); i != e; ++i) + if (!(RM[i/32] & (1u << (i%32)))) + DoneClobbers.set(i); + } + + // Process implicit defs, skipping those that have already been added + // as explicit. + for (unsigned OpN = 0; OpN < NumOps; ++OpN) { + MachineOperand &Op = In.getOperand(OpN); + if (!Op.isReg() || !Op.isDef() || !Op.isImplicit()) + continue; + Register R = Op.getReg(); + if (!R || !Register::isPhysicalRegister(R) || DoneDefs.test(R)) + continue; + RegisterRef RR = makeRegRef(Op); + uint16_t Flags = NodeAttrs::None; + if (TOI.isPreserving(In, OpN)) { + Flags |= NodeAttrs::Preserving; + // If the def is preserving, check if it is also undefined. + if (isDefUndef(In, RR)) + Flags |= NodeAttrs::Undef; + } + if (TOI.isClobbering(In, OpN)) + Flags |= NodeAttrs::Clobbering; + if (TOI.isFixedReg(In, OpN)) + Flags |= NodeAttrs::Fixed; + if (IsCall && Op.isDead()) { + if (DoneClobbers.test(R)) + continue; + Flags |= NodeAttrs::Dead; + } + NodeAddr<DefNode*> DA = newDef(SA, Op, Flags); + SA.Addr->addMember(DA, *this); + DoneDefs.set(R); + } + + for (unsigned OpN = 0; OpN < NumOps; ++OpN) { + MachineOperand &Op = In.getOperand(OpN); + if (!Op.isReg() || !Op.isUse()) + continue; + Register R = Op.getReg(); + if (!R || !Register::isPhysicalRegister(R)) + continue; + uint16_t Flags = NodeAttrs::None; + if (Op.isUndef()) + Flags |= NodeAttrs::Undef; + if (TOI.isFixedReg(In, OpN)) + Flags |= NodeAttrs::Fixed; + NodeAddr<UseNode*> UA = newUse(SA, Op, Flags); + SA.Addr->addMember(UA, *this); + } +} + +// 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, + NodeAddr<BlockNode*> BA) { + // Check all defs from block BA and record them in each block in BA's + // iterated dominance frontier. This information will later be used to + // create phi nodes. + MachineBasicBlock *BB = BA.Addr->getCode(); + assert(BB); + auto DFLoc = MDF.find(BB); + if (DFLoc == MDF.end() || DFLoc->second.empty()) + return; + + // Traverse all instructions in the block and collect the set of all + // defined references. For each reference there will be a phi created + // in the block's iterated dominance frontier. + // This is done to make sure that each defined reference gets only one + // phi node, even if it is defined multiple times. + RegisterSet Defs; + for (NodeAddr<InstrNode*> IA : BA.Addr->members(*this)) + for (NodeAddr<RefNode*> RA : IA.Addr->members_if(IsDef, *this)) + Defs.insert(RA.Addr->getRegRef(*this)); + + // Calculate the iterated dominance frontier of BB. + const MachineDominanceFrontier::DomSetType &DF = DFLoc->second; + SetVector<MachineBasicBlock*> IDF(DF.begin(), DF.end()); + for (unsigned i = 0; i < IDF.size(); ++i) { + auto F = MDF.find(IDF[i]); + if (F != MDF.end()) + IDF.insert(F->second.begin(), F->second.end()); + } + + // Finally, add the set of defs to each block in the iterated dominance + // frontier. + for (auto DB : IDF) { + NodeAddr<BlockNode*> DBA = findBlock(DB); + PhiM[DBA.Id].insert(Defs.begin(), Defs.end()); + } +} + +// 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, RegisterSet &AllRefs, + NodeAddr<BlockNode*> BA) { + // Check if this blocks has any DF defs, i.e. if there are any defs + // that this block is in the iterated dominance frontier of. + auto HasDF = PhiM.find(BA.Id); + if (HasDF == PhiM.end() || HasDF->second.empty()) + return; + + // First, remove all R in Refs in such that there exists T in Refs + // such that T covers R. In other words, only leave those refs that + // are not covered by another ref (i.e. maximal with respect to covering). + + auto MaxCoverIn = [this] (RegisterRef RR, RegisterSet &RRs) -> RegisterRef { + for (RegisterRef I : RRs) + if (I != RR && RegisterAggr::isCoverOf(I, RR, PRI)) + RR = I; + return RR; + }; + + RegisterSet MaxDF; + for (RegisterRef I : HasDF->second) + MaxDF.insert(MaxCoverIn(I, HasDF->second)); + + std::vector<RegisterRef> MaxRefs; + for (RegisterRef I : MaxDF) + MaxRefs.push_back(MaxCoverIn(I, AllRefs)); + + // Now, for each R in MaxRefs, get the alias closure of R. If the closure + // only has R in it, create a phi a def for R. Otherwise, create a phi, + // and add a def for each S in the closure. + + // Sort the refs so that the phis will be created in a deterministic order. + llvm::sort(MaxRefs); + // Remove duplicates. + auto NewEnd = std::unique(MaxRefs.begin(), MaxRefs.end()); + MaxRefs.erase(NewEnd, MaxRefs.end()); + + auto Aliased = [this,&MaxRefs](RegisterRef RR, + std::vector<unsigned> &Closure) -> bool { + for (unsigned I : Closure) + if (PRI.alias(RR, MaxRefs[I])) + return true; + return false; + }; + + // Prepare a list of NodeIds of the block's predecessors. + NodeList Preds; + const MachineBasicBlock *MBB = BA.Addr->getCode(); + for (MachineBasicBlock *PB : MBB->predecessors()) + Preds.push_back(findBlock(PB)); + + while (!MaxRefs.empty()) { + // Put the first element in the closure, and then add all subsequent + // elements from MaxRefs to it, if they alias at least one element + // already in the closure. + // ClosureIdx: vector of indices in MaxRefs of members of the closure. + std::vector<unsigned> ClosureIdx = { 0 }; + for (unsigned i = 1; i != MaxRefs.size(); ++i) + if (Aliased(MaxRefs[i], ClosureIdx)) + ClosureIdx.push_back(i); + + // Build a phi for the closure. + unsigned CS = ClosureIdx.size(); + NodeAddr<PhiNode*> PA = newPhi(BA); + + // Add defs. + for (unsigned X = 0; X != CS; ++X) { + RegisterRef RR = MaxRefs[ClosureIdx[X]]; + uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving; + NodeAddr<DefNode*> DA = newDef(PA, RR, PhiFlags); + PA.Addr->addMember(DA, *this); + } + // Add phi uses. + for (NodeAddr<BlockNode*> PBA : Preds) { + for (unsigned X = 0; X != CS; ++X) { + RegisterRef RR = MaxRefs[ClosureIdx[X]]; + NodeAddr<PhiUseNode*> PUA = newPhiUse(PA, RR, PBA); + PA.Addr->addMember(PUA, *this); + } + } + + // Erase from MaxRefs all elements in the closure. + auto Begin = MaxRefs.begin(); + for (unsigned i = ClosureIdx.size(); i != 0; --i) + MaxRefs.erase(Begin + ClosureIdx[i-1]); + } +} + +// Remove any unneeded phi nodes that were created during the build process. +void DataFlowGraph::removeUnusedPhis() { + // This will remove unused phis, i.e. phis where each def does not reach + // any uses or other defs. This will not detect or remove circular phi + // chains that are otherwise dead. Unused/dead phis are created during + // the build process and this function is intended to remove these cases + // that are easily determinable to be unnecessary. + + SetVector<NodeId> PhiQ; + for (NodeAddr<BlockNode*> BA : Func.Addr->members(*this)) { + for (auto P : BA.Addr->members_if(IsPhi, *this)) + PhiQ.insert(P.Id); + } + + static auto HasUsedDef = [](NodeList &Ms) -> bool { + for (NodeAddr<NodeBase*> M : Ms) { + if (M.Addr->getKind() != NodeAttrs::Def) + continue; + NodeAddr<DefNode*> DA = M; + if (DA.Addr->getReachedDef() != 0 || DA.Addr->getReachedUse() != 0) + return true; + } + return false; + }; + + // Any phi, if it is removed, may affect other phis (make them dead). + // For each removed phi, collect the potentially affected phis and add + // them back to the queue. + while (!PhiQ.empty()) { + auto PA = addr<PhiNode*>(PhiQ[0]); + PhiQ.remove(PA.Id); + NodeList Refs = PA.Addr->members(*this); + if (HasUsedDef(Refs)) + continue; + for (NodeAddr<RefNode*> RA : Refs) { + if (NodeId RD = RA.Addr->getReachingDef()) { + auto RDA = addr<DefNode*>(RD); + NodeAddr<InstrNode*> OA = RDA.Addr->getOwner(*this); + if (IsPhi(OA)) + PhiQ.insert(OA.Id); + } + if (RA.Addr->isDef()) + unlinkDef(RA, true); + else + unlinkUse(RA, true); + } + NodeAddr<BlockNode*> BA = PA.Addr->getOwner(*this); + BA.Addr->removeMember(PA, *this); + } +} + +// 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(NodeAddr<InstrNode*> IA, NodeAddr<T> TA, + DefStack &DS) { + if (DS.empty()) + return; + RegisterRef RR = TA.Addr->getRegRef(*this); + NodeAddr<T> TAP; + + // References from the def stack that have been examined so far. + RegisterAggr Defs(PRI); + + for (auto I = DS.top(), E = DS.bottom(); I != E; I.down()) { + RegisterRef QR = I->Addr->getRegRef(*this); + + // Skip all defs that are aliased to any of the defs that we have already + // seen. If this completes a cover of RR, stop the stack traversal. + bool Alias = Defs.hasAliasOf(QR); + bool Cover = Defs.insert(QR).hasCoverOf(RR); + if (Alias) { + if (Cover) + break; + continue; + } + + // The reaching def. + NodeAddr<DefNode*> RDA = *I; + + // Pick the reached node. + if (TAP.Id == 0) { + TAP = TA; + } else { + // Mark the existing ref as "shadow" and create a new shadow. + TAP.Addr->setFlags(TAP.Addr->getFlags() | NodeAttrs::Shadow); + TAP = getNextShadow(IA, TAP, true); + } + + // Create the link. + TAP.Addr->linkToDef(TAP.Id, RDA); + + if (Cover) + break; + } +} + +// Create data-flow links for all reference nodes in the statement node SA. +template <typename Predicate> +void DataFlowGraph::linkStmtRefs(DefStackMap &DefM, NodeAddr<StmtNode*> SA, + Predicate P) { +#ifndef NDEBUG + RegisterSet Defs; +#endif + + // Link all nodes (upwards in the data-flow) with their reaching defs. + for (NodeAddr<RefNode*> RA : SA.Addr->members_if(P, *this)) { + uint16_t Kind = RA.Addr->getKind(); + assert(Kind == NodeAttrs::Def || Kind == NodeAttrs::Use); + RegisterRef RR = RA.Addr->getRegRef(*this); +#ifndef NDEBUG + // Do not expect multiple defs of the same reference. + assert(Kind != NodeAttrs::Def || !Defs.count(RR)); + Defs.insert(RR); +#endif + + auto F = DefM.find(RR.Reg); + if (F == DefM.end()) + continue; + DefStack &DS = F->second; + if (Kind == NodeAttrs::Use) + linkRefUp<UseNode*>(SA, RA, DS); + else if (Kind == NodeAttrs::Def) + linkRefUp<DefNode*>(SA, RA, DS); + else + llvm_unreachable("Unexpected node in instruction"); + } +} + +// 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, NodeAddr<BlockNode*> BA) { + // Push block delimiters. + markBlock(BA.Id, DefM); + + auto IsClobber = [] (NodeAddr<RefNode*> RA) -> bool { + return IsDef(RA) && (RA.Addr->getFlags() & NodeAttrs::Clobbering); + }; + auto IsNoClobber = [] (NodeAddr<RefNode*> RA) -> bool { + return IsDef(RA) && !(RA.Addr->getFlags() & NodeAttrs::Clobbering); + }; + + assert(BA.Addr && "block node address is needed to create a data-flow link"); + // For each non-phi instruction in the block, link all the defs and uses + // to their reaching defs. For any member of the block (including phis), + // push the defs on the corresponding stacks. + for (NodeAddr<InstrNode*> IA : BA.Addr->members(*this)) { + // Ignore phi nodes here. They will be linked part by part from the + // predecessors. + if (IA.Addr->getKind() == NodeAttrs::Stmt) { + linkStmtRefs(DefM, IA, IsUse); + linkStmtRefs(DefM, IA, IsClobber); + } + + // Push the definitions on the stack. + pushClobbers(IA, DefM); + + if (IA.Addr->getKind() == NodeAttrs::Stmt) + linkStmtRefs(DefM, IA, IsNoClobber); + + pushDefs(IA, DefM); + } + + // Recursively process all children in the dominator tree. + MachineDomTreeNode *N = MDT.getNode(BA.Addr->getCode()); + for (auto I : *N) { + MachineBasicBlock *SB = I->getBlock(); + NodeAddr<BlockNode*> SBA = findBlock(SB); + linkBlockRefs(DefM, SBA); + } + + // Link the phi uses from the successor blocks. + auto IsUseForBA = [BA](NodeAddr<NodeBase*> NA) -> bool { + if (NA.Addr->getKind() != NodeAttrs::Use) + return false; + assert(NA.Addr->getFlags() & NodeAttrs::PhiRef); + NodeAddr<PhiUseNode*> PUA = NA; + return PUA.Addr->getPredecessor() == BA.Id; + }; + + RegisterSet EHLiveIns = getLandingPadLiveIns(); + MachineBasicBlock *MBB = BA.Addr->getCode(); + + for (MachineBasicBlock *SB : MBB->successors()) { + bool IsEHPad = SB->isEHPad(); + NodeAddr<BlockNode*> SBA = findBlock(SB); + for (NodeAddr<InstrNode*> IA : SBA.Addr->members_if(IsPhi, *this)) { + // Do not link phi uses for landing pad live-ins. + if (IsEHPad) { + // Find what register this phi is for. + NodeAddr<RefNode*> RA = IA.Addr->getFirstMember(*this); + assert(RA.Id != 0); + if (EHLiveIns.count(RA.Addr->getRegRef(*this))) + continue; + } + // Go over each phi use associated with MBB, and link it. + for (auto U : IA.Addr->members_if(IsUseForBA, *this)) { + NodeAddr<PhiUseNode*> PUA = U; + RegisterRef RR = PUA.Addr->getRegRef(*this); + linkRefUp<UseNode*>(IA, PUA, DefM[RR.Reg]); + } + } + } + + // Pop all defs from this block from the definition stacks. + releaseBlock(BA.Id, DefM); +} + +// Remove the use node UA from any data-flow and structural links. +void DataFlowGraph::unlinkUseDF(NodeAddr<UseNode*> UA) { + NodeId RD = UA.Addr->getReachingDef(); + NodeId Sib = UA.Addr->getSibling(); + + if (RD == 0) { + assert(Sib == 0); + return; + } + + auto RDA = addr<DefNode*>(RD); + auto TA = addr<UseNode*>(RDA.Addr->getReachedUse()); + if (TA.Id == UA.Id) { + RDA.Addr->setReachedUse(Sib); + return; + } + + while (TA.Id != 0) { + NodeId S = TA.Addr->getSibling(); + if (S == UA.Id) { + TA.Addr->setSibling(UA.Addr->getSibling()); + return; + } + TA = addr<UseNode*>(S); + } +} + +// Remove the def node DA from any data-flow and structural links. +void DataFlowGraph::unlinkDefDF(NodeAddr<DefNode*> DA) { + // + // RD + // | reached + // | def + // : + // . + // +----+ + // ... -- | DA | -- ... -- 0 : sibling chain of DA + // +----+ + // | | reached + // | : def + // | . + // | ... : Siblings (defs) + // | + // : reached + // . use + // ... : sibling chain of reached uses + + NodeId RD = DA.Addr->getReachingDef(); + + // Visit all siblings of the reached def and reset their reaching defs. + // Also, defs reached by DA are now "promoted" to being reached by RD, + // so all of them will need to be spliced into the sibling chain where + // DA belongs. + auto getAllNodes = [this] (NodeId N) -> NodeList { + NodeList Res; + while (N) { + auto RA = addr<RefNode*>(N); + // Keep the nodes in the exact sibling order. + Res.push_back(RA); + N = RA.Addr->getSibling(); + } + return Res; + }; + NodeList ReachedDefs = getAllNodes(DA.Addr->getReachedDef()); + NodeList ReachedUses = getAllNodes(DA.Addr->getReachedUse()); + + if (RD == 0) { + for (NodeAddr<RefNode*> I : ReachedDefs) + I.Addr->setSibling(0); + for (NodeAddr<RefNode*> I : ReachedUses) + I.Addr->setSibling(0); + } + for (NodeAddr<DefNode*> I : ReachedDefs) + I.Addr->setReachingDef(RD); + for (NodeAddr<UseNode*> I : ReachedUses) + I.Addr->setReachingDef(RD); + + NodeId Sib = DA.Addr->getSibling(); + if (RD == 0) { + assert(Sib == 0); + return; + } + + // Update the reaching def node and remove DA from the sibling list. + auto RDA = addr<DefNode*>(RD); + auto TA = addr<DefNode*>(RDA.Addr->getReachedDef()); + if (TA.Id == DA.Id) { + // If DA is the first reached def, just update the RD's reached def + // to the DA's sibling. + RDA.Addr->setReachedDef(Sib); + } else { + // Otherwise, traverse the sibling list of the reached defs and remove + // DA from it. + while (TA.Id != 0) { + NodeId S = TA.Addr->getSibling(); + if (S == DA.Id) { + TA.Addr->setSibling(Sib); + break; + } + TA = addr<DefNode*>(S); + } + } + + // Splice the DA's reached defs into the RDA's reached def chain. + if (!ReachedDefs.empty()) { + auto Last = NodeAddr<DefNode*>(ReachedDefs.back()); + Last.Addr->setSibling(RDA.Addr->getReachedDef()); + RDA.Addr->setReachedDef(ReachedDefs.front().Id); + } + // Splice the DA's reached uses into the RDA's reached use chain. + if (!ReachedUses.empty()) { + auto Last = NodeAddr<UseNode*>(ReachedUses.back()); + Last.Addr->setSibling(RDA.Addr->getReachedUse()); + RDA.Addr->setReachedUse(ReachedUses.front().Id); + } +} diff --git a/llvm/lib/CodeGen/RDFLiveness.cpp b/llvm/lib/CodeGen/RDFLiveness.cpp new file mode 100644 index 00000000000..0bcd27f8ea4 --- /dev/null +++ b/llvm/lib/CodeGen/RDFLiveness.cpp @@ -0,0 +1,1118 @@ +//===- 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/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/RDFLiveness.h" +#include "llvm/CodeGen/RDFGraph.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/Debug.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" +#include <algorithm> +#include <cassert> +#include <cstdint> +#include <iterator> +#include <map> +#include <utility> +#include <vector> + +using namespace llvm; +using namespace rdf; + +static cl::opt<unsigned> MaxRecNest("rdf-liveness-max-rec", cl::init(25), + cl::Hidden, cl::desc("Maximum recursion level")); + +namespace llvm { +namespace rdf { + + raw_ostream &operator<< (raw_ostream &OS, const Print<Liveness::RefMap> &P) { + OS << '{'; + for (auto &I : P.Obj) { + OS << ' ' << printReg(I.first, &P.G.getTRI()) << '{'; + for (auto J = I.second.begin(), E = I.second.end(); J != E; ) { + OS << Print<NodeId>(J->first, P.G) << PrintLaneMaskOpt(J->second); + if (++J != E) + OS << ','; + } + OS << '}'; + } + OS << " }"; + return OS; + } + +} // end namespace rdf +} // end namespace llvm + +// 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) { + NodeList RDefs; // Return value. + SetVector<NodeId> DefQ; + SetVector<NodeId> Owners; + + // Dead defs will be treated as if they were live, since they are actually + // on the data-flow path. They cannot be ignored because even though they + // do not generate meaningful values, they still modify registers. + + // If the reference is undefined, there is nothing to do. + if (RefA.Addr->getFlags() & NodeAttrs::Undef) + return RDefs; + + // The initial queue should not have reaching defs for shadows. The + // whole point of a shadow is that it will have a reaching def that + // is not aliased to the reaching defs of the related shadows. + NodeId Start = RefA.Id; + auto SNA = DFG.addr<RefNode*>(Start); + if (NodeId RD = SNA.Addr->getReachingDef()) + DefQ.insert(RD); + if (TopShadows) { + for (auto S : DFG.getRelatedRefs(RefA.Addr->getOwner(DFG), RefA)) + if (NodeId RD = NodeAddr<RefNode*>(S).Addr->getReachingDef()) + DefQ.insert(RD); + } + + // Collect all the reaching defs, going up until a phi node is encountered, + // or there are no more reaching defs. From this set, the actual set of + // reaching defs will be selected. + // The traversal upwards must go on until a covering def is encountered. + // It is possible that a collection of non-covering (individually) defs + // will be sufficient, but keep going until a covering one is found. + for (unsigned i = 0; i < DefQ.size(); ++i) { + auto TA = DFG.addr<DefNode*>(DefQ[i]); + if (TA.Addr->getFlags() & NodeAttrs::PhiRef) + continue; + // Stop at the covering/overwriting def of the initial register reference. + RegisterRef RR = TA.Addr->getRegRef(DFG); + if (!DFG.IsPreservingDef(TA)) + if (RegisterAggr::isCoverOf(RR, RefRR, PRI)) + continue; + // Get the next level of reaching defs. This will include multiple + // reaching defs for shadows. + for (auto S : DFG.getRelatedRefs(TA.Addr->getOwner(DFG), TA)) + if (NodeId RD = NodeAddr<RefNode*>(S).Addr->getReachingDef()) + DefQ.insert(RD); + } + + // Remove all non-phi defs that are not aliased to RefRR, and collect + // the owners of the remaining defs. + SetVector<NodeId> Defs; + for (NodeId N : DefQ) { + auto TA = DFG.addr<DefNode*>(N); + bool IsPhi = TA.Addr->getFlags() & NodeAttrs::PhiRef; + if (!IsPhi && !PRI.alias(RefRR, TA.Addr->getRegRef(DFG))) + continue; + Defs.insert(TA.Id); + Owners.insert(TA.Addr->getOwner(DFG).Id); + } + + // Return the MachineBasicBlock containing a given instruction. + auto Block = [this] (NodeAddr<InstrNode*> IA) -> MachineBasicBlock* { + if (IA.Addr->getKind() == NodeAttrs::Stmt) + return NodeAddr<StmtNode*>(IA).Addr->getCode()->getParent(); + assert(IA.Addr->getKind() == NodeAttrs::Phi); + NodeAddr<PhiNode*> PA = IA; + NodeAddr<BlockNode*> BA = PA.Addr->getOwner(DFG); + return BA.Addr->getCode(); + }; + // Less(A,B) iff instruction A is further down in the dominator tree than B. + auto Less = [&Block,this] (NodeId A, NodeId B) -> bool { + if (A == B) + return false; + auto OA = DFG.addr<InstrNode*>(A), OB = DFG.addr<InstrNode*>(B); + MachineBasicBlock *BA = Block(OA), *BB = Block(OB); + if (BA != BB) + return MDT.dominates(BB, BA); + // They are in the same block. + bool StmtA = OA.Addr->getKind() == NodeAttrs::Stmt; + bool StmtB = OB.Addr->getKind() == NodeAttrs::Stmt; + if (StmtA) { + if (!StmtB) // OB is a phi and phis dominate statements. + return true; + MachineInstr *CA = NodeAddr<StmtNode*>(OA).Addr->getCode(); + MachineInstr *CB = NodeAddr<StmtNode*>(OB).Addr->getCode(); + // The order must be linear, so tie-break such equalities. + if (CA == CB) + return A < B; + return MDT.dominates(CB, CA); + } else { + // OA is a phi. + if (StmtB) + return false; + // Both are phis. There is no ordering between phis (in terms of + // the data-flow), so tie-break this via node id comparison. + return A < B; + } + }; + + std::vector<NodeId> Tmp(Owners.begin(), Owners.end()); + llvm::sort(Tmp, Less); + + // The vector is a list of instructions, so that defs coming from + // the same instruction don't need to be artificially ordered. + // Then, when computing the initial segment, and iterating over an + // instruction, pick the defs that contribute to the covering (i.e. is + // not covered by previously added defs). Check the defs individually, + // i.e. first check each def if is covered or not (without adding them + // to the tracking set), and then add all the selected ones. + + // The reason for this is this example: + // *d1<A>, *d2<B>, ... Assume A and B are aliased (can happen in phi nodes). + // *d3<C> If A \incl BuC, and B \incl AuC, then *d2 would be + // covered if we added A first, and A would be covered + // if we added B first. + + RegisterAggr RRs(DefRRs); + + auto DefInSet = [&Defs] (NodeAddr<RefNode*> TA) -> bool { + return TA.Addr->getKind() == NodeAttrs::Def && + Defs.count(TA.Id); + }; + for (NodeId T : Tmp) { + if (!FullChain && RRs.hasCoverOf(RefRR)) + break; + auto TA = DFG.addr<InstrNode*>(T); + bool IsPhi = DFG.IsCode<NodeAttrs::Phi>(TA); + NodeList Ds; + for (NodeAddr<DefNode*> DA : TA.Addr->members_if(DefInSet, DFG)) { + RegisterRef QR = DA.Addr->getRegRef(DFG); + // Add phi defs even if they are covered by subsequent defs. This is + // for cases where the reached use is not covered by any of the defs + // encountered so far: the phi def is needed to expose the liveness + // of that use to the entry of the block. + // Example: + // phi d1<R3>(,d2,), ... Phi def d1 is covered by d2. + // d2<R3>(d1,,u3), ... + // ..., u3<D1>(d2) This use needs to be live on entry. + if (FullChain || IsPhi || !RRs.hasCoverOf(QR)) + Ds.push_back(DA); + } + RDefs.insert(RDefs.end(), Ds.begin(), Ds.end()); + for (NodeAddr<DefNode*> DA : Ds) { + // When collecting a full chain of definitions, do not consider phi + // defs to actually define a register. + uint16_t Flags = DA.Addr->getFlags(); + if (!FullChain || !(Flags & NodeAttrs::PhiRef)) + if (!(Flags & NodeAttrs::Preserving)) // Don't care about Undef here. + RRs.insert(DA.Addr->getRegRef(DFG)); + } + } + + auto DeadP = [](const NodeAddr<DefNode*> DA) -> bool { + return DA.Addr->getFlags() & NodeAttrs::Dead; + }; + RDefs.resize(std::distance(RDefs.begin(), llvm::remove_if(RDefs, DeadP))); + + return RDefs; +} + +std::pair<NodeSet,bool> +Liveness::getAllReachingDefsRec(RegisterRef RefRR, NodeAddr<RefNode*> RefA, + NodeSet &Visited, const NodeSet &Defs) { + return getAllReachingDefsRecImpl(RefRR, RefA, Visited, Defs, 0, MaxRecNest); +} + +std::pair<NodeSet,bool> +Liveness::getAllReachingDefsRecImpl(RegisterRef RefRR, NodeAddr<RefNode*> RefA, + NodeSet &Visited, const NodeSet &Defs, unsigned Nest, unsigned MaxNest) { + if (Nest > MaxNest) + return { NodeSet(), false }; + // Collect all defined registers. Do not consider phis to be defining + // anything, only collect "real" definitions. + RegisterAggr DefRRs(PRI); + for (NodeId D : Defs) { + const auto DA = DFG.addr<const DefNode*>(D); + if (!(DA.Addr->getFlags() & NodeAttrs::PhiRef)) + DefRRs.insert(DA.Addr->getRegRef(DFG)); + } + + NodeList RDs = getAllReachingDefs(RefRR, RefA, false, true, DefRRs); + if (RDs.empty()) + return { Defs, true }; + + // Make a copy of the preexisting definitions and add the newly found ones. + NodeSet TmpDefs = Defs; + for (NodeAddr<NodeBase*> R : RDs) + TmpDefs.insert(R.Id); + + NodeSet Result = Defs; + + for (NodeAddr<DefNode*> DA : RDs) { + Result.insert(DA.Id); + if (!(DA.Addr->getFlags() & NodeAttrs::PhiRef)) + continue; + NodeAddr<PhiNode*> PA = DA.Addr->getOwner(DFG); + if (Visited.count(PA.Id)) + continue; + Visited.insert(PA.Id); + // Go over all phi uses and get the reaching defs for each use. + for (auto U : PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG)) { + const auto &T = getAllReachingDefsRecImpl(RefRR, U, Visited, TmpDefs, + Nest+1, MaxNest); + if (!T.second) + return { T.first, false }; + Result.insert(T.first.begin(), T.first.end()); + } + } + + return { Result, true }; +} + +/// 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) { + NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG); + NodeList Ins = BA.Addr->members(DFG); + NodeId FindId = IA.Id; + auto E = Ins.rend(); + auto B = std::find_if(Ins.rbegin(), E, + [FindId] (const NodeAddr<InstrNode*> T) { + return T.Id == FindId; + }); + // Do not scan IA (which is what B would point to). + if (B != E) + ++B; + + do { + // Process the range of instructions from B to E. + for (NodeAddr<InstrNode*> I : make_range(B, E)) { + NodeList Refs = I.Addr->members(DFG); + NodeAddr<RefNode*> Clob, Use; + // Scan all the refs in I aliased to RefRR, and return the one that + // is the closest to the output of I, i.e. def > clobber > use. + for (NodeAddr<RefNode*> R : Refs) { + if (!PRI.alias(R.Addr->getRegRef(DFG), RefRR)) + continue; + if (DFG.IsDef(R)) { + // If it's a non-clobbering def, just return it. + if (!(R.Addr->getFlags() & NodeAttrs::Clobbering)) + return R; + Clob = R; + } else { + Use = R; + } + } + if (Clob.Id != 0) + return Clob; + if (Use.Id != 0) + return Use; + } + + // Go up to the immediate dominator, if any. + MachineBasicBlock *BB = BA.Addr->getCode(); + BA = NodeAddr<BlockNode*>(); + if (MachineDomTreeNode *N = MDT.getNode(BB)) { + if ((N = N->getIDom())) + BA = DFG.findBlock(N->getBlock()); + } + if (!BA.Id) + break; + + Ins = BA.Addr->members(DFG); + B = Ins.rbegin(); + E = Ins.rend(); + } while (true); + + return NodeAddr<RefNode*>(); +} + +NodeSet Liveness::getAllReachedUses(RegisterRef RefRR, + NodeAddr<DefNode*> DefA, const RegisterAggr &DefRRs) { + NodeSet Uses; + + // If the original register is already covered by all the intervening + // defs, no more uses can be reached. + if (DefRRs.hasCoverOf(RefRR)) + return Uses; + + // Add all directly reached uses. + // If the def is dead, it does not provide a value for any use. + bool IsDead = DefA.Addr->getFlags() & NodeAttrs::Dead; + NodeId U = !IsDead ? DefA.Addr->getReachedUse() : 0; + while (U != 0) { + auto UA = DFG.addr<UseNode*>(U); + if (!(UA.Addr->getFlags() & NodeAttrs::Undef)) { + RegisterRef UR = UA.Addr->getRegRef(DFG); + if (PRI.alias(RefRR, UR) && !DefRRs.hasCoverOf(UR)) + Uses.insert(U); + } + U = UA.Addr->getSibling(); + } + + // Traverse all reached defs. This time dead defs cannot be ignored. + for (NodeId D = DefA.Addr->getReachedDef(), NextD; D != 0; D = NextD) { + auto DA = DFG.addr<DefNode*>(D); + NextD = DA.Addr->getSibling(); + RegisterRef DR = DA.Addr->getRegRef(DFG); + // If this def is already covered, it cannot reach anything new. + // Similarly, skip it if it is not aliased to the interesting register. + if (DefRRs.hasCoverOf(DR) || !PRI.alias(RefRR, DR)) + continue; + NodeSet T; + if (DFG.IsPreservingDef(DA)) { + // If it is a preserving def, do not update the set of intervening defs. + T = getAllReachedUses(RefRR, DA, DefRRs); + } else { + RegisterAggr NewDefRRs = DefRRs; + NewDefRRs.insert(DR); + T = getAllReachedUses(RefRR, DA, NewDefRRs); + } + Uses.insert(T.begin(), T.end()); + } + return Uses; +} + +void Liveness::computePhiInfo() { + RealUseMap.clear(); + + NodeList Phis; + NodeAddr<FuncNode*> FA = DFG.getFunc(); + NodeList Blocks = FA.Addr->members(DFG); + for (NodeAddr<BlockNode*> BA : Blocks) { + auto Ps = BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG); + Phis.insert(Phis.end(), Ps.begin(), Ps.end()); + } + + // phi use -> (map: reaching phi -> set of registers defined in between) + std::map<NodeId,std::map<NodeId,RegisterAggr>> PhiUp; + std::vector<NodeId> PhiUQ; // Work list of phis for upward propagation. + std::map<NodeId,RegisterAggr> PhiDRs; // Phi -> registers defined by it. + + // Go over all phis. + for (NodeAddr<PhiNode*> PhiA : Phis) { + // Go over all defs and collect the reached uses that are non-phi uses + // (i.e. the "real uses"). + RefMap &RealUses = RealUseMap[PhiA.Id]; + NodeList PhiRefs = PhiA.Addr->members(DFG); + + // Have a work queue of defs whose reached uses need to be found. + // For each def, add to the queue all reached (non-phi) defs. + SetVector<NodeId> DefQ; + NodeSet PhiDefs; + RegisterAggr DRs(PRI); + for (NodeAddr<RefNode*> R : PhiRefs) { + if (!DFG.IsRef<NodeAttrs::Def>(R)) + continue; + DRs.insert(R.Addr->getRegRef(DFG)); + DefQ.insert(R.Id); + PhiDefs.insert(R.Id); + } + PhiDRs.insert(std::make_pair(PhiA.Id, DRs)); + + // Collect the super-set of all possible reached uses. This set will + // contain all uses reached from this phi, either directly from the + // phi defs, or (recursively) via non-phi defs reached by the phi defs. + // This set of uses will later be trimmed to only contain these uses that + // are actually reached by the phi defs. + for (unsigned i = 0; i < DefQ.size(); ++i) { + NodeAddr<DefNode*> DA = DFG.addr<DefNode*>(DefQ[i]); + // Visit all reached uses. Phi defs should not really have the "dead" + // flag set, but check it anyway for consistency. + bool IsDead = DA.Addr->getFlags() & NodeAttrs::Dead; + NodeId UN = !IsDead ? DA.Addr->getReachedUse() : 0; + while (UN != 0) { + NodeAddr<UseNode*> A = DFG.addr<UseNode*>(UN); + uint16_t F = A.Addr->getFlags(); + if ((F & (NodeAttrs::Undef | NodeAttrs::PhiRef)) == 0) { + RegisterRef R = PRI.normalize(A.Addr->getRegRef(DFG)); + RealUses[R.Reg].insert({A.Id,R.Mask}); + } + UN = A.Addr->getSibling(); + } + // Visit all reached defs, and add them to the queue. These defs may + // override some of the uses collected here, but that will be handled + // later. + NodeId DN = DA.Addr->getReachedDef(); + while (DN != 0) { + NodeAddr<DefNode*> A = DFG.addr<DefNode*>(DN); + for (auto T : DFG.getRelatedRefs(A.Addr->getOwner(DFG), A)) { + uint16_t Flags = NodeAddr<DefNode*>(T).Addr->getFlags(); + // Must traverse the reached-def chain. Consider: + // def(D0) -> def(R0) -> def(R0) -> use(D0) + // The reachable use of D0 passes through a def of R0. + if (!(Flags & NodeAttrs::PhiRef)) + DefQ.insert(T.Id); + } + DN = A.Addr->getSibling(); + } + } + // Filter out these uses that appear to be reachable, but really + // are not. For example: + // + // R1:0 = d1 + // = R1:0 u2 Reached by d1. + // R0 = d3 + // = R1:0 u4 Still reached by d1: indirectly through + // the def d3. + // R1 = d5 + // = R1:0 u6 Not reached by d1 (covered collectively + // by d3 and d5), but following reached + // defs and uses from d1 will lead here. + for (auto UI = RealUses.begin(), UE = RealUses.end(); UI != UE; ) { + // For each reached register UI->first, there is a set UI->second, of + // uses of it. For each such use, check if it is reached by this phi, + // i.e. check if the set of its reaching uses intersects the set of + // this phi's defs. + NodeRefSet Uses = UI->second; + UI->second.clear(); + for (std::pair<NodeId,LaneBitmask> I : Uses) { + auto UA = DFG.addr<UseNode*>(I.first); + // Undef flag is checked above. + assert((UA.Addr->getFlags() & NodeAttrs::Undef) == 0); + RegisterRef R(UI->first, I.second); + // Calculate the exposed part of the reached use. + RegisterAggr Covered(PRI); + for (NodeAddr<DefNode*> DA : getAllReachingDefs(R, UA)) { + if (PhiDefs.count(DA.Id)) + break; + Covered.insert(DA.Addr->getRegRef(DFG)); + } + if (RegisterRef RC = Covered.clearIn(R)) { + // We are updating the map for register UI->first, so we need + // to map RC to be expressed in terms of that register. + RegisterRef S = PRI.mapTo(RC, UI->first); + UI->second.insert({I.first, S.Mask}); + } + } + UI = UI->second.empty() ? RealUses.erase(UI) : std::next(UI); + } + + // If this phi reaches some "real" uses, add it to the queue for upward + // propagation. + if (!RealUses.empty()) + PhiUQ.push_back(PhiA.Id); + + // Go over all phi uses and check if the reaching def is another phi. + // Collect the phis that are among the reaching defs of these uses. + // While traversing the list of reaching defs for each phi use, accumulate + // the set of registers defined between this phi (PhiA) and the owner phi + // of the reaching def. + NodeSet SeenUses; + + for (auto I : PhiRefs) { + if (!DFG.IsRef<NodeAttrs::Use>(I) || SeenUses.count(I.Id)) + continue; + NodeAddr<PhiUseNode*> PUA = I; + if (PUA.Addr->getReachingDef() == 0) + continue; + + RegisterRef UR = PUA.Addr->getRegRef(DFG); + NodeList Ds = getAllReachingDefs(UR, PUA, true, false, NoRegs); + RegisterAggr DefRRs(PRI); + + for (NodeAddr<DefNode*> D : Ds) { + if (D.Addr->getFlags() & NodeAttrs::PhiRef) { + NodeId RP = D.Addr->getOwner(DFG).Id; + std::map<NodeId,RegisterAggr> &M = PhiUp[PUA.Id]; + auto F = M.find(RP); + if (F == M.end()) + M.insert(std::make_pair(RP, DefRRs)); + else + F->second.insert(DefRRs); + } + DefRRs.insert(D.Addr->getRegRef(DFG)); + } + + for (NodeAddr<PhiUseNode*> T : DFG.getRelatedRefs(PhiA, PUA)) + SeenUses.insert(T.Id); + } + } + + if (Trace) { + dbgs() << "Phi-up-to-phi map with intervening defs:\n"; + for (auto I : PhiUp) { + dbgs() << "phi " << Print<NodeId>(I.first, DFG) << " -> {"; + for (auto R : I.second) + dbgs() << ' ' << Print<NodeId>(R.first, DFG) + << Print<RegisterAggr>(R.second, DFG); + dbgs() << " }\n"; + } + } + + // Propagate the reached registers up in the phi chain. + // + // The following type of situation needs careful handling: + // + // phi d1<R1:0> (1) + // | + // ... d2<R1> + // | + // phi u3<R1:0> (2) + // | + // ... u4<R1> + // + // The phi node (2) defines a register pair R1:0, and reaches a "real" + // use u4 of just R1. The same phi node is also known to reach (upwards) + // the phi node (1). However, the use u4 is not reached by phi (1), + // because of the intervening definition d2 of R1. The data flow between + // phis (1) and (2) is restricted to R1:0 minus R1, i.e. R0. + // + // When propagating uses up the phi chains, get the all reaching defs + // for a given phi use, and traverse the list until the propagated ref + // is covered, or until reaching the final phi. Only assume that the + // reference reaches the phi in the latter case. + + for (unsigned i = 0; i < PhiUQ.size(); ++i) { + auto PA = DFG.addr<PhiNode*>(PhiUQ[i]); + NodeList PUs = PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG); + RefMap &RUM = RealUseMap[PA.Id]; + + for (NodeAddr<UseNode*> UA : PUs) { + std::map<NodeId,RegisterAggr> &PUM = PhiUp[UA.Id]; + RegisterRef UR = PRI.normalize(UA.Addr->getRegRef(DFG)); + for (const std::pair<const NodeId, RegisterAggr> &P : PUM) { + bool Changed = false; + const RegisterAggr &MidDefs = P.second; + + // Collect the set PropUp of uses that are reached by the current + // phi PA, and are not covered by any intervening def between the + // currently visited use UA and the upward phi P. + + if (MidDefs.hasCoverOf(UR)) + continue; + + // General algorithm: + // for each (R,U) : U is use node of R, U is reached by PA + // if MidDefs does not cover (R,U) + // then add (R-MidDefs,U) to RealUseMap[P] + // + for (const std::pair<const RegisterId, NodeRefSet> &T : RUM) { + RegisterRef R(T.first); + // The current phi (PA) could be a phi for a regmask. It could + // reach a whole variety of uses that are not related to the + // specific upward phi (P.first). + const RegisterAggr &DRs = PhiDRs.at(P.first); + if (!DRs.hasAliasOf(R)) + continue; + R = PRI.mapTo(DRs.intersectWith(R), T.first); + for (std::pair<NodeId,LaneBitmask> V : T.second) { + LaneBitmask M = R.Mask & V.second; + if (M.none()) + continue; + if (RegisterRef SS = MidDefs.clearIn(RegisterRef(R.Reg, M))) { + NodeRefSet &RS = RealUseMap[P.first][SS.Reg]; + Changed |= RS.insert({V.first,SS.Mask}).second; + } + } + } + + if (Changed) + PhiUQ.push_back(P.first); + } + } + } + + if (Trace) { + dbgs() << "Real use map:\n"; + for (auto I : RealUseMap) { + dbgs() << "phi " << Print<NodeId>(I.first, DFG); + NodeAddr<PhiNode*> PA = DFG.addr<PhiNode*>(I.first); + NodeList Ds = PA.Addr->members_if(DFG.IsRef<NodeAttrs::Def>, DFG); + if (!Ds.empty()) { + RegisterRef RR = NodeAddr<DefNode*>(Ds[0]).Addr->getRegRef(DFG); + dbgs() << '<' << Print<RegisterRef>(RR, DFG) << '>'; + } else { + dbgs() << "<noreg>"; + } + dbgs() << " -> " << Print<RefMap>(I.second, DFG) << '\n'; + } + } +} + +void Liveness::computeLiveIns() { + // Populate the node-to-block map. This speeds up the calculations + // significantly. + NBMap.clear(); + for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) { + MachineBasicBlock *BB = BA.Addr->getCode(); + for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) { + for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG)) + NBMap.insert(std::make_pair(RA.Id, BB)); + NBMap.insert(std::make_pair(IA.Id, BB)); + } + } + + MachineFunction &MF = DFG.getMF(); + + // Compute IDF first, then the inverse. + decltype(IIDF) IDF; + for (MachineBasicBlock &B : MF) { + auto F1 = MDF.find(&B); + if (F1 == MDF.end()) + continue; + SetVector<MachineBasicBlock*> IDFB(F1->second.begin(), F1->second.end()); + for (unsigned i = 0; i < IDFB.size(); ++i) { + auto F2 = MDF.find(IDFB[i]); + if (F2 != MDF.end()) + IDFB.insert(F2->second.begin(), F2->second.end()); + } + // Add B to the IDF(B). This will put B in the IIDF(B). + IDFB.insert(&B); + IDF[&B].insert(IDFB.begin(), IDFB.end()); + } + + for (auto I : IDF) + for (auto S : I.second) + IIDF[S].insert(I.first); + + computePhiInfo(); + + NodeAddr<FuncNode*> FA = DFG.getFunc(); + NodeList Blocks = FA.Addr->members(DFG); + + // Build the phi live-on-entry map. + for (NodeAddr<BlockNode*> BA : Blocks) { + MachineBasicBlock *MB = BA.Addr->getCode(); + RefMap &LON = PhiLON[MB]; + for (auto P : BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG)) + for (const RefMap::value_type &S : RealUseMap[P.Id]) + LON[S.first].insert(S.second.begin(), S.second.end()); + } + + if (Trace) { + dbgs() << "Phi live-on-entry map:\n"; + for (auto &I : PhiLON) + dbgs() << "block #" << I.first->getNumber() << " -> " + << Print<RefMap>(I.second, DFG) << '\n'; + } + + // Build the phi live-on-exit map. Each phi node has some set of reached + // "real" uses. Propagate this set backwards into the block predecessors + // through the reaching defs of the corresponding phi uses. + for (NodeAddr<BlockNode*> BA : Blocks) { + NodeList Phis = BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG); + for (NodeAddr<PhiNode*> PA : Phis) { + RefMap &RUs = RealUseMap[PA.Id]; + if (RUs.empty()) + continue; + + NodeSet SeenUses; + for (auto U : PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG)) { + if (!SeenUses.insert(U.Id).second) + continue; + NodeAddr<PhiUseNode*> PUA = U; + if (PUA.Addr->getReachingDef() == 0) + continue; + + // Each phi has some set (possibly empty) of reached "real" uses, + // that is, uses that are part of the compiled program. Such a use + // may be located in some farther block, but following a chain of + // reaching defs will eventually lead to this phi. + // Any chain of reaching defs may fork at a phi node, but there + // will be a path upwards that will lead to this phi. Now, this + // chain will need to fork at this phi, since some of the reached + // uses may have definitions joining in from multiple predecessors. + // For each reached "real" use, identify the set of reaching defs + // coming from each predecessor P, and add them to PhiLOX[P]. + // + auto PrA = DFG.addr<BlockNode*>(PUA.Addr->getPredecessor()); + RefMap &LOX = PhiLOX[PrA.Addr->getCode()]; + + for (const std::pair<const RegisterId, NodeRefSet> &RS : RUs) { + // We need to visit each individual use. + for (std::pair<NodeId,LaneBitmask> P : RS.second) { + // Create a register ref corresponding to the use, and find + // all reaching defs starting from the phi use, and treating + // all related shadows as a single use cluster. + RegisterRef S(RS.first, P.second); + NodeList Ds = getAllReachingDefs(S, PUA, true, false, NoRegs); + for (NodeAddr<DefNode*> D : Ds) { + // Calculate the mask corresponding to the visited def. + RegisterAggr TA(PRI); + TA.insert(D.Addr->getRegRef(DFG)).intersect(S); + LaneBitmask TM = TA.makeRegRef().Mask; + LOX[S.Reg].insert({D.Id, TM}); + } + } + } + + for (NodeAddr<PhiUseNode*> T : DFG.getRelatedRefs(PA, PUA)) + SeenUses.insert(T.Id); + } // for U : phi uses + } // for P : Phis + } // for B : Blocks + + if (Trace) { + dbgs() << "Phi live-on-exit map:\n"; + for (auto &I : PhiLOX) + dbgs() << "block #" << I.first->getNumber() << " -> " + << Print<RefMap>(I.second, DFG) << '\n'; + } + + RefMap LiveIn; + traverse(&MF.front(), LiveIn); + + // Add function live-ins to the live-in set of the function entry block. + LiveMap[&MF.front()].insert(DFG.getLiveIns()); + + if (Trace) { + // Dump the liveness map + for (MachineBasicBlock &B : MF) { + std::vector<RegisterRef> LV; + for (auto I = B.livein_begin(), E = B.livein_end(); I != E; ++I) + LV.push_back(RegisterRef(I->PhysReg, I->LaneMask)); + llvm::sort(LV); + dbgs() << printMBBReference(B) << "\t rec = {"; + for (auto I : LV) + dbgs() << ' ' << Print<RegisterRef>(I, DFG); + dbgs() << " }\n"; + //dbgs() << "\tcomp = " << Print<RegisterAggr>(LiveMap[&B], DFG) << '\n'; + + LV.clear(); + const RegisterAggr &LG = LiveMap[&B]; + for (auto I = LG.rr_begin(), E = LG.rr_end(); I != E; ++I) + LV.push_back(*I); + llvm::sort(LV); + dbgs() << "\tcomp = {"; + for (auto I : LV) + dbgs() << ' ' << Print<RegisterRef>(I, DFG); + dbgs() << " }\n"; + + } + } +} + +void Liveness::resetLiveIns() { + for (auto &B : DFG.getMF()) { + // Remove all live-ins. + std::vector<unsigned> T; + for (auto I = B.livein_begin(), E = B.livein_end(); I != E; ++I) + T.push_back(I->PhysReg); + for (auto I : T) + B.removeLiveIn(I); + // Add the newly computed live-ins. + const RegisterAggr &LiveIns = LiveMap[&B]; + for (auto I = LiveIns.rr_begin(), E = LiveIns.rr_end(); I != E; ++I) { + RegisterRef R = *I; + B.addLiveIn({MCPhysReg(R.Reg), R.Mask}); + } + } +} + +void Liveness::resetKills() { + for (auto &B : DFG.getMF()) + resetKills(&B); +} + +void Liveness::resetKills(MachineBasicBlock *B) { + auto CopyLiveIns = [this] (MachineBasicBlock *B, BitVector &LV) -> void { + for (auto I : B->liveins()) { + MCSubRegIndexIterator S(I.PhysReg, &TRI); + if (!S.isValid()) { + LV.set(I.PhysReg); + continue; + } + do { + LaneBitmask M = TRI.getSubRegIndexLaneMask(S.getSubRegIndex()); + if ((M & I.LaneMask).any()) + LV.set(S.getSubReg()); + ++S; + } while (S.isValid()); + } + }; + + BitVector LiveIn(TRI.getNumRegs()), Live(TRI.getNumRegs()); + CopyLiveIns(B, LiveIn); + for (auto SI : B->successors()) + CopyLiveIns(SI, Live); + + for (auto I = B->rbegin(), E = B->rend(); I != E; ++I) { + MachineInstr *MI = &*I; + if (MI->isDebugInstr()) + continue; + + MI->clearKillInfo(); + for (auto &Op : MI->operands()) { + // An implicit def of a super-register may not necessarily start a + // live range of it, since an implicit use could be used to keep parts + // of it live. Instead of analyzing the implicit operands, ignore + // implicit defs. + if (!Op.isReg() || !Op.isDef() || Op.isImplicit()) + continue; + Register R = Op.getReg(); + if (!Register::isPhysicalRegister(R)) + continue; + for (MCSubRegIterator SR(R, &TRI, true); SR.isValid(); ++SR) + Live.reset(*SR); + } + for (auto &Op : MI->operands()) { + if (!Op.isReg() || !Op.isUse() || Op.isUndef()) + continue; + Register R = Op.getReg(); + if (!Register::isPhysicalRegister(R)) + continue; + bool IsLive = false; + for (MCRegAliasIterator AR(R, &TRI, true); AR.isValid(); ++AR) { + if (!Live[*AR]) + continue; + IsLive = true; + break; + } + if (!IsLive) + Op.setIsKill(true); + for (MCSubRegIterator SR(R, &TRI, true); SR.isValid(); ++SR) + Live.set(*SR); + } + } +} + +// Helper function to obtain the basic block containing the reaching def +// of the given use. +MachineBasicBlock *Liveness::getBlockWithRef(NodeId RN) const { + auto F = NBMap.find(RN); + if (F != NBMap.end()) + return F->second; + llvm_unreachable("Node id not in map"); +} + +void Liveness::traverse(MachineBasicBlock *B, RefMap &LiveIn) { + // The LiveIn map, for each (physical) register, contains the set of live + // reaching defs of that register that are live on entry to the associated + // block. + + // The summary of the traversal algorithm: + // + // R is live-in in B, if there exists a U(R), such that rdef(R) dom B + // and (U \in IDF(B) or B dom U). + // + // for (C : children) { + // LU = {} + // traverse(C, LU) + // LiveUses += LU + // } + // + // LiveUses -= Defs(B); + // LiveUses += UpwardExposedUses(B); + // for (C : IIDF[B]) + // for (U : LiveUses) + // if (Rdef(U) dom C) + // C.addLiveIn(U) + // + + // Go up the dominator tree (depth-first). + MachineDomTreeNode *N = MDT.getNode(B); + for (auto I : *N) { + RefMap L; + MachineBasicBlock *SB = I->getBlock(); + traverse(SB, L); + + for (auto S : L) + LiveIn[S.first].insert(S.second.begin(), S.second.end()); + } + + if (Trace) { + dbgs() << "\n-- " << printMBBReference(*B) << ": " << __func__ + << " after recursion into: {"; + for (auto I : *N) + dbgs() << ' ' << I->getBlock()->getNumber(); + dbgs() << " }\n"; + dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n'; + dbgs() << " Local: " << Print<RegisterAggr>(LiveMap[B], DFG) << '\n'; + } + + // Add reaching defs of phi uses that are live on exit from this block. + RefMap &PUs = PhiLOX[B]; + for (auto &S : PUs) + LiveIn[S.first].insert(S.second.begin(), S.second.end()); + + if (Trace) { + dbgs() << "after LOX\n"; + dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n'; + dbgs() << " Local: " << Print<RegisterAggr>(LiveMap[B], DFG) << '\n'; + } + + // The LiveIn map at this point has all defs that are live-on-exit from B, + // as if they were live-on-entry to B. First, we need to filter out all + // defs that are present in this block. Then we will add reaching defs of + // all upward-exposed uses. + + // To filter out the defs, first make a copy of LiveIn, and then re-populate + // LiveIn with the defs that should remain. + RefMap LiveInCopy = LiveIn; + LiveIn.clear(); + + for (const std::pair<const RegisterId, NodeRefSet> &LE : LiveInCopy) { + RegisterRef LRef(LE.first); + NodeRefSet &NewDefs = LiveIn[LRef.Reg]; // To be filled. + const NodeRefSet &OldDefs = LE.second; + for (NodeRef OR : OldDefs) { + // R is a def node that was live-on-exit + auto DA = DFG.addr<DefNode*>(OR.first); + NodeAddr<InstrNode*> IA = DA.Addr->getOwner(DFG); + NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG); + if (B != BA.Addr->getCode()) { + // Defs from a different block need to be preserved. Defs from this + // block will need to be processed further, except for phi defs, the + // liveness of which is handled through the PhiLON/PhiLOX maps. + NewDefs.insert(OR); + continue; + } + + // Defs from this block need to stop the liveness from being + // propagated upwards. This only applies to non-preserving defs, + // and to the parts of the register actually covered by those defs. + // (Note that phi defs should always be preserving.) + RegisterAggr RRs(PRI); + LRef.Mask = OR.second; + + if (!DFG.IsPreservingDef(DA)) { + assert(!(IA.Addr->getFlags() & NodeAttrs::Phi)); + // DA is a non-phi def that is live-on-exit from this block, and + // that is also located in this block. LRef is a register ref + // whose use this def reaches. If DA covers LRef, then no part + // of LRef is exposed upwards.A + if (RRs.insert(DA.Addr->getRegRef(DFG)).hasCoverOf(LRef)) + continue; + } + + // DA itself was not sufficient to cover LRef. In general, it is + // the last in a chain of aliased defs before the exit from this block. + // There could be other defs in this block that are a part of that + // chain. Check that now: accumulate the registers from these defs, + // and if they all together cover LRef, it is not live-on-entry. + for (NodeAddr<DefNode*> TA : getAllReachingDefs(DA)) { + // DefNode -> InstrNode -> BlockNode. + NodeAddr<InstrNode*> ITA = TA.Addr->getOwner(DFG); + NodeAddr<BlockNode*> BTA = ITA.Addr->getOwner(DFG); + // Reaching defs are ordered in the upward direction. + if (BTA.Addr->getCode() != B) { + // We have reached past the beginning of B, and the accumulated + // registers are not covering LRef. The first def from the + // upward chain will be live. + // Subtract all accumulated defs (RRs) from LRef. + RegisterRef T = RRs.clearIn(LRef); + assert(T); + NewDefs.insert({TA.Id,T.Mask}); + break; + } + + // TA is in B. Only add this def to the accumulated cover if it is + // not preserving. + if (!(TA.Addr->getFlags() & NodeAttrs::Preserving)) + RRs.insert(TA.Addr->getRegRef(DFG)); + // If this is enough to cover LRef, then stop. + if (RRs.hasCoverOf(LRef)) + break; + } + } + } + + emptify(LiveIn); + + if (Trace) { + dbgs() << "after defs in block\n"; + dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n'; + dbgs() << " Local: " << Print<RegisterAggr>(LiveMap[B], DFG) << '\n'; + } + + // Scan the block for upward-exposed uses and add them to the tracking set. + for (auto I : DFG.getFunc().Addr->findBlock(B, DFG).Addr->members(DFG)) { + NodeAddr<InstrNode*> IA = I; + if (IA.Addr->getKind() != NodeAttrs::Stmt) + continue; + for (NodeAddr<UseNode*> UA : IA.Addr->members_if(DFG.IsUse, DFG)) { + if (UA.Addr->getFlags() & NodeAttrs::Undef) + continue; + RegisterRef RR = PRI.normalize(UA.Addr->getRegRef(DFG)); + for (NodeAddr<DefNode*> D : getAllReachingDefs(UA)) + if (getBlockWithRef(D.Id) != B) + LiveIn[RR.Reg].insert({D.Id,RR.Mask}); + } + } + + if (Trace) { + dbgs() << "after uses in block\n"; + dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n'; + dbgs() << " Local: " << Print<RegisterAggr>(LiveMap[B], DFG) << '\n'; + } + + // Phi uses should not be propagated up the dominator tree, since they + // are not dominated by their corresponding reaching defs. + RegisterAggr &Local = LiveMap[B]; + RefMap &LON = PhiLON[B]; + for (auto &R : LON) { + LaneBitmask M; + for (auto P : R.second) + M |= P.second; + Local.insert(RegisterRef(R.first,M)); + } + + if (Trace) { + dbgs() << "after phi uses in block\n"; + dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n'; + dbgs() << " Local: " << Print<RegisterAggr>(Local, DFG) << '\n'; + } + + for (auto C : IIDF[B]) { + RegisterAggr &LiveC = LiveMap[C]; + for (const std::pair<const RegisterId, NodeRefSet> &S : LiveIn) + for (auto R : S.second) + if (MDT.properlyDominates(getBlockWithRef(R.first), C)) + LiveC.insert(RegisterRef(S.first, R.second)); + } +} + +void Liveness::emptify(RefMap &M) { + for (auto I = M.begin(), E = M.end(); I != E; ) + I = I->second.empty() ? M.erase(I) : std::next(I); +} diff --git a/llvm/lib/CodeGen/RDFRegisters.cpp b/llvm/lib/CodeGen/RDFRegisters.cpp new file mode 100644 index 00000000000..bd8661816e7 --- /dev/null +++ b/llvm/lib/CodeGen/RDFRegisters.cpp @@ -0,0 +1,380 @@ +//===- RDFRegisters.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 +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/BitVector.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/MachineOperand.h" +#include "llvm/CodeGen/RDFRegisters.h" +#include "llvm/CodeGen/TargetRegisterInfo.h" +#include "llvm/MC/LaneBitmask.h" +#include "llvm/MC/MCRegisterInfo.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" +#include <cassert> +#include <cstdint> +#include <set> +#include <utility> + +using namespace llvm; +using namespace rdf; + +PhysicalRegisterInfo::PhysicalRegisterInfo(const TargetRegisterInfo &tri, + const MachineFunction &mf) + : TRI(tri) { + RegInfos.resize(TRI.getNumRegs()); + + BitVector BadRC(TRI.getNumRegs()); + for (const TargetRegisterClass *RC : TRI.regclasses()) { + for (MCPhysReg R : *RC) { + RegInfo &RI = RegInfos[R]; + if (RI.RegClass != nullptr && !BadRC[R]) { + if (RC->LaneMask != RI.RegClass->LaneMask) { + BadRC.set(R); + RI.RegClass = nullptr; + } + } else + RI.RegClass = RC; + } + } + + UnitInfos.resize(TRI.getNumRegUnits()); + + for (uint32_t U = 0, NU = TRI.getNumRegUnits(); U != NU; ++U) { + if (UnitInfos[U].Reg != 0) + continue; + MCRegUnitRootIterator R(U, &TRI); + assert(R.isValid()); + RegisterId F = *R; + ++R; + if (R.isValid()) { + UnitInfos[U].Mask = LaneBitmask::getAll(); + UnitInfos[U].Reg = F; + } else { + for (MCRegUnitMaskIterator I(F, &TRI); I.isValid(); ++I) { + std::pair<uint32_t,LaneBitmask> P = *I; + UnitInfo &UI = UnitInfos[P.first]; + UI.Reg = F; + if (P.second.any()) { + UI.Mask = P.second; + } else { + if (const TargetRegisterClass *RC = RegInfos[F].RegClass) + UI.Mask = RC->LaneMask; + else + UI.Mask = LaneBitmask::getAll(); + } + } + } + } + + for (const uint32_t *RM : TRI.getRegMasks()) + RegMasks.insert(RM); + for (const MachineBasicBlock &B : mf) + for (const MachineInstr &In : B) + for (const MachineOperand &Op : In.operands()) + if (Op.isRegMask()) + RegMasks.insert(Op.getRegMask()); + + MaskInfos.resize(RegMasks.size()+1); + for (uint32_t M = 1, NM = RegMasks.size(); M <= NM; ++M) { + BitVector PU(TRI.getNumRegUnits()); + const uint32_t *MB = RegMasks.get(M); + for (unsigned i = 1, e = TRI.getNumRegs(); i != e; ++i) { + if (!(MB[i/32] & (1u << (i%32)))) + continue; + for (MCRegUnitIterator U(i, &TRI); U.isValid(); ++U) + PU.set(*U); + } + MaskInfos[M].Units = PU.flip(); + } +} + +RegisterRef PhysicalRegisterInfo::normalize(RegisterRef RR) const { + return RR; +} + +std::set<RegisterId> PhysicalRegisterInfo::getAliasSet(RegisterId Reg) const { + // Do not include RR in the alias set. + std::set<RegisterId> AS; + assert(isRegMaskId(Reg) || Register::isPhysicalRegister(Reg)); + if (isRegMaskId(Reg)) { + // XXX SLOW + const uint32_t *MB = getRegMaskBits(Reg); + for (unsigned i = 1, e = TRI.getNumRegs(); i != e; ++i) { + if (MB[i/32] & (1u << (i%32))) + continue; + AS.insert(i); + } + for (const uint32_t *RM : RegMasks) { + RegisterId MI = getRegMaskId(RM); + if (MI != Reg && aliasMM(RegisterRef(Reg), RegisterRef(MI))) + AS.insert(MI); + } + return AS; + } + + for (MCRegAliasIterator AI(Reg, &TRI, false); AI.isValid(); ++AI) + AS.insert(*AI); + for (const uint32_t *RM : RegMasks) { + RegisterId MI = getRegMaskId(RM); + if (aliasRM(RegisterRef(Reg), RegisterRef(MI))) + AS.insert(MI); + } + return AS; +} + +bool PhysicalRegisterInfo::aliasRR(RegisterRef RA, RegisterRef RB) const { + assert(Register::isPhysicalRegister(RA.Reg)); + assert(Register::isPhysicalRegister(RB.Reg)); + + MCRegUnitMaskIterator UMA(RA.Reg, &TRI); + MCRegUnitMaskIterator UMB(RB.Reg, &TRI); + // Reg units are returned in the numerical order. + while (UMA.isValid() && UMB.isValid()) { + // Skip units that are masked off in RA. + std::pair<RegisterId,LaneBitmask> PA = *UMA; + if (PA.second.any() && (PA.second & RA.Mask).none()) { + ++UMA; + continue; + } + // Skip units that are masked off in RB. + std::pair<RegisterId,LaneBitmask> PB = *UMB; + if (PB.second.any() && (PB.second & RB.Mask).none()) { + ++UMB; + continue; + } + + if (PA.first == PB.first) + return true; + if (PA.first < PB.first) + ++UMA; + else if (PB.first < PA.first) + ++UMB; + } + return false; +} + +bool PhysicalRegisterInfo::aliasRM(RegisterRef RR, RegisterRef RM) const { + assert(Register::isPhysicalRegister(RR.Reg) && isRegMaskId(RM.Reg)); + const uint32_t *MB = getRegMaskBits(RM.Reg); + bool Preserved = MB[RR.Reg/32] & (1u << (RR.Reg%32)); + // If the lane mask information is "full", e.g. when the given lane mask + // is a superset of the lane mask from the register class, check the regmask + // bit directly. + if (RR.Mask == LaneBitmask::getAll()) + return !Preserved; + const TargetRegisterClass *RC = RegInfos[RR.Reg].RegClass; + if (RC != nullptr && (RR.Mask & RC->LaneMask) == RC->LaneMask) + return !Preserved; + + // Otherwise, check all subregisters whose lane mask overlaps the given + // mask. For each such register, if it is preserved by the regmask, then + // clear the corresponding bits in the given mask. If at the end, all + // bits have been cleared, the register does not alias the regmask (i.e. + // is it preserved by it). + LaneBitmask M = RR.Mask; + for (MCSubRegIndexIterator SI(RR.Reg, &TRI); SI.isValid(); ++SI) { + LaneBitmask SM = TRI.getSubRegIndexLaneMask(SI.getSubRegIndex()); + if ((SM & RR.Mask).none()) + continue; + unsigned SR = SI.getSubReg(); + if (!(MB[SR/32] & (1u << (SR%32)))) + continue; + // The subregister SR is preserved. + M &= ~SM; + if (M.none()) + return false; + } + + return true; +} + +bool PhysicalRegisterInfo::aliasMM(RegisterRef RM, RegisterRef RN) const { + assert(isRegMaskId(RM.Reg) && isRegMaskId(RN.Reg)); + unsigned NumRegs = TRI.getNumRegs(); + const uint32_t *BM = getRegMaskBits(RM.Reg); + const uint32_t *BN = getRegMaskBits(RN.Reg); + + for (unsigned w = 0, nw = NumRegs/32; w != nw; ++w) { + // Intersect the negations of both words. Disregard reg=0, + // i.e. 0th bit in the 0th word. + uint32_t C = ~BM[w] & ~BN[w]; + if (w == 0) + C &= ~1; + if (C) + return true; + } + + // Check the remaining registers in the last word. + unsigned TailRegs = NumRegs % 32; + if (TailRegs == 0) + return false; + unsigned TW = NumRegs / 32; + uint32_t TailMask = (1u << TailRegs) - 1; + if (~BM[TW] & ~BN[TW] & TailMask) + return true; + + return false; +} + +RegisterRef PhysicalRegisterInfo::mapTo(RegisterRef RR, unsigned R) const { + if (RR.Reg == R) + return RR; + if (unsigned Idx = TRI.getSubRegIndex(R, RR.Reg)) + return RegisterRef(R, TRI.composeSubRegIndexLaneMask(Idx, RR.Mask)); + if (unsigned Idx = TRI.getSubRegIndex(RR.Reg, R)) { + const RegInfo &RI = RegInfos[R]; + LaneBitmask RCM = RI.RegClass ? RI.RegClass->LaneMask + : LaneBitmask::getAll(); + LaneBitmask M = TRI.reverseComposeSubRegIndexLaneMask(Idx, RR.Mask); + return RegisterRef(R, M & RCM); + } + llvm_unreachable("Invalid arguments: unrelated registers?"); +} + +bool RegisterAggr::hasAliasOf(RegisterRef RR) const { + if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) + return Units.anyCommon(PRI.getMaskUnits(RR.Reg)); + + for (MCRegUnitMaskIterator U(RR.Reg, &PRI.getTRI()); U.isValid(); ++U) { + std::pair<uint32_t,LaneBitmask> P = *U; + if (P.second.none() || (P.second & RR.Mask).any()) + if (Units.test(P.first)) + return true; + } + return false; +} + +bool RegisterAggr::hasCoverOf(RegisterRef RR) const { + if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) { + BitVector T(PRI.getMaskUnits(RR.Reg)); + return T.reset(Units).none(); + } + + for (MCRegUnitMaskIterator U(RR.Reg, &PRI.getTRI()); U.isValid(); ++U) { + std::pair<uint32_t,LaneBitmask> P = *U; + if (P.second.none() || (P.second & RR.Mask).any()) + if (!Units.test(P.first)) + return false; + } + return true; +} + +RegisterAggr &RegisterAggr::insert(RegisterRef RR) { + if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) { + Units |= PRI.getMaskUnits(RR.Reg); + return *this; + } + + for (MCRegUnitMaskIterator U(RR.Reg, &PRI.getTRI()); U.isValid(); ++U) { + std::pair<uint32_t,LaneBitmask> P = *U; + if (P.second.none() || (P.second & RR.Mask).any()) + Units.set(P.first); + } + return *this; +} + +RegisterAggr &RegisterAggr::insert(const RegisterAggr &RG) { + Units |= RG.Units; + return *this; +} + +RegisterAggr &RegisterAggr::intersect(RegisterRef RR) { + return intersect(RegisterAggr(PRI).insert(RR)); +} + +RegisterAggr &RegisterAggr::intersect(const RegisterAggr &RG) { + Units &= RG.Units; + return *this; +} + +RegisterAggr &RegisterAggr::clear(RegisterRef RR) { + return clear(RegisterAggr(PRI).insert(RR)); +} + +RegisterAggr &RegisterAggr::clear(const RegisterAggr &RG) { + Units.reset(RG.Units); + return *this; +} + +RegisterRef RegisterAggr::intersectWith(RegisterRef RR) const { + RegisterAggr T(PRI); + T.insert(RR).intersect(*this); + if (T.empty()) + return RegisterRef(); + RegisterRef NR = T.makeRegRef(); + assert(NR); + return NR; +} + +RegisterRef RegisterAggr::clearIn(RegisterRef RR) const { + return RegisterAggr(PRI).insert(RR).clear(*this).makeRegRef(); +} + +RegisterRef RegisterAggr::makeRegRef() const { + int U = Units.find_first(); + if (U < 0) + return RegisterRef(); + + auto AliasedRegs = [this] (uint32_t Unit, BitVector &Regs) { + for (MCRegUnitRootIterator R(Unit, &PRI.getTRI()); R.isValid(); ++R) + for (MCSuperRegIterator S(*R, &PRI.getTRI(), true); S.isValid(); ++S) + Regs.set(*S); + }; + + // Find the set of all registers that are aliased to all the units + // in this aggregate. + + // Get all the registers aliased to the first unit in the bit vector. + BitVector Regs(PRI.getTRI().getNumRegs()); + AliasedRegs(U, Regs); + U = Units.find_next(U); + + // For each other unit, intersect it with the set of all registers + // aliased that unit. + while (U >= 0) { + BitVector AR(PRI.getTRI().getNumRegs()); + AliasedRegs(U, AR); + Regs &= AR; + U = Units.find_next(U); + } + + // If there is at least one register remaining, pick the first one, + // and consolidate the masks of all of its units contained in this + // aggregate. + + int F = Regs.find_first(); + if (F <= 0) + return RegisterRef(); + + LaneBitmask M; + for (MCRegUnitMaskIterator I(F, &PRI.getTRI()); I.isValid(); ++I) { + std::pair<uint32_t,LaneBitmask> P = *I; + if (Units.test(P.first)) + M |= P.second.none() ? LaneBitmask::getAll() : P.second; + } + return RegisterRef(F, M); +} + +void RegisterAggr::print(raw_ostream &OS) const { + OS << '{'; + for (int U = Units.find_first(); U >= 0; U = Units.find_next(U)) + OS << ' ' << printRegUnit(U, &PRI.getTRI()); + OS << " }"; +} + +RegisterAggr::rr_iterator::rr_iterator(const RegisterAggr &RG, + bool End) + : Owner(&RG) { + for (int U = RG.Units.find_first(); U >= 0; U = RG.Units.find_next(U)) { + RegisterRef R = RG.PRI.getRefForUnit(U); + Masks[R.Reg] |= R.Mask; + } + Pos = End ? Masks.end() : Masks.begin(); + Index = End ? Masks.size() : 0; +} |
