Index: include/llvm/CodeGen/RDFGraph.h =================================================================== --- /dev/null +++ include/llvm/CodeGen/RDFGraph.h @@ -0,0 +1,945 @@ +//===--- RDFGraph.h ---------------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Target-independent, SSA-based data flow graph for register data flow (RDF) +// for a non-SSA program representation (e.g. post-RA machine code). +// +// +// *** Introduction +// +// The RDF graph is a collection of nodes, each of which denotes some element +// of the program. There are two main types of such elements: code and refe- +// rences. Conceptually, "code" is something that represents the structure +// of the program, e.g. basic block or a statement, while "reference" is an +// instance of accessing a register, e.g. a definition or a use. Nodes are +// connected with each other based on the structure of the program (such as +// blocks, instructions, etc.), and based on the data flow (e.g. reaching +// definitions, reached uses, etc.). The single-reaching-definition principle +// of SSA is generally observed, although, due to the non-SSA representation +// of the program, there are some differences between the graph and a "pure" +// SSA representation. +// +// +// *** Implementation remarks +// +// Since the graph can contain a large number of nodes, memory consumption +// was one of the major design considerations. As a result, there is a single +// base class NodeBase which defines all members used by all possible derived +// classes. The members are arranged in a union, and a derived class cannot +// add any data members of its own. Each derived class only defines the +// functional interface, i.e. member functions. NodeBase must be a POD, +// which implies that all of its members must also be PODs. +// Since nodes need to be connected with other nodes, pointers have been +// replaced with 32-bit identifiers: each node has an id of type NodeId. +// There are mapping functions in the graph that translate between actual +// memory addresses and the corresponding identifiers. +// A node id of 0 is equivalent to nullptr. +// +// +// *** Structure of the graph +// +// A code node is always a collection of other nodes. For example, a code +// node corresponding to a basic block will contain code nodes corresponding +// to instructions. In turn, a code node corresponding to an instruction will +// contain a list of reference nodes that correspond to the definitions and +// uses of registers in that instruction. The members are arranged into a +// circular list, which is yet another consequence of the effort to save +// memory: for each member node it should be possible to obtain its owner, +// and it should be possible to access all other members. There are other +// ways to accomplish that, but the circular list seemed the most natural. +// +// +- CodeNode -+ +// | | <---------------------------------------------------+ +// +-+--------+-+ | +// |FirstM |LastM | +// | +-------------------------------------+ | +// | | | +// V V | +// +----------+ Next +----------+ Next Next +----------+ Next | +// | |----->| |-----> ... ----->| |----->-+ +// +- Member -+ +- Member -+ +- Member -+ +// +// The order of members is such that related reference nodes (see below) +// should be contiguous on the member list. +// +// A reference node is a node that encapsulates an access to a register, +// in other words, data flowing into or out of a register. There are two +// major kinds of reference nodes: defs and uses. A def node will contain +// the id of the first reached use, and the id of the first reached def. +// Each def and use will contain the id of the reaching def, and also the +// id of the next reached def (for def nodes) or use (for use nodes). +// The "next node sharing the same reaching def" is denoted as "sibling". +// In summary: +// - Def node contains: reaching def, sibling, first reached def, and first +// reached use. +// - Use node contains: reaching def and sibling. +// +// +-- DefNode --+ +// | R2 = ... | <---+--------------------+ +// ++---------+--+ | | +// |Reached |Reached | | +// |Def |Use | | +// | | |Reaching |Reaching +// | V |Def |Def +// | +-- UseNode --+ Sib +-- UseNode --+ Sib Sib +// | | ... = R2 |----->| ... = R2 |----> ... ----> 0 +// | +-------------+ +-------------+ +// V +// +-- DefNode --+ Sib +// | R2 = ... |----> ... +// ++---------+--+ +// | | +// | | +// ... ... +// +// To get a full picture, the circular lists connecting blocks within a +// function, instructions within a block, etc. should be superimposed with +// the def-def, def-use links shown above. +// To illustrate this, consider a small example in a pseudo-assembly: +// foo: +// add r2, r0, r1 ; r2 = r0+r1 +// addi r0, r2, 1 ; r0 = r2+1 +// ret r0 ; return value in r0 +// +// The graph (in a format used by the debugging functions) would look like: +// +// DFG dump:[ +// f1: Function foo +// b2: === BB#0 === preds(0), succs(0): +// p3: phi [d4(,d12,u9):] +// p5: phi [d6(,,u10):] +// s7: add [d8(,,u13):, u9(d4):, u10(d6):] +// s11: addi [d12(d4,,u15):, u13(d8):] +// s14: ret [u15(d12):] +// ] +// +// The f1, b2, p3, etc. are node ids. The letter is prepended to indicate the +// kind of the node (i.e. f - function, b - basic block, p - phi, s - state- +// ment, d - def, u - use). +// The format of a def node is: +// dN(rd,d,u):sib, +// where +// N - numeric node id, +// R - register being defined +// rd - reaching def, +// d - reached def, +// u - reached use, +// sib - sibling. +// The format of a use node is: +// uN[!](rd):sib, +// where +// N - numeric node id, +// R - register being used, +// rd - reaching def, +// sib - sibling. +// Possible annotations (usually preceding the node id): +// + - preserving def, +// ~ - clobbering def, +// " - shadow ref (follows the node id), +// ! - fixed register (appears after register name). +// +// The circular lists are not explicit in the dump. +// +// +// *** Node attributes +// +// NodeBase has a member "Attrs", which is the primary way of determining +// the node's characteristics. The fields in this member decide whether +// the node is a code node or a reference node (i.e. node's "type"), then +// within each type, the "kind" determines what specifically this node +// represents. The remaining bits, "flags", contain additional information +// that is even more detailed than the "kind". +// CodeNode's kinds are: +// - Phi: Phi node, members are reference nodes. +// - Stmt: Statement, members are reference nodes. +// - Block: Basic block, members are instruction nodes (i.e. Phi or Stmt). +// - Func: The whole function. The members are basic block nodes. +// RefNode's kinds are: +// - Use. +// - Def. +// +// Meaning of flags: +// - Preserving: applies only to defs. A preserving def is one that can +// preserve some of the original bits among those that are included in +// the register associated with that def. For example, if R0 is a 32-bit +// register, but a def can only change the lower 16 bits, then it will +// be marked as preserving. +// - Shadow: a reference that has duplicates holding additional reaching +// defs (see more below). +// - Clobbering: applied only to defs, indicates that the value generated +// by this def is unspecified. A typical example would be volatile registers +// after function calls. +// - Fixed: the register in this def/use cannot be replaced with any other +// register. A typical case would be a parameter register to a call, or +// the register with the return value from a function. +// - Undef: the register in this reference the register is assumed to have +// no pre-existing value, even if it appears to be reached by some def. +// This is typically used to prevent keeping registers artificially live +// in cases when they are defined via predicated instructions. For example: +// r0 = add-if-true cond, r10, r11 (1) +// r0 = add-if-false cond, r12, r13, r0 (2) +// ... = r0 (3) +// Before (1), r0 is not intended to be live, and the use of r0 in (3) is +// not meant to be reached by any def preceding (1). However, since the +// defs in (1) and (2) are both preserving, these properties alone would +// imply that the use in (3) may indeed be reached by some prior def. +// Adding Undef flag to the def in (1) prevents that. The Undef flag +// may be applied to both defs and uses. +// - Dead: applies only to defs. The value coming out of a "dead" def is +// assumed to be unused, even if the def appears to be reaching other defs +// or uses. The motivation for this flag comes from dead defs on function +// calls: there is no way to determine if such a def is dead without +// analyzing the target's ABI. Hence the graph should contain this info, +// as it is unavailable otherwise. On the other hand, a def without any +// uses on a typical instruction is not the intended target for this flag. +// +// *** Shadow references +// +// It may happen that a super-register can have two (or more) non-overlapping +// sub-registers. When both of these sub-registers are defined and followed +// by a use of the super-register, the use of the super-register will not +// have a unique reaching def: both defs of the sub-registers need to be +// accounted for. In such cases, a duplicate use of the super-register is +// added and it points to the extra reaching def. Both uses are marked with +// a flag "shadow". Example: +// Assume t0 is a super-register of r0 and r1, r0 and r1 do not overlap: +// set r0, 1 ; r0 = 1 +// set r1, 1 ; r1 = 1 +// addi t1, t0, 1 ; t1 = t0+1 +// +// The DFG: +// s1: set [d2(,,u9):] +// s3: set [d4(,,u10):] +// s5: addi [d6(,,):, u7"(d2):, u8"(d4):] +// +// The statement s5 has two use nodes for t0: u7" and u9". The quotation +// mark " indicates that the node is a shadow. +// + +#ifndef LLVM_CODEGEN_RDFGRAPH_H +#define LLVM_CODEGEN_RDFGRAPH_H + +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/CodeGen/RDFRegisters.h" +#include "llvm/MC/LaneBitmask.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/MathExtras.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include +#include +#include +#include +#include +#include +#include +#include +#include + +// RDF uses uint32_t to refer to registers. This is to ensure that the type +// size remains specific. In other places, registers are often stored using +// unsigned. +static_assert(sizeof(uint32_t) == sizeof(unsigned), "Those should be equal"); + +namespace llvm { + + class MachineBasicBlock; + class MachineFunction; + class MachineInstr; + class MachineOperand; + class MachineDominanceFrontier; + class MachineDominatorTree; + class TargetInstrInfo; + +namespace rdf { + + typedef uint32_t NodeId; + + struct DataFlowGraph; + + struct NodeAttrs { + enum : uint16_t { + None = 0x0000, // Nothing + + // Types: 2 bits + TypeMask = 0x0003, + Code = 0x0001, // 01, Container + Ref = 0x0002, // 10, Reference + + // Kind: 3 bits + KindMask = 0x0007 << 2, + Def = 0x0001 << 2, // 001 + Use = 0x0002 << 2, // 010 + Phi = 0x0003 << 2, // 011 + Stmt = 0x0004 << 2, // 100 + Block = 0x0005 << 2, // 101 + Func = 0x0006 << 2, // 110 + + // Flags: 7 bits for now + FlagMask = 0x007F << 5, + Shadow = 0x0001 << 5, // 0000001, Has extra reaching defs. + Clobbering = 0x0002 << 5, // 0000010, Produces unspecified values. + PhiRef = 0x0004 << 5, // 0000100, Member of PhiNode. + Preserving = 0x0008 << 5, // 0001000, Def can keep original bits. + Fixed = 0x0010 << 5, // 0010000, Fixed register. + Undef = 0x0020 << 5, // 0100000, Has no pre-existing value. + Dead = 0x0040 << 5, // 1000000, Does not define a value. + }; + + static uint16_t type(uint16_t T) { return T & TypeMask; } + static uint16_t kind(uint16_t T) { return T & KindMask; } + static uint16_t flags(uint16_t T) { return T & FlagMask; } + + static uint16_t set_type(uint16_t A, uint16_t T) { + return (A & ~TypeMask) | T; + } + + static uint16_t set_kind(uint16_t A, uint16_t K) { + return (A & ~KindMask) | K; + } + + static uint16_t set_flags(uint16_t A, uint16_t F) { + return (A & ~FlagMask) | F; + } + + // Test if A contains B. + static bool contains(uint16_t A, uint16_t B) { + if (type(A) != Code) + return false; + uint16_t KB = kind(B); + switch (kind(A)) { + case Func: + return KB == Block; + case Block: + return KB == Phi || KB == Stmt; + case Phi: + case Stmt: + return type(B) == Ref; + } + return false; + } + }; + + struct BuildOptions { + enum : unsigned { + None = 0x00, + KeepDeadPhis = 0x01, // Do not remove dead phis during build. + }; + }; + + template struct NodeAddr { + NodeAddr() : Addr(nullptr) {} + NodeAddr(T A, NodeId I) : Addr(A), Id(I) {} + + // Type cast (casting constructor). The reason for having this class + // instead of std::pair. + template NodeAddr(const NodeAddr &NA) + : Addr(static_cast(NA.Addr)), Id(NA.Id) {} + + bool operator== (const NodeAddr &NA) const { + assert((Addr == NA.Addr) == (Id == NA.Id)); + return Addr == NA.Addr; + } + bool operator!= (const NodeAddr &NA) const { + return !operator==(NA); + } + + T Addr; + NodeId Id = 0; + }; + + struct NodeBase; + + // Fast memory allocation and translation between node id and node address. + // This is really the same idea as the one underlying the "bump pointer + // allocator", the difference being in the translation. A node id is + // composed of two components: the index of the block in which it was + // allocated, and the index within the block. With the default settings, + // where the number of nodes per block is 4096, the node id (minus 1) is: + // + // bit position: 11 0 + // +----------------------------+--------------+ + // | Index of the block |Index in block| + // +----------------------------+--------------+ + // + // The actual node id is the above plus 1, to avoid creating a node id of 0. + // + // This method significantly improved the build time, compared to using maps + // (std::unordered_map or DenseMap) to translate between pointers and ids. + struct NodeAllocator { + // Amount of storage for a single node. + enum { NodeMemSize = 32 }; + + NodeAllocator(uint32_t NPB = 4096) + : NodesPerBlock(NPB), BitsPerIndex(Log2_32(NPB)), + IndexMask((1 << BitsPerIndex)-1) { + assert(isPowerOf2_32(NPB)); + } + + NodeBase *ptr(NodeId N) const { + uint32_t N1 = N-1; + uint32_t BlockN = N1 >> BitsPerIndex; + uint32_t Offset = (N1 & IndexMask) * NodeMemSize; + return reinterpret_cast(Blocks[BlockN]+Offset); + } + + NodeId id(const NodeBase *P) const; + NodeAddr New(); + void clear(); + + private: + void startNewBlock(); + bool needNewBlock(); + + uint32_t makeId(uint32_t Block, uint32_t Index) const { + // Add 1 to the id, to avoid the id of 0, which is treated as "null". + return ((Block << BitsPerIndex) | Index) + 1; + } + + const uint32_t NodesPerBlock; + const uint32_t BitsPerIndex; + const uint32_t IndexMask; + char *ActiveEnd = nullptr; + std::vector Blocks; + typedef BumpPtrAllocatorImpl AllocatorTy; + AllocatorTy MemPool; + }; + + typedef std::set RegisterSet; + + struct TargetOperandInfo { + TargetOperandInfo(const TargetInstrInfo &tii) : TII(tii) {} + virtual ~TargetOperandInfo() = default; + + virtual bool isPreserving(const MachineInstr &In, unsigned OpNum) const; + virtual bool isClobbering(const MachineInstr &In, unsigned OpNum) const; + virtual bool isFixedReg(const MachineInstr &In, unsigned OpNum) const; + + const TargetInstrInfo &TII; + }; + + // Packed register reference. Only used for storage. + struct PackedRegisterRef { + RegisterId Reg; + uint32_t MaskId; + }; + + struct LaneMaskIndex : private IndexedSet { + LaneMaskIndex() = default; + + LaneBitmask getLaneMaskForIndex(uint32_t K) const { + return K == 0 ? LaneBitmask::getAll() : get(K); + } + uint32_t getIndexForLaneMask(LaneBitmask LM) { + assert(LM.any()); + return LM.all() ? 0 : insert(LM); + } + uint32_t getIndexForLaneMask(LaneBitmask LM) const { + assert(LM.any()); + return LM.all() ? 0 : find(LM); + } + }; + + struct NodeBase { + public: + // Make sure this is a POD. + NodeBase() = default; + + uint16_t getType() const { return NodeAttrs::type(Attrs); } + uint16_t getKind() const { return NodeAttrs::kind(Attrs); } + uint16_t getFlags() const { return NodeAttrs::flags(Attrs); } + NodeId getNext() const { return Next; } + + uint16_t getAttrs() const { return Attrs; } + void setAttrs(uint16_t A) { Attrs = A; } + void setFlags(uint16_t F) { setAttrs(NodeAttrs::set_flags(getAttrs(), F)); } + + // Insert node NA after "this" in the circular chain. + void append(NodeAddr NA); + // Initialize all members to 0. + void init() { memset(this, 0, sizeof *this); } + void setNext(NodeId N) { Next = N; } + + protected: + uint16_t Attrs; + uint16_t Reserved; + NodeId Next; // Id of the next node in the circular chain. + // Definitions of nested types. Using anonymous nested structs would make + // this class definition clearer, but unnamed structs are not a part of + // the standard. + struct Def_struct { + NodeId DD, DU; // Ids of the first reached def and use. + }; + struct PhiU_struct { + NodeId PredB; // Id of the predecessor block for a phi use. + }; + struct Code_struct { + void *CP; // Pointer to the actual code. + NodeId FirstM, LastM; // Id of the first member and last. + }; + struct Ref_struct { + NodeId RD, Sib; // Ids of the reaching def and the sibling. + union { + Def_struct Def; + PhiU_struct PhiU; + }; + union { + MachineOperand *Op; // Non-phi refs point to a machine operand. + PackedRegisterRef PR; // Phi refs store register info directly. + }; + }; + + // The actual payload. + union { + Ref_struct Ref; + Code_struct Code; + }; + }; + // The allocator allocates chunks of 32 bytes for each node. The fact that + // each node takes 32 bytes in memory is used for fast translation between + // the node id and the node address. + static_assert(sizeof(NodeBase) <= NodeAllocator::NodeMemSize, + "NodeBase must be at most NodeAllocator::NodeMemSize bytes"); + + typedef std::vector> NodeList; + typedef std::set NodeSet; + + struct RefNode : public NodeBase { + RefNode() = default; + + RegisterRef getRegRef(const DataFlowGraph &G) const; + + MachineOperand &getOp() { + assert(!(getFlags() & NodeAttrs::PhiRef)); + return *Ref.Op; + } + + void setRegRef(RegisterRef RR, DataFlowGraph &G); + void setRegRef(MachineOperand *Op, DataFlowGraph &G); + + NodeId getReachingDef() const { + return Ref.RD; + } + void setReachingDef(NodeId RD) { + Ref.RD = RD; + } + + NodeId getSibling() const { + return Ref.Sib; + } + void setSibling(NodeId Sib) { + Ref.Sib = Sib; + } + + bool isUse() const { + assert(getType() == NodeAttrs::Ref); + return getKind() == NodeAttrs::Use; + } + + bool isDef() const { + assert(getType() == NodeAttrs::Ref); + return getKind() == NodeAttrs::Def; + } + + template + NodeAddr getNextRef(RegisterRef RR, Predicate P, bool NextOnly, + const DataFlowGraph &G); + NodeAddr getOwner(const DataFlowGraph &G); + }; + + struct DefNode : public RefNode { + NodeId getReachedDef() const { + return Ref.Def.DD; + } + void setReachedDef(NodeId D) { + Ref.Def.DD = D; + } + NodeId getReachedUse() const { + return Ref.Def.DU; + } + void setReachedUse(NodeId U) { + Ref.Def.DU = U; + } + + void linkToDef(NodeId Self, NodeAddr DA); + }; + + struct UseNode : public RefNode { + void linkToDef(NodeId Self, NodeAddr DA); + }; + + struct PhiUseNode : public UseNode { + NodeId getPredecessor() const { + assert(getFlags() & NodeAttrs::PhiRef); + return Ref.PhiU.PredB; + } + void setPredecessor(NodeId B) { + assert(getFlags() & NodeAttrs::PhiRef); + Ref.PhiU.PredB = B; + } + }; + + struct CodeNode : public NodeBase { + template T getCode() const { + return static_cast(Code.CP); + } + void setCode(void *C) { + Code.CP = C; + } + + NodeAddr getFirstMember(const DataFlowGraph &G) const; + NodeAddr getLastMember(const DataFlowGraph &G) const; + void addMember(NodeAddr NA, const DataFlowGraph &G); + void addMemberAfter(NodeAddr MA, NodeAddr NA, + const DataFlowGraph &G); + void removeMember(NodeAddr NA, const DataFlowGraph &G); + + NodeList members(const DataFlowGraph &G) const; + template + NodeList members_if(Predicate P, const DataFlowGraph &G) const; + }; + + struct InstrNode : public CodeNode { + NodeAddr getOwner(const DataFlowGraph &G); + }; + + struct PhiNode : public InstrNode { + MachineInstr *getCode() const { + return nullptr; + } + }; + + struct StmtNode : public InstrNode { + MachineInstr *getCode() const { + return CodeNode::getCode(); + } + }; + + struct BlockNode : public CodeNode { + MachineBasicBlock *getCode() const { + return CodeNode::getCode(); + } + + void addPhi(NodeAddr PA, const DataFlowGraph &G); + }; + + struct FuncNode : public CodeNode { + MachineFunction *getCode() const { + return CodeNode::getCode(); + } + + NodeAddr findBlock(const MachineBasicBlock *BB, + const DataFlowGraph &G) const; + NodeAddr getEntryBlock(const DataFlowGraph &G); + }; + + struct DataFlowGraph { + DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii, + const TargetRegisterInfo &tri, const MachineDominatorTree &mdt, + const MachineDominanceFrontier &mdf, const TargetOperandInfo &toi); + + NodeBase *ptr(NodeId N) const; + template T ptr(NodeId N) const { + return static_cast(ptr(N)); + } + + NodeId id(const NodeBase *P) const; + + template NodeAddr addr(NodeId N) const { + return { ptr(N), N }; + } + + NodeAddr getFunc() const { return Func; } + MachineFunction &getMF() const { return MF; } + const TargetInstrInfo &getTII() const { return TII; } + const TargetRegisterInfo &getTRI() const { return TRI; } + const PhysicalRegisterInfo &getPRI() const { return PRI; } + const MachineDominatorTree &getDT() const { return MDT; } + const MachineDominanceFrontier &getDF() const { return MDF; } + const RegisterAggr &getLiveIns() const { return LiveIns; } + + struct DefStack { + DefStack() = default; + + bool empty() const { return Stack.empty() || top() == bottom(); } + + private: + typedef NodeAddr value_type; + struct Iterator { + typedef DefStack::value_type value_type; + + Iterator &up() { Pos = DS.nextUp(Pos); return *this; } + Iterator &down() { Pos = DS.nextDown(Pos); return *this; } + + value_type operator*() const { + assert(Pos >= 1); + return DS.Stack[Pos-1]; + } + const value_type *operator->() const { + assert(Pos >= 1); + return &DS.Stack[Pos-1]; + } + bool operator==(const Iterator &It) const { return Pos == It.Pos; } + bool operator!=(const Iterator &It) const { return Pos != It.Pos; } + + private: + Iterator(const DefStack &S, bool Top); + + // Pos-1 is the index in the StorageType object that corresponds to + // the top of the DefStack. + const DefStack &DS; + unsigned Pos; + friend struct DefStack; + }; + + public: + typedef Iterator iterator; + iterator top() const { return Iterator(*this, true); } + iterator bottom() const { return Iterator(*this, false); } + unsigned size() const; + + void push(NodeAddr DA) { Stack.push_back(DA); } + void pop(); + void start_block(NodeId N); + void clear_block(NodeId N); + + private: + friend struct Iterator; + typedef std::vector StorageType; + + bool isDelimiter(const StorageType::value_type &P, NodeId N = 0) const { + return (P.Addr == nullptr) && (N == 0 || P.Id == N); + } + + unsigned nextUp(unsigned P) const; + unsigned nextDown(unsigned P) const; + + StorageType Stack; + }; + + // Make this std::unordered_map for speed of accessing elements. + // Map: Register (physical or virtual) -> DefStack + typedef std::unordered_map DefStackMap; + + void build(unsigned Options = BuildOptions::None); + void pushDefs(NodeAddr IA, DefStackMap &DM); + void markBlock(NodeId B, DefStackMap &DefM); + void releaseBlock(NodeId B, DefStackMap &DefM); + + PackedRegisterRef pack(RegisterRef RR) { + return { RR.Reg, LMI.getIndexForLaneMask(RR.Mask) }; + } + PackedRegisterRef pack(RegisterRef RR) const { + return { RR.Reg, LMI.getIndexForLaneMask(RR.Mask) }; + } + RegisterRef unpack(PackedRegisterRef PR) const { + return RegisterRef(PR.Reg, LMI.getLaneMaskForIndex(PR.MaskId)); + } + + RegisterRef makeRegRef(unsigned Reg, unsigned Sub) const; + RegisterRef makeRegRef(const MachineOperand &Op) const; + RegisterRef normalizeRef(RegisterRef RR) const; + RegisterRef restrictRef(RegisterRef AR, RegisterRef BR) const; + + NodeAddr getNextRelated(NodeAddr IA, + NodeAddr RA) const; + NodeAddr getNextImp(NodeAddr IA, + NodeAddr RA, bool Create); + NodeAddr getNextImp(NodeAddr IA, + NodeAddr RA) const; + NodeAddr getNextShadow(NodeAddr IA, + NodeAddr RA, bool Create); + NodeAddr getNextShadow(NodeAddr IA, + NodeAddr RA) const; + + NodeList getRelatedRefs(NodeAddr IA, + NodeAddr RA) const; + + void unlinkUse(NodeAddr UA, bool RemoveFromOwner) { + unlinkUseDF(UA); + if (RemoveFromOwner) + removeFromOwner(UA); + } + + void unlinkDef(NodeAddr DA, bool RemoveFromOwner) { + unlinkDefDF(DA); + if (RemoveFromOwner) + removeFromOwner(DA); + } + + // Some useful filters. + template + static bool IsRef(const NodeAddr BA) { + return BA.Addr->getType() == NodeAttrs::Ref && + BA.Addr->getKind() == Kind; + } + + template + static bool IsCode(const NodeAddr BA) { + return BA.Addr->getType() == NodeAttrs::Code && + BA.Addr->getKind() == Kind; + } + + static bool IsDef(const NodeAddr BA) { + return BA.Addr->getType() == NodeAttrs::Ref && + BA.Addr->getKind() == NodeAttrs::Def; + } + + static bool IsUse(const NodeAddr BA) { + return BA.Addr->getType() == NodeAttrs::Ref && + BA.Addr->getKind() == NodeAttrs::Use; + } + + static bool IsPhi(const NodeAddr BA) { + return BA.Addr->getType() == NodeAttrs::Code && + BA.Addr->getKind() == NodeAttrs::Phi; + } + + static bool IsPreservingDef(const NodeAddr DA) { + uint16_t Flags = DA.Addr->getFlags(); + return (Flags & NodeAttrs::Preserving) && !(Flags & NodeAttrs::Undef); + } + + private: + void reset(); + + RegisterSet getLandingPadLiveIns() const; + + NodeAddr newNode(uint16_t Attrs); + NodeAddr cloneNode(const NodeAddr B); + NodeAddr newUse(NodeAddr Owner, + MachineOperand &Op, uint16_t Flags = NodeAttrs::None); + NodeAddr newPhiUse(NodeAddr Owner, + RegisterRef RR, NodeAddr PredB, + uint16_t Flags = NodeAttrs::PhiRef); + NodeAddr newDef(NodeAddr Owner, + MachineOperand &Op, uint16_t Flags = NodeAttrs::None); + NodeAddr newDef(NodeAddr Owner, + RegisterRef RR, uint16_t Flags = NodeAttrs::PhiRef); + NodeAddr newPhi(NodeAddr Owner); + NodeAddr newStmt(NodeAddr Owner, + MachineInstr *MI); + NodeAddr newBlock(NodeAddr Owner, + MachineBasicBlock *BB); + NodeAddr newFunc(MachineFunction *MF); + + template + std::pair,NodeAddr> + locateNextRef(NodeAddr IA, NodeAddr RA, + Predicate P) const; + + typedef std::map BlockRefsMap; + + void buildStmt(NodeAddr BA, MachineInstr &In); + void buildBlockRefs(NodeAddr BA, BlockRefsMap &RefM); + void recordDefsForDF(BlockRefsMap &PhiM, BlockRefsMap &RefM, + NodeAddr BA); + void buildPhis(BlockRefsMap &PhiM, BlockRefsMap &RefM, + NodeAddr BA); + void removeUnusedPhis(); + + template void linkRefUp(NodeAddr IA, + NodeAddr TA, DefStack &DS); + void linkStmtRefs(DefStackMap &DefM, NodeAddr SA); + void linkBlockRefs(DefStackMap &DefM, NodeAddr BA); + + void unlinkUseDF(NodeAddr UA); + void unlinkDefDF(NodeAddr DA); + + void removeFromOwner(NodeAddr RA) { + NodeAddr IA = RA.Addr->getOwner(*this); + IA.Addr->removeMember(RA, *this); + } + + NodeAddr findBlock(MachineBasicBlock *BB) { + return BlockNodes[BB]; + } + + MachineFunction &MF; + const TargetInstrInfo &TII; + const TargetRegisterInfo &TRI; + const PhysicalRegisterInfo PRI; + const MachineDominatorTree &MDT; + const MachineDominanceFrontier &MDF; + const TargetOperandInfo &TOI; + + RegisterAggr LiveIns; + NodeAddr Func; + NodeAllocator Memory; + // Local map: MachineBasicBlock -> NodeAddr + std::map> BlockNodes; + // Lane mask map. + LaneMaskIndex LMI; + }; // struct DataFlowGraph + + template + NodeAddr RefNode::getNextRef(RegisterRef RR, Predicate P, + bool NextOnly, const DataFlowGraph &G) { + // Get the "Next" reference in the circular list that references RR and + // satisfies predicate "Pred". + auto NA = G.addr(getNext()); + + while (NA.Addr != this) { + if (NA.Addr->getType() == NodeAttrs::Ref) { + NodeAddr RA = NA; + if (RA.Addr->getRegRef(G) == RR && P(NA)) + return NA; + if (NextOnly) + break; + NA = G.addr(NA.Addr->getNext()); + } else { + // We've hit the beginning of the chain. + assert(NA.Addr->getType() == NodeAttrs::Code); + NodeAddr CA = NA; + NA = CA.Addr->getFirstMember(G); + } + } + // Return the equivalent of "nullptr" if such a node was not found. + return NodeAddr(); + } + + template + NodeList CodeNode::members_if(Predicate P, const DataFlowGraph &G) const { + NodeList MM; + auto M = getFirstMember(G); + if (M.Id == 0) + return MM; + + while (M.Addr != this) { + if (P(M)) + MM.push_back(M); + M = G.addr(M.Addr->getNext()); + } + return MM; + } + + + template struct Print; + template + raw_ostream &operator<< (raw_ostream &OS, const Print &P); + + template + struct Print { + Print(const T &x, const DataFlowGraph &g) : Obj(x), G(g) {} + const T &Obj; + const DataFlowGraph &G; + }; + + template + struct PrintNode : Print> { + PrintNode(const NodeAddr &x, const DataFlowGraph &g) + : Print>(x, g) {} + }; + +} // end namespace rdf + +} // end namespace llvm + +#endif // LLVM_CODEGEN_RDFGRAPH_H Index: include/llvm/CodeGen/RDFLiveness.h =================================================================== --- /dev/null +++ include/llvm/CodeGen/RDFLiveness.h @@ -0,0 +1,135 @@ +//===--- RDFLiveness.h ----------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Recalculate the liveness information given a data flow graph. +// This includes block live-ins and kill flags. + +#ifndef LLVM_CODEGEN_RDFLIVENESS_H +#define LLVM_CODEGEN_RDFLIVENESS_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/CodeGen/RDFGraph.h" +#include + +using namespace llvm; + +namespace llvm { + class MachineBasicBlock; + class MachineFunction; + class MachineRegisterInfo; + class TargetRegisterInfo; + class MachineDominatorTree; + class MachineDominanceFrontier; + +namespace rdf { + struct Liveness { + public: + // This is really a std::map, except that it provides a non-trivial + // default constructor to the element accessed via []. + struct LiveMapType { + LiveMapType(const PhysicalRegisterInfo &pri) : Empty(pri) {} + + RegisterAggr &operator[] (MachineBasicBlock *B) { + return Map.emplace(B, Empty).first->second; + } + private: + RegisterAggr Empty; + std::map Map; + }; + + typedef std::pair NodeRef; + typedef std::set NodeRefSet; + // RegisterId in RefMap must be normalized. + typedef std::map RefMap; + + Liveness(MachineRegisterInfo &mri, const DataFlowGraph &g) + : DFG(g), TRI(g.getTRI()), PRI(g.getPRI()), MDT(g.getDT()), + MDF(g.getDF()), MRI(mri), LiveMap(g.getPRI()), Empty(), + NoRegs(g.getPRI()), Trace(false) {} + + NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr RefA, + bool FullChain, const RegisterAggr &DefRRs); + NodeList getAllReachingDefs(NodeAddr RefA) { + return getAllReachingDefs(RefA.Addr->getRegRef(DFG), RefA, false, NoRegs); + } + NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr RefA) { + return getAllReachingDefs(RefRR, RefA, false, NoRegs); + } + NodeSet getAllReachingDefsRec(RegisterRef RefRR, NodeAddr RefA, + NodeSet &Visited, const NodeSet &Defs); + NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr DefA, + const RegisterAggr &DefRRs); + NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr DefA) { + return getAllReachedUses(RefRR, DefA, NoRegs); + } + + LiveMapType &getLiveMap() { return LiveMap; } + const LiveMapType &getLiveMap() const { return LiveMap; } + const RefMap &getRealUses(NodeId P) const { + auto F = RealUseMap.find(P); + return F == RealUseMap.end() ? Empty : F->second; + } + + void computePhiInfo(); + void computeLiveIns(); + void resetLiveIns(); + void resetKills(); + void resetKills(MachineBasicBlock *B); + + void trace(bool T) { Trace = T; } + + private: + const DataFlowGraph &DFG; + const TargetRegisterInfo &TRI; + const PhysicalRegisterInfo &PRI; + const MachineDominatorTree &MDT; + const MachineDominanceFrontier &MDF; + MachineRegisterInfo &MRI; + LiveMapType LiveMap; + const RefMap Empty; + const RegisterAggr NoRegs; + bool Trace; + + // Cache of mapping from node ids (for RefNodes) to the containing + // basic blocks. Not computing it each time for each node reduces + // the liveness calculation time by a large fraction. + typedef DenseMap NodeBlockMap; + NodeBlockMap NBMap; + + // Phi information: + // + // RealUseMap + // map: NodeId -> (map: RegisterId -> NodeRefSet) + // phi id -> (map: register -> set of reached non-phi uses) + std::map RealUseMap; + + // Inverse iterated dominance frontier. + std::map> IIDF; + + // Live on entry. + std::map PhiLON; + + // Phi uses are considered to be located at the end of the block that + // they are associated with. The reaching def of a phi use dominates the + // block that the use corresponds to, but not the block that contains + // the phi itself. To include these uses in the liveness propagation (up + // the dominator tree), create a map: block -> set of uses live on exit. + std::map PhiLOX; + + bool isRestrictedToRef(NodeAddr IA, NodeAddr RA, + RegisterRef RR) const; + RegisterRef getRestrictedRegRef(NodeAddr RA) const; + MachineBasicBlock *getBlockWithRef(NodeId RN) const; + void traverse(MachineBasicBlock *B, RefMap &LiveIn); + void emptify(RefMap &M); + }; +} // namespace rdf +} // namespace llvm + +#endif // LLVM_CODEGEN_RDFLIVENESS_H Index: include/llvm/CodeGen/RDFRegisters.h =================================================================== --- /dev/null +++ include/llvm/CodeGen/RDFRegisters.h @@ -0,0 +1,170 @@ +//===--- RDFRegisters.h -----------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_RDFREGISTERS_H +#define LLVM_CODEGEN_RDFREGISTERS_H + +#include "llvm/ADT/BitVector.h" +#include "llvm/Target/TargetRegisterInfo.h" + +#include +#include +#include + +namespace llvm { +namespace rdf { + + typedef uint32_t RegisterId; + + // Template class for a map translating uint32_t into arbitrary types. + // The map will act like an indexed set: upon insertion of a new object, + // it will automatically assign a new index to it. Index of 0 is treated + // as invalid and is never allocated. + template + struct IndexedSet { + IndexedSet() : Map() { Map.reserve(N); } + + T get(uint32_t Idx) const { + // Index Idx corresponds to Map[Idx-1]. + assert(Idx != 0 && !Map.empty() && Idx-1 < Map.size()); + return Map[Idx-1]; + } + + uint32_t insert(T Val) { + // Linear search. + auto F = llvm::find(Map, Val); + if (F != Map.end()) + return F - Map.begin() + 1; + Map.push_back(Val); + return Map.size(); // Return actual_index + 1. + } + + uint32_t find(T Val) const { + auto F = llvm::find(Map, Val); + assert(F != Map.end()); + return F - Map.begin() + 1; + } + + private: + std::vector Map; + }; + + struct RegisterRef { + RegisterId Reg = 0; + LaneBitmask Mask = LaneBitmask::getNone(); + + RegisterRef() = default; + explicit RegisterRef(RegisterId R, LaneBitmask M = LaneBitmask::getAll()) + : Reg(R), Mask(R != 0 ? M : LaneBitmask::getNone()) {} + + operator bool() const { + return Reg != 0 && Mask.any(); + } + bool operator== (const RegisterRef &RR) const { + return Reg == RR.Reg && Mask == RR.Mask; + } + bool operator!= (const RegisterRef &RR) const { + return !operator==(RR); + } + bool operator< (const RegisterRef &RR) const { + return Reg < RR.Reg || (Reg == RR.Reg && Mask < RR.Mask); + } + }; + + + struct PhysicalRegisterInfo { + PhysicalRegisterInfo(const TargetRegisterInfo &tri, + const MachineFunction &mf); + + static bool isRegMaskId(RegisterId R) { + return TargetRegisterInfo::isStackSlot(R); + } + RegisterId getRegMaskId(const uint32_t *RM) const { + return TargetRegisterInfo::index2StackSlot(RegMasks.find(RM)); + } + const uint32_t *getRegMaskBits(RegisterId R) const { + return RegMasks.get(TargetRegisterInfo::stackSlot2Index(R)); + } + + bool alias(RegisterRef RA, RegisterRef RB) const { + if (!isRegMaskId(RA.Reg)) + return !isRegMaskId(RB.Reg) ? aliasRR(RA, RB) : aliasRM(RA, RB); + return !isRegMaskId(RB.Reg) ? aliasRM(RB, RA) : aliasMM(RA, RB); + } + std::set getAliasSet(RegisterId Reg) const; + + const TargetRegisterInfo &getTRI() const { return TRI; } + +// private: + struct RegInfo { + unsigned MaxSuper = 0; + const TargetRegisterClass *RegClass = nullptr; + }; + + const TargetRegisterInfo &TRI; + std::vector RegInfos; + IndexedSet RegMasks; + + bool aliasRR(RegisterRef RA, RegisterRef RB) const; + bool aliasRM(RegisterRef RR, RegisterRef RM) const; + bool aliasMM(RegisterRef RM, RegisterRef RN) const; + }; + + + struct RegisterAggr { + RegisterAggr(const PhysicalRegisterInfo &pri) + : ExpAliasUnits(pri.getTRI().getNumRegUnits()), PRI(pri) {} + RegisterAggr(const RegisterAggr &RG) = default; + + bool empty() const { return Masks.empty(); } + bool hasAliasOf(RegisterRef RR) const; + bool hasCoverOf(RegisterRef RR) const; + static bool isCoverOf(RegisterRef RA, RegisterRef RB, + const PhysicalRegisterInfo &PRI) { + return RegisterAggr(PRI).insert(RA).hasCoverOf(RB); + } + + RegisterAggr &insert(RegisterRef RR); + RegisterAggr &insert(const RegisterAggr &RG); + RegisterAggr &clear(RegisterRef RR); + RegisterAggr &clear(const RegisterAggr &RG); + + RegisterRef clearIn(RegisterRef RR) const; + + void print(raw_ostream &OS) const; + + private: + typedef std::unordered_map MapType; + + public: + typedef MapType::const_iterator iterator; + iterator begin() const { return Masks.begin(); } + iterator end() const { return Masks.end(); } + RegisterRef normalize(RegisterRef RR) const; + + private: + MapType Masks; + BitVector ExpAliasUnits; // Register units for explicit aliases. + bool CheckUnits = false; + const PhysicalRegisterInfo &PRI; + }; + + + // Optionally print the lane mask, if it is not ~0. + struct PrintLaneMaskOpt { + PrintLaneMaskOpt(LaneBitmask M) : Mask(M) {} + LaneBitmask Mask; + }; + raw_ostream &operator<< (raw_ostream &OS, const PrintLaneMaskOpt &P); + +} // namespace rdf +} // namespace llvm + +#endif // LLVM_CODEGEN_RDFREGISTERS_H + Index: lib/CodeGen/CMakeLists.txt =================================================================== --- lib/CodeGen/CMakeLists.txt +++ lib/CodeGen/CMakeLists.txt @@ -96,6 +96,9 @@ ProcessImplicitDefs.cpp PrologEpilogInserter.cpp PseudoSourceValue.cpp + RDFGraph.cpp + RDFLiveness.cpp + RDFRegisters.cpp RegAllocBase.cpp RegAllocBasic.cpp RegAllocFast.cpp Index: lib/CodeGen/RDFGraph.cpp =================================================================== --- /dev/null +++ lib/CodeGen/RDFGraph.cpp @@ -0,0 +1,1839 @@ +//===--- RDFGraph.cpp -----------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Target-independent, SSA-based data flow graph for register data flow (RDF). +// +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/STLExtras.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/IR/Function.h" +#include "llvm/MC/LaneBitmask.h" +#include "llvm/MC/MCInstrDesc.h" +#include "llvm/MC/MCRegisterInfo.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetLowering.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include +#include +#include +#include +#include +#include +#include + +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; +} + +template<> +raw_ostream &operator<< (raw_ostream &OS, const Print &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; +} + +template<> +raw_ostream &operator<< (raw_ostream &OS, const Print &P) { + auto NA = P.G.addr(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 RA, + const DataFlowGraph &G) { + OS << Print(RA.Id, G) << '<' + << Print(RA.Addr->getRegRef(G), G) << '>'; + if (RA.Addr->getFlags() & NodeAttrs::Fixed) + OS << '!'; +} + +template<> +raw_ostream &operator<< (raw_ostream &OS, const Print> &P) { + printRefHeader(OS, P.Obj, P.G); + OS << '('; + if (NodeId N = P.Obj.Addr->getReachingDef()) + OS << Print(N, P.G); + OS << ','; + if (NodeId N = P.Obj.Addr->getReachedDef()) + OS << Print(N, P.G); + OS << ','; + if (NodeId N = P.Obj.Addr->getReachedUse()) + OS << Print(N, P.G); + OS << "):"; + if (NodeId N = P.Obj.Addr->getSibling()) + OS << Print(N, P.G); + return OS; +} + +template<> +raw_ostream &operator<< (raw_ostream &OS, const Print> &P) { + printRefHeader(OS, P.Obj, P.G); + OS << '('; + if (NodeId N = P.Obj.Addr->getReachingDef()) + OS << Print(N, P.G); + OS << "):"; + if (NodeId N = P.Obj.Addr->getSibling()) + OS << Print(N, P.G); + return OS; +} + +template<> +raw_ostream &operator<< (raw_ostream &OS, + const Print> &P) { + printRefHeader(OS, P.Obj, P.G); + OS << '('; + if (NodeId N = P.Obj.Addr->getReachingDef()) + OS << Print(N, P.G); + OS << ','; + if (NodeId N = P.Obj.Addr->getPredecessor()) + OS << Print(N, P.G); + OS << "):"; + if (NodeId N = P.Obj.Addr->getSibling()) + OS << Print(N, P.G); + return OS; +} + +template<> +raw_ostream &operator<< (raw_ostream &OS, const Print> &P) { + switch (P.Obj.Addr->getKind()) { + case NodeAttrs::Def: + OS << PrintNode(P.Obj, P.G); + break; + case NodeAttrs::Use: + if (P.Obj.Addr->getFlags() & NodeAttrs::PhiRef) + OS << PrintNode(P.Obj, P.G); + else + OS << PrintNode(P.Obj, P.G); + break; + } + return OS; +} + +template<> +raw_ostream &operator<< (raw_ostream &OS, const Print &P) { + unsigned N = P.Obj.size(); + for (auto I : P.Obj) { + OS << Print(I.Id, P.G); + if (--N) + OS << ' '; + } + return OS; +} + +template<> +raw_ostream &operator<< (raw_ostream &OS, const Print &P) { + unsigned N = P.Obj.size(); + for (auto I : P.Obj) { + OS << Print(I, P.G); + if (--N) + OS << ' '; + } + return OS; +} + +namespace { + + template + struct PrintListV { + PrintListV(const NodeList &L, const DataFlowGraph &G) : List(L), G(G) {} + + typedef T Type; + const NodeList &List; + const DataFlowGraph &G; + }; + + template + raw_ostream &operator<< (raw_ostream &OS, const PrintListV &P) { + unsigned N = P.List.size(); + for (NodeAddr A : P.List) { + OS << PrintNode(A, P.G); + if (--N) + OS << ", "; + } + return OS; + } + +} // end anonymous namespace + +template<> +raw_ostream &operator<< (raw_ostream &OS, const Print> &P) { + OS << Print(P.Obj.Id, P.G) << ": phi [" + << PrintListV(P.Obj.Addr->members(P.G), P.G) << ']'; + return OS; +} + +template<> +raw_ostream &operator<< (raw_ostream &OS, + const Print> &P) { + const MachineInstr &MI = *P.Obj.Addr->getCode(); + unsigned Opc = MI.getOpcode(); + OS << Print(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 << "BB#" << T->getMBB()->getNumber(); + else if (T->isGlobal()) + OS << T->getGlobal()->getName(); + else if (T->isSymbol()) + OS << T->getSymbolName(); + } + } + OS << " [" << PrintListV(P.Obj.Addr->members(P.G), P.G) << ']'; + return OS; +} + +template<> +raw_ostream &operator<< (raw_ostream &OS, + const Print> &P) { + switch (P.Obj.Addr->getKind()) { + case NodeAttrs::Phi: + OS << PrintNode(P.Obj, P.G); + break; + case NodeAttrs::Stmt: + OS << PrintNode(P.Obj, P.G); + break; + default: + OS << "instr? " << Print(P.Obj.Id, P.G); + break; + } + return OS; +} + +template<> +raw_ostream &operator<< (raw_ostream &OS, + const Print> &P) { + MachineBasicBlock *BB = P.Obj.Addr->getCode(); + unsigned NP = BB->pred_size(); + std::vector Ns; + auto PrintBBs = [&OS] (std::vector Ns) -> void { + unsigned N = Ns.size(); + for (int I : Ns) { + OS << "BB#" << I; + if (--N) + OS << ", "; + } + }; + + OS << Print(P.Obj.Id, P.G) << ": --- BB#" << BB->getNumber() + << " --- 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(I, P.G) << '\n'; + return OS; +} + +template<> +raw_ostream &operator<< (raw_ostream &OS, + const Print> &P) { + OS << "DFG dump:[\n" << Print(P.Obj.Id, P.G) << ": Function: " + << P.Obj.Addr->getCode()->getName() << '\n'; + for (auto I : P.Obj.Addr->members(P.G)) + OS << PrintNode(I, P.G) << '\n'; + OS << "]\n"; + return OS; +} + +template<> +raw_ostream &operator<< (raw_ostream &OS, const Print &P) { + OS << '{'; + for (auto I : P.Obj) + OS << ' ' << Print(I, P.G); + OS << " }"; + return OS; +} + +template<> +raw_ostream &operator<< (raw_ostream &OS, const Print &P) { + P.Obj.print(OS); + return OS; +} + +template<> +raw_ostream &operator<< (raw_ostream &OS, + const Print &P) { + for (auto I = P.Obj.top(), E = P.Obj.bottom(); I != E; ) { + OS << Print(I->Id, P.G) + << '<' << Print(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(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 NodeAllocator::New() { + if (needNewBlock()) + startNewBlock(); + + uint32_t ActiveB = Blocks.size()-1; + uint32_t Index = (ActiveEnd - Blocks[ActiveB])/NodeMemSize; + NodeAddr NA = { reinterpret_cast(ActiveEnd), + makeId(ActiveB, Index) }; + ActiveEnd += NodeMemSize; + return NA; +} + +NodeId NodeAllocator::id(const NodeBase *P) const { + uintptr_t A = reinterpret_cast(P); + for (unsigned i = 0, n = Blocks.size(); i != n; ++i) { + uintptr_t B = reinterpret_cast(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 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 RefNode::getOwner(const DataFlowGraph &G) { + NodeAddr NA = G.addr(getNext()); + + while (NA.Addr != this) { + if (NA.Addr->getType() == NodeAttrs::Code) + return NA; + NA = G.addr(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 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 DA) { + Ref.RD = DA.Id; + Ref.Sib = DA.Addr->getReachedUse(); + DA.Addr->setReachedUse(Self); +} + +// Get the first member of the code node. +NodeAddr CodeNode::getFirstMember(const DataFlowGraph &G) const { + if (Code.FirstM == 0) + return NodeAddr(); + return G.addr(Code.FirstM); +} + +// Get the last member of the code node. +NodeAddr CodeNode::getLastMember(const DataFlowGraph &G) const { + if (Code.LastM == 0) + return NodeAddr(); + return G.addr(Code.LastM); +} + +// Add node NA at the end of the member list of the given code node. +void CodeNode::addMember(NodeAddr NA, const DataFlowGraph &G) { + NodeAddr 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 MA, NodeAddr 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 NA, const DataFlowGraph &G) { + NodeAddr 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(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) -> bool { return true; }; + return members_if(True, G); +} + +// Return the owner of the given instr node. +NodeAddr InstrNode::getOwner(const DataFlowGraph &G) { + NodeAddr NA = G.addr(getNext()); + + while (NA.Addr != this) { + assert(NA.Addr->getType() == NodeAttrs::Code); + if (NA.Addr->getKind() == NodeAttrs::Block) + return NA; + NA = G.addr(NA.Addr->getNext()); + } + llvm_unreachable("No owner in circular list"); +} + +// Add the phi node PA to the given block node. +void BlockNode::addPhi(NodeAddr PA, const DataFlowGraph &G) { + NodeAddr 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 MN = M; + do { + M = MN; + MN = G.addr(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 FuncNode::findBlock(const MachineBasicBlock *BB, + const DataFlowGraph &G) const { + auto EqBB = [BB] (NodeAddr NA) -> bool { + return NodeAddr(NA).Addr->getCode() == BB; + }; + NodeList Ms = members_if(EqBB, G); + if (!Ms.empty()) + return Ms[0]; + return NodeAddr(); +} + +// Get the block node for the entry block in the given function. +NodeAddr 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 { + if (In.isCall()) + if (In.getOperand(OpNum).isImplicit()) + 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; + RegisterId 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(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 (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 DataFlowGraph::newNode(uint16_t Attrs) { + NodeAddr 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 DataFlowGraph::cloneNode(const NodeAddr B) { + NodeAddr 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 RA = NA; + RA.Addr->setReachingDef(0); + RA.Addr->setSibling(0); + if (NA.Addr->getKind() == NodeAttrs::Def) { + NodeAddr DA = NA; + DA.Addr->setReachedDef(0); + DA.Addr->setReachedUse(0); + } + } + return NA; +} + +// Allocation routines for specific node types/kinds. + +NodeAddr DataFlowGraph::newUse(NodeAddr Owner, + MachineOperand &Op, uint16_t Flags) { + NodeAddr UA = newNode(NodeAttrs::Ref | NodeAttrs::Use | Flags); + UA.Addr->setRegRef(&Op, *this); + return UA; +} + +NodeAddr DataFlowGraph::newPhiUse(NodeAddr Owner, + RegisterRef RR, NodeAddr PredB, uint16_t Flags) { + NodeAddr PUA = newNode(NodeAttrs::Ref | NodeAttrs::Use | Flags); + assert(Flags & NodeAttrs::PhiRef); + PUA.Addr->setRegRef(RR, *this); + PUA.Addr->setPredecessor(PredB.Id); + return PUA; +} + +NodeAddr DataFlowGraph::newDef(NodeAddr Owner, + MachineOperand &Op, uint16_t Flags) { + NodeAddr DA = newNode(NodeAttrs::Ref | NodeAttrs::Def | Flags); + DA.Addr->setRegRef(&Op, *this); + return DA; +} + +NodeAddr DataFlowGraph::newDef(NodeAddr Owner, + RegisterRef RR, uint16_t Flags) { + NodeAddr DA = newNode(NodeAttrs::Ref | NodeAttrs::Def | Flags); + assert(Flags & NodeAttrs::PhiRef); + DA.Addr->setRegRef(RR, *this); + return DA; +} + +NodeAddr DataFlowGraph::newPhi(NodeAddr Owner) { + NodeAddr PA = newNode(NodeAttrs::Code | NodeAttrs::Phi); + Owner.Addr->addPhi(PA, *this); + return PA; +} + +NodeAddr DataFlowGraph::newStmt(NodeAddr Owner, + MachineInstr *MI) { + NodeAddr SA = newNode(NodeAttrs::Code | NodeAttrs::Stmt); + SA.Addr->setCode(MI); + Owner.Addr->addMember(SA, *this); + return SA; +} + +NodeAddr DataFlowGraph::newBlock(NodeAddr Owner, + MachineBasicBlock *BB) { + NodeAddr BA = newNode(NodeAttrs::Code | NodeAttrs::Block); + BA.Addr->setCode(BB); + Owner.Addr->addMember(BA, *this); + return BA; +} + +NodeAddr DataFlowGraph::newFunc(MachineFunction *MF) { + NodeAddr 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 BA = newBlock(Func, &B); + BlockNodes.insert(std::make_pair(&B, BA)); + for (MachineInstr &I : B) { + if (I.isDebugValue()) + continue; + buildStmt(BA, I); + } + } + + NodeAddr EA = Func.Addr->getEntryBlock(*this); + NodeList Blocks = Func.Addr->members(*this); + + // Collect information about block references. + BlockRefsMap RefM; + buildBlockRefs(EA, RefM); + + // 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 (auto I = MRI.livein_begin(), E = MRI.livein_end(); I != E; ++I) + LiveIns.insert(RegisterRef(I->first)); + 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 P : LiveIns) { + NodeAddr PA = newPhi(EA); + uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving; + RegisterRef RR(P.first, P.second); + NodeAddr 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 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 PA = newPhi(BA); + uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving; + // Add def: + NodeAddr DA = newDef(PA, RR, PhiFlags); + PA.Addr->addMember(DA, *this); + // Add uses (no reaching defs for phi uses): + for (NodeAddr PBA : Preds) { + NodeAddr 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 BA : Blocks) + recordDefsForDF(PhiM, RefM, BA); + for (NodeAddr BA : Blocks) + buildPhis(PhiM, RefM, 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) || + TargetRegisterInfo::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::normalizeRef(RegisterRef RR) const { + // FIXME copied from RegisterAggr + if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) + return RR; + const TargetRegisterClass *RC = PRI.RegInfos[RR.Reg].RegClass; + LaneBitmask RCMask = RC != nullptr ? RC->LaneMask : LaneBitmask(0x00000001); + LaneBitmask Common = RR.Mask & RCMask; + + RegisterId SuperReg = PRI.RegInfos[RR.Reg].MaxSuper; +// Ex: IP/EIP/RIP +// assert(RC != nullptr || RR.Reg == SuperReg); + uint32_t Sub = PRI.getTRI().getSubRegIndex(SuperReg, RR.Reg); + LaneBitmask SuperMask = PRI.getTRI().composeSubRegIndexLaneMask(Sub, Common); + return RegisterRef(SuperReg, SuperMask); +} + +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 = normalizeRef(AR); + RegisterRef NBR = normalizeRef(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::pushDefs(NodeAddr IA, DefStackMap &DefM) { + NodeList Defs = IA.Addr->members_if(IsDef, *this); + NodeSet Visited; +#ifndef NDEBUG + RegisterSet 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 DA : Defs) { + if (Visited.count(DA.Id)) + continue; + + NodeList Rel = getRelatedRefs(IA, DA); + NodeAddr 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).second) { + MachineInstr *MI = NodeAddr(IA).Addr->getCode(); + dbgs() << "Multiple definitions of register: " + << Print(RR, *this) << " in\n " << *MI + << "in BB#" << MI->getParent()->getNumber() << '\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 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 IA, + NodeAddr 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(); +} + +// 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 DataFlowGraph::getNextRelated(NodeAddr IA, + NodeAddr RA) const { + assert(IA.Id != 0 && RA.Id != 0); + + auto Related = [this,RA](NodeAddr 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 TA) -> bool { + return Related(TA) && + &RA.Addr->getOp() == &TA.Addr->getOp(); + }; + auto RelatedPhi = [&Related,RA](NodeAddr TA) -> bool { + if (!Related(TA)) + return false; + if (TA.Addr->getKind() != NodeAttrs::Use) + return true; + // For phi uses, compare predecessor blocks. + const NodeAddr TUA = TA; + const NodeAddr 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 +std::pair,NodeAddr> +DataFlowGraph::locateNextRef(NodeAddr IA, NodeAddr RA, + Predicate P) const { + assert(IA.Id != 0 && RA.Id != 0); + + NodeAddr 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()); +} + +// Get the next shadow node in IA corresponding to RA, and optionally create +// such a node if it does not exist. +NodeAddr DataFlowGraph::getNextShadow(NodeAddr IA, + NodeAddr RA, bool Create) { + assert(IA.Id != 0 && RA.Id != 0); + + uint16_t Flags = RA.Addr->getFlags() | NodeAttrs::Shadow; + auto IsShadow = [Flags] (NodeAddr 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 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 DataFlowGraph::getNextShadow(NodeAddr IA, + NodeAddr RA) const { + assert(IA.Id != 0 && RA.Id != 0); + uint16_t Flags = RA.Addr->getFlags() | NodeAttrs::Shadow; + auto IsShadow = [Flags] (NodeAddr 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 BA, MachineInstr &In) { + NodeAddr 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; + }; + + // Collect a set of registers that this instruction implicitly uses + // or defines. Implicit operands from an instruction will be ignored + // unless they are listed here. + RegisterSet ImpUses, ImpDefs; + if (const uint16_t *ImpD = In.getDesc().getImplicitDefs()) + while (uint16_t R = *ImpD++) + ImpDefs.insert(RegisterRef(R)); + if (const uint16_t *ImpU = In.getDesc().getImplicitUses()) + while (uint16_t R = *ImpU++) + ImpUses.insert(RegisterRef(R)); + + bool IsCall = isCall(In); + bool NeedsImplicit = IsCall || In.isInlineAsm() || In.isReturn(); + bool IsPredicated = TII.isPredicated(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; + unsigned R = Op.getReg(); + if (!R || !TargetRegisterInfo::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 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 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; + unsigned R = Op.getReg(); + if (!R || !TargetRegisterInfo::isPhysicalRegister(R) || DoneDefs.test(R)) + continue; + RegisterRef RR = makeRegRef(Op); + if (!NeedsImplicit && !ImpDefs.count(RR)) + 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, 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 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; + unsigned R = Op.getReg(); + if (!R || !TargetRegisterInfo::isPhysicalRegister(R)) + continue; + RegisterRef RR = makeRegRef(Op); + // Add implicit uses on return and call instructions, and on predicated + // instructions regardless of whether or not they appear in the instruction + // descriptor's list. + bool Implicit = Op.isImplicit(); + bool TakeImplicit = NeedsImplicit || IsPredicated; + if (Implicit && !TakeImplicit && !ImpUses.count(RR)) + continue; + uint16_t Flags = NodeAttrs::None; + if (Op.isUndef()) + Flags |= NodeAttrs::Undef; + if (TOI.isFixedReg(In, OpN)) + Flags |= NodeAttrs::Fixed; + NodeAddr UA = newUse(SA, Op, Flags); + SA.Addr->addMember(UA, *this); + } +} + +// Build a map that for each block will have the set of all references from +// that block, and from all blocks dominated by it. +void DataFlowGraph::buildBlockRefs(NodeAddr BA, + BlockRefsMap &RefM) { + RegisterSet &Refs = RefM[BA.Id]; + MachineDomTreeNode *N = MDT.getNode(BA.Addr->getCode()); + assert(N); + for (auto I : *N) { + MachineBasicBlock *SB = I->getBlock(); + NodeAddr SBA = findBlock(SB); + buildBlockRefs(SBA, RefM); + const RegisterSet &RefsS = RefM[SBA.Id]; + Refs.insert(RefsS.begin(), RefsS.end()); + } + + for (NodeAddr IA : BA.Addr->members(*this)) + for (NodeAddr RA : IA.Addr->members(*this)) + Refs.insert(RA.Addr->getRegRef(*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, BlockRefsMap &RefM, + NodeAddr 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 IA : BA.Addr->members(*this)) + for (NodeAddr 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 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()); + } + + // Get the register references that are reachable from this block. + RegisterSet &Refs = RefM[BA.Id]; + for (auto DB : IDF) { + NodeAddr DBA = findBlock(DB); + const RegisterSet &RefsD = RefM[DBA.Id]; + Refs.insert(RefsD.begin(), RefsD.end()); + } + + // Finally, add the set of defs to each block in the iterated dominance + // frontier. + for (auto DB : IDF) { + NodeAddr 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, BlockRefsMap &RefM, + NodeAddr 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 MaxRefs; + RegisterSet &RefB = RefM[BA.Id]; + for (RegisterRef I : MaxDF) + MaxRefs.push_back(MaxCoverIn(I, RefB)); + + // 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. + std::sort(MaxRefs.begin(), MaxRefs.end()); + // Remove duplicates. + auto NewEnd = std::unique(MaxRefs.begin(), MaxRefs.end()); + MaxRefs.erase(NewEnd, MaxRefs.end()); + + auto Aliased = [this,&MaxRefs](RegisterRef RR, + std::vector &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 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 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 DA = newDef(PA, RR, PhiFlags); + PA.Addr->addMember(DA, *this); + } + // Add phi uses. + for (NodeAddr PBA : Preds) { + for (unsigned X = 0; X != CS; ++X) { + RegisterRef RR = MaxRefs[ClosureIdx[X]]; + NodeAddr 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 PhiQ; + for (NodeAddr 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 M : Ms) { + if (M.Addr->getKind() != NodeAttrs::Def) + continue; + NodeAddr 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(PhiQ[0]); + PhiQ.remove(PA.Id); + NodeList Refs = PA.Addr->members(*this); + if (HasUsedDef(Refs)) + continue; + for (NodeAddr RA : Refs) { + if (NodeId RD = RA.Addr->getReachingDef()) { + auto RDA = addr(RD); + NodeAddr OA = RDA.Addr->getOwner(*this); + if (IsPhi(OA)) + PhiQ.insert(OA.Id); + } + if (RA.Addr->isDef()) + unlinkDef(RA, true); + else + unlinkUse(RA, true); + } + NodeAddr 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 +void DataFlowGraph::linkRefUp(NodeAddr IA, NodeAddr TA, + DefStack &DS) { + if (DS.empty()) + return; + RegisterRef RR = TA.Addr->getRegRef(*this); + NodeAddr 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 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. +void DataFlowGraph::linkStmtRefs(DefStackMap &DefM, NodeAddr SA) { +#ifndef NDEBUG + RegisterSet Defs; +#endif + + // Link all nodes (upwards in the data-flow) with their reaching defs. + for (NodeAddr RA : SA.Addr->members(*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(SA, RA, DS); + else if (Kind == NodeAttrs::Def) + linkRefUp(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 BA) { + // Push block delimiters. + markBlock(BA.Id, DefM); + + 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 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); + + // Push the definitions on the stack. + 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 SBA = findBlock(SB); + linkBlockRefs(DefM, SBA); + } + + // Link the phi uses from the successor blocks. + auto IsUseForBA = [BA](NodeAddr NA) -> bool { + if (NA.Addr->getKind() != NodeAttrs::Use) + return false; + assert(NA.Addr->getFlags() & NodeAttrs::PhiRef); + NodeAddr 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 SBA = findBlock(SB); + for (NodeAddr 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 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 PUA = U; + RegisterRef RR = PUA.Addr->getRegRef(*this); + linkRefUp(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 UA) { + NodeId RD = UA.Addr->getReachingDef(); + NodeId Sib = UA.Addr->getSibling(); + + if (RD == 0) { + assert(Sib == 0); + return; + } + + auto RDA = addr(RD); + auto TA = addr(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(S); + } +} + +// Remove the def node DA from any data-flow and structural links. +void DataFlowGraph::unlinkDefDF(NodeAddr 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(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 I : ReachedDefs) + I.Addr->setSibling(0); + for (NodeAddr I : ReachedUses) + I.Addr->setSibling(0); + } + for (NodeAddr I : ReachedDefs) + I.Addr->setReachingDef(RD); + for (NodeAddr 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(RD); + auto TA = addr(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(S); + } + } + + // Splice the DA's reached defs into the RDA's reached def chain. + if (!ReachedDefs.empty()) { + auto Last = NodeAddr(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(ReachedUses.back()); + Last.Addr->setSibling(RDA.Addr->getReachedUse()); + RDA.Addr->setReachedUse(ReachedUses.front().Id); + } +} Index: lib/CodeGen/RDFLiveness.cpp =================================================================== --- /dev/null +++ lib/CodeGen/RDFLiveness.cpp @@ -0,0 +1,1027 @@ +//===--- RDFLiveness.cpp --------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// 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>. +// +#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/MachineRegisterInfo.h" +#include "llvm/CodeGen/RDFGraph.h" +#include "llvm/CodeGen/RDFLiveness.h" +#include "llvm/Target/TargetRegisterInfo.h" + +using namespace llvm; +using namespace rdf; + +namespace llvm { +namespace rdf { + template<> + raw_ostream &operator<< (raw_ostream &OS, const Print &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(J->first, P.G) << PrintLaneMaskOpt(J->second); + if (++J != E) + OS << ','; + } + OS << '}'; + } + OS << " }"; + return OS; + } +} // namespace rdf +} // 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 RefA, bool FullChain, const RegisterAggr &DefRRs) { + NodeList RDefs; // Return value. + SetVector DefQ; + SetVector 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(Start); + if (NodeId RD = SNA.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(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(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 Defs; + for (NodeId N : DefQ) { + auto TA = DFG.addr(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 IA) -> MachineBasicBlock* { + if (IA.Addr->getKind() == NodeAttrs::Stmt) + return NodeAddr(IA).Addr->getCode()->getParent(); + assert(IA.Addr->getKind() == NodeAttrs::Phi); + NodeAddr PA = IA; + NodeAddr 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(A), OB = DFG.addr(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(OA).Addr->getCode(); + MachineInstr *CB = NodeAddr(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 Tmp(Owners.begin(), Owners.end()); + std::sort(Tmp.begin(), Tmp.end(), 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, *d2, ... Assume A and B are aliased (can happen in phi nodes). + // *d3 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 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(T); + bool IsPhi = DFG.IsCode(TA); + NodeList Ds; + for (NodeAddr 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(,d2,), ... Phi def d1 is covered by d2. + // d2(d1,,u3), ... + // ..., u3(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 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 DA) -> bool { + return DA.Addr->getFlags() & NodeAttrs::Dead; + }; + RDefs.resize(std::distance(RDefs.begin(), remove_if(RDefs, DeadP))); + + return RDefs; +} + + +NodeSet Liveness::getAllReachingDefsRec(RegisterRef RefRR, + NodeAddr RefA, NodeSet &Visited, const NodeSet &Defs) { + // 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(D); + if (!(DA.Addr->getFlags() & NodeAttrs::PhiRef)) + DefRRs.insert(DA.Addr->getRegRef(DFG)); + } + + NodeList RDs = getAllReachingDefs(RefRR, RefA, true, DefRRs); + if (RDs.empty()) + return Defs; + + // Make a copy of the preexisting definitions and add the newly found ones. + NodeSet TmpDefs = Defs; + for (NodeAddr R : RDs) + TmpDefs.insert(R.Id); + + NodeSet Result = Defs; + + for (NodeAddr DA : RDs) { + Result.insert(DA.Id); + if (!(DA.Addr->getFlags() & NodeAttrs::PhiRef)) + continue; + NodeAddr 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, DFG)) { + const auto &T = getAllReachingDefsRec(RefRR, U, Visited, TmpDefs); + Result.insert(T.begin(), T.end()); + } + } + + return Result; +} + + +NodeSet Liveness::getAllReachedUses(RegisterRef RefRR, + NodeAddr 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(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(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 FA = DFG.getFunc(); + NodeList Blocks = FA.Addr->members(DFG); + for (NodeAddr BA : Blocks) { + auto Ps = BA.Addr->members_if(DFG.IsCode, DFG); + Phis.insert(Phis.end(), Ps.begin(), Ps.end()); + } + + // phi use -> (map: reaching phi -> set of registers defined in between) + std::map> PhiUp; + std::vector PhiUQ; // Work list of phis for upward propagation. + + // Go over all phis. + for (NodeAddr 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 DefQ; + NodeSet PhiDefs; + for (NodeAddr R : PhiRefs) { + if (!DFG.IsRef(R)) + continue; + DefQ.insert(R.Id); + PhiDefs.insert(R.Id); + } + + // 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 DA = DFG.addr(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 A = DFG.addr(UN); + uint16_t F = A.Addr->getFlags(); + if ((F & (NodeAttrs::Undef | NodeAttrs::PhiRef)) == 0) { + RegisterRef R = DFG.normalizeRef(getRestrictedRegRef(A)); + 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 A = DFG.addr(DN); + for (auto T : DFG.getRelatedRefs(A.Addr->getOwner(DFG), A)) { + uint16_t Flags = NodeAddr(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. + auto InPhiDefs = [&PhiDefs] (NodeAddr DA) -> bool { + return PhiDefs.count(DA.Id); + }; + 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; + for (auto I = Uses.begin(), E = Uses.end(); I != E; ) { + auto UA = DFG.addr(I->first); + // Undef flag is checked above. + assert((UA.Addr->getFlags() & NodeAttrs::Undef) == 0); + RegisterRef R(UI->first, I->second); + NodeList RDs = getAllReachingDefs(R, UA); + if (any_of(RDs, InPhiDefs)) + ++I; + else + I = Uses.erase(I); + } + if (Uses.empty()) + UI = RealUses.erase(UI); + else + ++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(I) || SeenUses.count(I.Id)) + continue; + NodeAddr UA = I; + + // Given a phi use UA, traverse all related phi uses (including UA). + // The related phi uses may reach different phi nodes or may reach the + // same phi node. If multiple uses reach the same phi P, the intervening + // defs must be accumulated for all such uses. To group all such uses + // into one set, map their node ids to the first use id that reaches P. + std::map FirstUse; // Phi reached up -> first phi use. + + for (NodeAddr VA : DFG.getRelatedRefs(PhiA, UA)) { + SeenUses.insert(VA.Id); + RegisterAggr DefRRs(PRI); + for (NodeAddr DA : getAllReachingDefs(VA)) { + if (DA.Addr->getFlags() & NodeAttrs::PhiRef) { + NodeId RP = DA.Addr->getOwner(DFG).Id; + NodeId FU = FirstUse.insert({RP,VA.Id}).first->second; + std::map &M = PhiUp[FU]; + auto F = M.find(RP); + if (F == M.end()) + M.insert(std::make_pair(RP, DefRRs)); + else + F->second.insert(DefRRs); + } + DefRRs.insert(DA.Addr->getRegRef(DFG)); + } + } + } + } + + if (Trace) { + dbgs() << "Phi-up-to-phi map with intervening defs:\n"; + for (auto I : PhiUp) { + dbgs() << "phi " << Print(I.first, DFG) << " -> {"; + for (auto R : I.second) + dbgs() << ' ' << Print(R.first, DFG) + << Print(R.second, DFG); + dbgs() << " }\n"; + } + } + + // Propagate the reached registers up in the phi chain. + // + // The following type of situation needs careful handling: + // + // phi d1 (1) + // | + // ... d2 + // | + // phi u3 (2) + // | + // ... u4 + // + // 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(PhiUQ[i]); + NodeList PUs = PA.Addr->members_if(DFG.IsRef, DFG); + RefMap &RUM = RealUseMap[PA.Id]; + + for (NodeAddr UA : PUs) { + std::map &PUM = PhiUp[UA.Id]; + RegisterRef UR = DFG.normalizeRef(getRestrictedRegRef(UA)); + for (const std::pair &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 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 &T : RUM) { + RegisterRef R = DFG.restrictRef(RegisterRef(T.first), UR); + if (!R) + continue; + for (std::pair V : T.second) { + RegisterRef S = DFG.restrictRef(RegisterRef(R.Reg, V.second), R); + if (!S) + continue; + if (RegisterRef SS = MidDefs.clearIn(S)) { + 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(I.first, DFG); + NodeAddr PA = DFG.addr(I.first); + NodeList Ds = PA.Addr->members_if(DFG.IsRef, DFG); + if (!Ds.empty()) { + RegisterRef RR = NodeAddr(Ds[0]).Addr->getRegRef(DFG); + dbgs() << '<' << Print(RR, DFG) << '>'; + } else { + dbgs() << ""; + } + dbgs() << " -> " << Print(I.second, DFG) << '\n'; + } + } +} + + +void Liveness::computeLiveIns() { + // Populate the node-to-block map. This speeds up the calculations + // significantly. + NBMap.clear(); + for (NodeAddr BA : DFG.getFunc().Addr->members(DFG)) { + MachineBasicBlock *BB = BA.Addr->getCode(); + for (NodeAddr IA : BA.Addr->members(DFG)) { + for (NodeAddr 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 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 FA = DFG.getFunc(); + NodeList Blocks = FA.Addr->members(DFG); + + // Build the phi live-on-entry map. + for (NodeAddr BA : Blocks) { + MachineBasicBlock *MB = BA.Addr->getCode(); + RefMap &LON = PhiLON[MB]; + for (auto P : BA.Addr->members_if(DFG.IsCode, 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(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 BA : Blocks) { + NodeList Phis = BA.Addr->members_if(DFG.IsCode, DFG); + for (NodeAddr PA : Phis) { + RefMap &RUs = RealUseMap[PA.Id]; + if (RUs.empty()) + continue; + + for (auto U : PA.Addr->members_if(DFG.IsRef, DFG)) { + NodeAddr PUA = U; + if (PUA.Addr->getReachingDef() == 0) + continue; + + // Mark all reached "real" uses of P as live on exit in the + // predecessor. + // Remap all the RUs so that they have a correct reaching def. + auto PrA = DFG.addr(PUA.Addr->getPredecessor()); + RefMap &LOX = PhiLOX[PrA.Addr->getCode()]; + + RegisterRef UR = DFG.normalizeRef(getRestrictedRegRef(PUA)); + for (const std::pair &T : RUs) { + // Check if T.first aliases UR? + LaneBitmask M; + for (std::pair P : T.second) + M |= P.second; + + RegisterRef S = DFG.restrictRef(RegisterRef(T.first, M), UR); + if (!S) + continue; + for (NodeAddr D : getAllReachingDefs(S, PUA)) + LOX[S.Reg].insert({D.Id, S.Mask}); + } + } // 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(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 LV; + for (auto I = B.livein_begin(), E = B.livein_end(); I != E; ++I) + LV.push_back(RegisterRef(I->PhysReg, I->LaneMask)); + std::sort(LV.begin(), LV.end()); + dbgs() << "BB#" << B.getNumber() << "\t rec = {"; + for (auto I : LV) + dbgs() << ' ' << Print(I, DFG); + dbgs() << " }\n"; + //dbgs() << "\tcomp = " << Print(LiveMap[&B], DFG) << '\n'; + + LV.clear(); + for (std::pair P : LiveMap[&B]) { + MCSubRegIndexIterator S(P.first, &TRI); + if (!S.isValid()) { + LV.push_back(RegisterRef(P.first)); + continue; + } + do { + LaneBitmask M = TRI.getSubRegIndexLaneMask(S.getSubRegIndex()); + if ((M & P.second).any()) + LV.push_back(RegisterRef(S.getSubReg())); + ++S; + } while (S.isValid()); + } + std::sort(LV.begin(), LV.end()); + dbgs() << "\tcomp = {"; + for (auto I : LV) + dbgs() << ' ' << Print(I, DFG); + dbgs() << " }\n"; + + } + } +} + + +void Liveness::resetLiveIns() { + for (auto &B : DFG.getMF()) { + // Remove all live-ins. + std::vector 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. + auto &LiveIns = LiveMap[&B]; + for (auto I : LiveIns) { + B.addLiveIn({MCPhysReg(I.first), I.second}); + } + } +} + + +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->isDebugValue()) + 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; + unsigned R = Op.getReg(); + if (!TargetRegisterInfo::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()) + continue; + unsigned R = Op.getReg(); + if (!TargetRegisterInfo::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); + } + } +} + + +RegisterRef Liveness::getRestrictedRegRef(NodeAddr RA) const { + assert(DFG.IsRef(RA)); + if (RA.Addr->getFlags() & NodeAttrs::Shadow) { + NodeId RD = RA.Addr->getReachingDef(); + assert(RD); + RA = DFG.addr(RD); + } + return RA.Addr->getRegRef(DFG); +} + + +// 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-- BB#" << B->getNumber() << ": " << __func__ + << " after recursion into: {"; + for (auto I : *N) + dbgs() << ' ' << I->getBlock()->getNumber(); + dbgs() << " }\n"; + dbgs() << " LiveIn: " << Print(LiveIn, DFG) << '\n'; + dbgs() << " Local: " << Print(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(LiveIn, DFG) << '\n'; + dbgs() << " Local: " << Print(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 &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(OR.first); + NodeAddr IA = DA.Addr->getOwner(DFG); + NodeAddr 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 TA : getAllReachingDefs(DA)) { + // DefNode -> InstrNode -> BlockNode. + NodeAddr ITA = TA.Addr->getOwner(DFG); + NodeAddr 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. + RegisterAggr L(PRI); + L.insert(LRef).clear(RRs); + assert(!L.empty()); + NewDefs.insert({TA.Id,L.begin()->second}); + 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(LiveIn, DFG) << '\n'; + dbgs() << " Local: " << Print(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 IA = I; + if (IA.Addr->getKind() != NodeAttrs::Stmt) + continue; + for (NodeAddr UA : IA.Addr->members_if(DFG.IsUse, DFG)) { + if (UA.Addr->getFlags() & NodeAttrs::Undef) + continue; + RegisterRef RR = DFG.normalizeRef(UA.Addr->getRegRef(DFG)); + for (NodeAddr 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(LiveIn, DFG) << '\n'; + dbgs() << " Local: " << Print(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(LiveIn, DFG) << '\n'; + dbgs() << " Local: " << Print(Local, DFG) << '\n'; + } + + for (auto C : IIDF[B]) { + RegisterAggr &LiveC = LiveMap[C]; + for (const std::pair &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); +} + Index: lib/CodeGen/RDFRegisters.cpp =================================================================== --- /dev/null +++ lib/CodeGen/RDFRegisters.cpp @@ -0,0 +1,337 @@ +//===--- RDFRegisters.cpp ---------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/BitVector.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/RDFRegisters.h" + +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; + } + } + + for (MCPhysReg R = 1, NR = TRI.getNumRegs(); R != NR; ++R) { + MCPhysReg SuperR = R; + for (MCSuperRegIterator S(R, &TRI, false); S.isValid(); ++S) + SuperR = *S; + RegInfos[R].MaxSuper = SuperR; + } + + 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()); +} + +std::set PhysicalRegisterInfo::getAliasSet(RegisterId Reg) const { + // Do not include RR in the alias set. + std::set AS; + assert(isRegMaskId(Reg) || TargetRegisterInfo::isPhysicalRegister(Reg)); + if (isRegMaskId(Reg)) { + // XXX SLOW + // XXX Add other regmasks to the set. + 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); + } + return AS; + } + + for (MCRegAliasIterator AI(Reg, &TRI, false); AI.isValid(); ++AI) + AS.insert(*AI); + return AS; +} + +bool PhysicalRegisterInfo::aliasRR(RegisterRef RA, RegisterRef RB) const { + assert(TargetRegisterInfo::isPhysicalRegister(RA.Reg)); + assert(TargetRegisterInfo::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()) { + std::pair PA = *UMA; + std::pair PB = *UMB; + if (PA.first == PB.first) { + // Lane mask of 0 (given by the iterator) should be treated as "full". + // This can happen when the register has only one unit, or when the + // unit corresponds to explicit aliasing. In such cases, the lane mask + // from RegisterRef should be ignored. + if (PA.second.none() || PB.second.none()) + return true; + + // At this point the common unit corresponds to a subregister. The lane + // masks correspond to the lane mask of that unit within the original + // register, for example assuming register quadruple q0 = r3:0, and + // a register pair d1 = r3:2, the lane mask of r2 in q0 may be 0b0100, + // while the lane mask of r2 in d1 may be 0b0001. + LaneBitmask LA = PA.second & RA.Mask; + LaneBitmask LB = PB.second & RB.Mask; + if (LA.any() && LB.any()) { + unsigned Root = *MCRegUnitRootIterator(PA.first, &TRI); + // If register units were guaranteed to only have 1 bit in any lane + // mask, the code below would not be necessary. This is because LA + // and LB would have at most 1 bit set each, and that bit would be + // guaranteed to correspond to the given register unit. + uint32_t SubA = TRI.getSubRegIndex(RA.Reg, Root); + uint32_t SubB = TRI.getSubRegIndex(RB.Reg, Root); + const TargetRegisterClass *RC = RegInfos[Root].RegClass; + LaneBitmask RCMask = RC != nullptr ? RC->LaneMask : LaneBitmask(0x1); + LaneBitmask MaskA = TRI.reverseComposeSubRegIndexLaneMask(SubA, LA); + LaneBitmask MaskB = TRI.reverseComposeSubRegIndexLaneMask(SubB, LB); + if ((MaskA & MaskB & RCMask).any()) + return true; + } + + ++UMA; + ++UMB; + continue; + } + if (PA.first < PB.first) + ++UMA; + else if (PB.first < PA.first) + ++UMB; + } + return false; +} + +bool PhysicalRegisterInfo::aliasRM(RegisterRef RR, RegisterRef RM) const { + assert(TargetRegisterInfo::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 RegisterAggr::normalize(RegisterRef RR) const { + if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) + return RR; + const TargetRegisterClass *RC = PRI.RegInfos[RR.Reg].RegClass; + LaneBitmask RCMask = RC != nullptr ? RC->LaneMask : LaneBitmask(0x00000001); + LaneBitmask Common = RR.Mask & RCMask; + + RegisterId SuperReg = PRI.RegInfos[RR.Reg].MaxSuper; +// Ex: IP/EIP/RIP +// assert(RC != nullptr || RR.Reg == SuperReg); + uint32_t Sub = PRI.getTRI().getSubRegIndex(SuperReg, RR.Reg); + LaneBitmask SuperMask = PRI.getTRI().composeSubRegIndexLaneMask(Sub, Common); + return RegisterRef(SuperReg, SuperMask); +} + +bool RegisterAggr::hasAliasOf(RegisterRef RR) const { + if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) { + // XXX SLOW + const uint32_t *MB = PRI.getRegMaskBits(RR.Reg); + for (unsigned i = 1, e = PRI.getTRI().getNumRegs(); i != e; ++i) { + if (MB[i/32] & (1u << (i%32))) + continue; + if (hasAliasOf(RegisterRef(i, LaneBitmask::getAll()))) + return true; + } + } + + RegisterRef NR = normalize(RR); + auto F = Masks.find(NR.Reg); + if (F != Masks.end()) { + if ((F->second & NR.Mask).any()) + return true; + } + if (CheckUnits) { + for (MCRegUnitIterator U(RR.Reg, &PRI.getTRI()); U.isValid(); ++U) + if (ExpAliasUnits.test(*U)) + return true; + } + return false; +} + +bool RegisterAggr::hasCoverOf(RegisterRef RR) const { + if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) { + // XXX SLOW + const uint32_t *MB = PRI.getRegMaskBits(RR.Reg); + for (unsigned i = 1, e = PRI.getTRI().getNumRegs(); i != e; ++i) { + if (MB[i/32] & (1u << (i%32))) + continue; + if (!hasCoverOf(RegisterRef(i, LaneBitmask::getAll()))) + return false; + } + return true; + } + + // Always have a cover for empty lane mask. + RegisterRef NR = normalize(RR); + if (NR.Mask.none()) + return true; + auto F = Masks.find(NR.Reg); + if (F == Masks.end()) + return false; + return (NR.Mask & F->second) == NR.Mask; +} + +RegisterAggr &RegisterAggr::insert(RegisterRef RR) { + if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) { + // XXX SLOW + const uint32_t *MB = PRI.getRegMaskBits(RR.Reg); + for (unsigned i = 1, e = PRI.getTRI().getNumRegs(); i != e; ++i) { + if (MB[i/32] & (1u << (i%32))) + continue; + insert(RegisterRef(i, LaneBitmask::getAll())); + } + return *this; + } + + RegisterRef NR = normalize(RR); + auto F = Masks.find(NR.Reg); + if (F == Masks.end()) + Masks.insert({NR.Reg, NR.Mask}); + else + F->second |= NR.Mask; + + // Visit all register units to see if there are any that were created + // by explicit aliases. Add those that were to the bit vector. + const TargetRegisterInfo &TRI = PRI.getTRI(); + for (MCRegUnitIterator U(RR.Reg, &TRI); U.isValid(); ++U) { + MCRegUnitRootIterator R(*U, &TRI); + ++R; + if (!R.isValid()) + continue; + ExpAliasUnits.set(*U); + CheckUnits = true; + } + return *this; +} + +RegisterAggr &RegisterAggr::insert(const RegisterAggr &RG) { + for (std::pair P : RG.Masks) + insert(RegisterRef(P.first, P.second)); + return *this; +} + +RegisterAggr &RegisterAggr::clear(RegisterRef RR) { + if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) { + // XXX SLOW + const uint32_t *MB = PRI.getRegMaskBits(RR.Reg); + for (unsigned i = 1, e = PRI.getTRI().getNumRegs(); i != e; ++i) { + if (MB[i/32] & (1u << (i%32))) + continue; + clear(RegisterRef(i, LaneBitmask::getAll())); + } + return *this; + } + + RegisterRef NR = normalize(RR); + auto F = Masks.find(NR.Reg); + if (F == Masks.end()) + return *this; + LaneBitmask NewM = F->second & ~NR.Mask; + if (NewM.none()) + Masks.erase(F); + else + F->second = NewM; + return *this; +} + +RegisterAggr &RegisterAggr::clear(const RegisterAggr &RG) { + for (std::pair P : RG.Masks) + clear(RegisterRef(P.first, P.second)); + return *this; +} + +RegisterRef RegisterAggr::clearIn(RegisterRef RR) const { + RegisterAggr T(PRI); + T.insert(RR).clear(*this); + if (T.empty()) + return RegisterRef(); + return RegisterRef(T.begin()->first, T.begin()->second); +} + +void RegisterAggr::print(raw_ostream &OS) const { + OS << '{'; + for (auto I : Masks) + OS << ' ' << PrintReg(I.first, &PRI.getTRI()) + << PrintLaneMaskOpt(I.second); + OS << " }"; +} + Index: lib/Target/Hexagon/CMakeLists.txt =================================================================== --- lib/Target/Hexagon/CMakeLists.txt +++ lib/Target/Hexagon/CMakeLists.txt @@ -57,9 +57,6 @@ HexagonVLIWPacketizer.cpp RDFCopy.cpp RDFDeadCode.cpp - RDFGraph.cpp - RDFLiveness.cpp - RDFRegisters.cpp ) add_subdirectory(AsmParser) Index: lib/Target/Hexagon/HexagonOptAddrMode.cpp =================================================================== --- lib/Target/Hexagon/HexagonOptAddrMode.cpp +++ lib/Target/Hexagon/HexagonOptAddrMode.cpp @@ -15,8 +15,6 @@ #include "HexagonInstrInfo.h" #include "HexagonSubtarget.h" #include "MCTargetDesc/HexagonBaseInfo.h" -#include "RDFGraph.h" -#include "RDFLiveness.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/StringRef.h" #include "llvm/CodeGen/MachineBasicBlock.h" @@ -27,6 +25,8 @@ #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineOperand.h" +#include "llvm/CodeGen/RDFGraph.h" +#include "llvm/CodeGen/RDFLiveness.h" #include "llvm/MC/MCInstrDesc.h" #include "llvm/Pass.h" #include "llvm/Support/CommandLine.h" Index: lib/Target/Hexagon/HexagonRDFOpt.cpp =================================================================== --- lib/Target/Hexagon/HexagonRDFOpt.cpp +++ lib/Target/Hexagon/HexagonRDFOpt.cpp @@ -11,8 +11,6 @@ #include "HexagonSubtarget.h" #include "RDFCopy.h" #include "RDFDeadCode.h" -#include "RDFGraph.h" -#include "RDFLiveness.h" #include "llvm/ADT/SetVector.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineDominanceFrontier.h" @@ -20,6 +18,8 @@ #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/RDFGraph.h" +#include "llvm/CodeGen/RDFLiveness.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Format.h" #include "llvm/Target/TargetInstrInfo.h" Index: lib/Target/Hexagon/RDFCopy.h =================================================================== --- lib/Target/Hexagon/RDFCopy.h +++ lib/Target/Hexagon/RDFCopy.h @@ -10,7 +10,7 @@ #ifndef LLVM_LIB_TARGET_HEXAGON_RDFCOPY_H #define LLVM_LIB_TARGET_HEXAGON_RDFCOPY_H -#include "RDFGraph.h" +#include "llvm/CodeGen/RDFGraph.h" #include #include Index: lib/Target/Hexagon/RDFCopy.cpp =================================================================== --- lib/Target/Hexagon/RDFCopy.cpp +++ lib/Target/Hexagon/RDFCopy.cpp @@ -10,11 +10,11 @@ // RDF-based copy propagation. #include "RDFCopy.h" -#include "RDFGraph.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/RDFGraph.h" #include "llvm/Support/CommandLine.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetRegisterInfo.h" Index: lib/Target/Hexagon/RDFDeadCode.h =================================================================== --- lib/Target/Hexagon/RDFDeadCode.h +++ lib/Target/Hexagon/RDFDeadCode.h @@ -24,9 +24,9 @@ #ifndef RDF_DEADCODE_H #define RDF_DEADCODE_H -#include "RDFGraph.h" -#include "RDFLiveness.h" #include "llvm/ADT/SetVector.h" +#include "llvm/CodeGen/RDFGraph.h" +#include "llvm/CodeGen/RDFLiveness.h" namespace llvm { class MachineRegisterInfo; Index: lib/Target/Hexagon/RDFDeadCode.cpp =================================================================== --- lib/Target/Hexagon/RDFDeadCode.cpp +++ lib/Target/Hexagon/RDFDeadCode.cpp @@ -9,14 +9,13 @@ // // RDF-based generic dead code elimination. -#include "RDFGraph.h" -#include "RDFLiveness.h" #include "RDFDeadCode.h" - #include "llvm/ADT/SetVector.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/RDFGraph.h" +#include "llvm/CodeGen/RDFLiveness.h" #include Index: lib/Target/Hexagon/RDFGraph.h =================================================================== --- lib/Target/Hexagon/RDFGraph.h +++ /dev/null @@ -1,945 +0,0 @@ -//===--- RDFGraph.h ---------------------------------------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Target-independent, SSA-based data flow graph for register data flow (RDF) -// for a non-SSA program representation (e.g. post-RA machine code). -// -// -// *** Introduction -// -// The RDF graph is a collection of nodes, each of which denotes some element -// of the program. There are two main types of such elements: code and refe- -// rences. Conceptually, "code" is something that represents the structure -// of the program, e.g. basic block or a statement, while "reference" is an -// instance of accessing a register, e.g. a definition or a use. Nodes are -// connected with each other based on the structure of the program (such as -// blocks, instructions, etc.), and based on the data flow (e.g. reaching -// definitions, reached uses, etc.). The single-reaching-definition principle -// of SSA is generally observed, although, due to the non-SSA representation -// of the program, there are some differences between the graph and a "pure" -// SSA representation. -// -// -// *** Implementation remarks -// -// Since the graph can contain a large number of nodes, memory consumption -// was one of the major design considerations. As a result, there is a single -// base class NodeBase which defines all members used by all possible derived -// classes. The members are arranged in a union, and a derived class cannot -// add any data members of its own. Each derived class only defines the -// functional interface, i.e. member functions. NodeBase must be a POD, -// which implies that all of its members must also be PODs. -// Since nodes need to be connected with other nodes, pointers have been -// replaced with 32-bit identifiers: each node has an id of type NodeId. -// There are mapping functions in the graph that translate between actual -// memory addresses and the corresponding identifiers. -// A node id of 0 is equivalent to nullptr. -// -// -// *** Structure of the graph -// -// A code node is always a collection of other nodes. For example, a code -// node corresponding to a basic block will contain code nodes corresponding -// to instructions. In turn, a code node corresponding to an instruction will -// contain a list of reference nodes that correspond to the definitions and -// uses of registers in that instruction. The members are arranged into a -// circular list, which is yet another consequence of the effort to save -// memory: for each member node it should be possible to obtain its owner, -// and it should be possible to access all other members. There are other -// ways to accomplish that, but the circular list seemed the most natural. -// -// +- CodeNode -+ -// | | <---------------------------------------------------+ -// +-+--------+-+ | -// |FirstM |LastM | -// | +-------------------------------------+ | -// | | | -// V V | -// +----------+ Next +----------+ Next Next +----------+ Next | -// | |----->| |-----> ... ----->| |----->-+ -// +- Member -+ +- Member -+ +- Member -+ -// -// The order of members is such that related reference nodes (see below) -// should be contiguous on the member list. -// -// A reference node is a node that encapsulates an access to a register, -// in other words, data flowing into or out of a register. There are two -// major kinds of reference nodes: defs and uses. A def node will contain -// the id of the first reached use, and the id of the first reached def. -// Each def and use will contain the id of the reaching def, and also the -// id of the next reached def (for def nodes) or use (for use nodes). -// The "next node sharing the same reaching def" is denoted as "sibling". -// In summary: -// - Def node contains: reaching def, sibling, first reached def, and first -// reached use. -// - Use node contains: reaching def and sibling. -// -// +-- DefNode --+ -// | R2 = ... | <---+--------------------+ -// ++---------+--+ | | -// |Reached |Reached | | -// |Def |Use | | -// | | |Reaching |Reaching -// | V |Def |Def -// | +-- UseNode --+ Sib +-- UseNode --+ Sib Sib -// | | ... = R2 |----->| ... = R2 |----> ... ----> 0 -// | +-------------+ +-------------+ -// V -// +-- DefNode --+ Sib -// | R2 = ... |----> ... -// ++---------+--+ -// | | -// | | -// ... ... -// -// To get a full picture, the circular lists connecting blocks within a -// function, instructions within a block, etc. should be superimposed with -// the def-def, def-use links shown above. -// To illustrate this, consider a small example in a pseudo-assembly: -// foo: -// add r2, r0, r1 ; r2 = r0+r1 -// addi r0, r2, 1 ; r0 = r2+1 -// ret r0 ; return value in r0 -// -// The graph (in a format used by the debugging functions) would look like: -// -// DFG dump:[ -// f1: Function foo -// b2: === BB#0 === preds(0), succs(0): -// p3: phi [d4(,d12,u9):] -// p5: phi [d6(,,u10):] -// s7: add [d8(,,u13):, u9(d4):, u10(d6):] -// s11: addi [d12(d4,,u15):, u13(d8):] -// s14: ret [u15(d12):] -// ] -// -// The f1, b2, p3, etc. are node ids. The letter is prepended to indicate the -// kind of the node (i.e. f - function, b - basic block, p - phi, s - state- -// ment, d - def, u - use). -// The format of a def node is: -// dN(rd,d,u):sib, -// where -// N - numeric node id, -// R - register being defined -// rd - reaching def, -// d - reached def, -// u - reached use, -// sib - sibling. -// The format of a use node is: -// uN[!](rd):sib, -// where -// N - numeric node id, -// R - register being used, -// rd - reaching def, -// sib - sibling. -// Possible annotations (usually preceding the node id): -// + - preserving def, -// ~ - clobbering def, -// " - shadow ref (follows the node id), -// ! - fixed register (appears after register name). -// -// The circular lists are not explicit in the dump. -// -// -// *** Node attributes -// -// NodeBase has a member "Attrs", which is the primary way of determining -// the node's characteristics. The fields in this member decide whether -// the node is a code node or a reference node (i.e. node's "type"), then -// within each type, the "kind" determines what specifically this node -// represents. The remaining bits, "flags", contain additional information -// that is even more detailed than the "kind". -// CodeNode's kinds are: -// - Phi: Phi node, members are reference nodes. -// - Stmt: Statement, members are reference nodes. -// - Block: Basic block, members are instruction nodes (i.e. Phi or Stmt). -// - Func: The whole function. The members are basic block nodes. -// RefNode's kinds are: -// - Use. -// - Def. -// -// Meaning of flags: -// - Preserving: applies only to defs. A preserving def is one that can -// preserve some of the original bits among those that are included in -// the register associated with that def. For example, if R0 is a 32-bit -// register, but a def can only change the lower 16 bits, then it will -// be marked as preserving. -// - Shadow: a reference that has duplicates holding additional reaching -// defs (see more below). -// - Clobbering: applied only to defs, indicates that the value generated -// by this def is unspecified. A typical example would be volatile registers -// after function calls. -// - Fixed: the register in this def/use cannot be replaced with any other -// register. A typical case would be a parameter register to a call, or -// the register with the return value from a function. -// - Undef: the register in this reference the register is assumed to have -// no pre-existing value, even if it appears to be reached by some def. -// This is typically used to prevent keeping registers artificially live -// in cases when they are defined via predicated instructions. For example: -// r0 = add-if-true cond, r10, r11 (1) -// r0 = add-if-false cond, r12, r13, r0 (2) -// ... = r0 (3) -// Before (1), r0 is not intended to be live, and the use of r0 in (3) is -// not meant to be reached by any def preceding (1). However, since the -// defs in (1) and (2) are both preserving, these properties alone would -// imply that the use in (3) may indeed be reached by some prior def. -// Adding Undef flag to the def in (1) prevents that. The Undef flag -// may be applied to both defs and uses. -// - Dead: applies only to defs. The value coming out of a "dead" def is -// assumed to be unused, even if the def appears to be reaching other defs -// or uses. The motivation for this flag comes from dead defs on function -// calls: there is no way to determine if such a def is dead without -// analyzing the target's ABI. Hence the graph should contain this info, -// as it is unavailable otherwise. On the other hand, a def without any -// uses on a typical instruction is not the intended target for this flag. -// -// *** Shadow references -// -// It may happen that a super-register can have two (or more) non-overlapping -// sub-registers. When both of these sub-registers are defined and followed -// by a use of the super-register, the use of the super-register will not -// have a unique reaching def: both defs of the sub-registers need to be -// accounted for. In such cases, a duplicate use of the super-register is -// added and it points to the extra reaching def. Both uses are marked with -// a flag "shadow". Example: -// Assume t0 is a super-register of r0 and r1, r0 and r1 do not overlap: -// set r0, 1 ; r0 = 1 -// set r1, 1 ; r1 = 1 -// addi t1, t0, 1 ; t1 = t0+1 -// -// The DFG: -// s1: set [d2(,,u9):] -// s3: set [d4(,,u10):] -// s5: addi [d6(,,):, u7"(d2):, u8"(d4):] -// -// The statement s5 has two use nodes for t0: u7" and u9". The quotation -// mark " indicates that the node is a shadow. -// - -#ifndef LLVM_LIB_TARGET_HEXAGON_RDFGRAPH_H -#define LLVM_LIB_TARGET_HEXAGON_RDFGRAPH_H - -#include "RDFRegisters.h" -#include "llvm/ADT/BitVector.h" -#include "llvm/ADT/STLExtras.h" -#include "llvm/MC/LaneBitmask.h" -#include "llvm/Support/Allocator.h" -#include "llvm/Support/MathExtras.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Target/TargetRegisterInfo.h" -#include -#include -#include -#include -#include -#include -#include -#include -#include - -// RDF uses uint32_t to refer to registers. This is to ensure that the type -// size remains specific. In other places, registers are often stored using -// unsigned. -static_assert(sizeof(uint32_t) == sizeof(unsigned), "Those should be equal"); - -namespace llvm { - - class MachineBasicBlock; - class MachineFunction; - class MachineInstr; - class MachineOperand; - class MachineDominanceFrontier; - class MachineDominatorTree; - class TargetInstrInfo; - -namespace rdf { - - typedef uint32_t NodeId; - - struct DataFlowGraph; - - struct NodeAttrs { - enum : uint16_t { - None = 0x0000, // Nothing - - // Types: 2 bits - TypeMask = 0x0003, - Code = 0x0001, // 01, Container - Ref = 0x0002, // 10, Reference - - // Kind: 3 bits - KindMask = 0x0007 << 2, - Def = 0x0001 << 2, // 001 - Use = 0x0002 << 2, // 010 - Phi = 0x0003 << 2, // 011 - Stmt = 0x0004 << 2, // 100 - Block = 0x0005 << 2, // 101 - Func = 0x0006 << 2, // 110 - - // Flags: 7 bits for now - FlagMask = 0x007F << 5, - Shadow = 0x0001 << 5, // 0000001, Has extra reaching defs. - Clobbering = 0x0002 << 5, // 0000010, Produces unspecified values. - PhiRef = 0x0004 << 5, // 0000100, Member of PhiNode. - Preserving = 0x0008 << 5, // 0001000, Def can keep original bits. - Fixed = 0x0010 << 5, // 0010000, Fixed register. - Undef = 0x0020 << 5, // 0100000, Has no pre-existing value. - Dead = 0x0040 << 5, // 1000000, Does not define a value. - }; - - static uint16_t type(uint16_t T) { return T & TypeMask; } - static uint16_t kind(uint16_t T) { return T & KindMask; } - static uint16_t flags(uint16_t T) { return T & FlagMask; } - - static uint16_t set_type(uint16_t A, uint16_t T) { - return (A & ~TypeMask) | T; - } - - static uint16_t set_kind(uint16_t A, uint16_t K) { - return (A & ~KindMask) | K; - } - - static uint16_t set_flags(uint16_t A, uint16_t F) { - return (A & ~FlagMask) | F; - } - - // Test if A contains B. - static bool contains(uint16_t A, uint16_t B) { - if (type(A) != Code) - return false; - uint16_t KB = kind(B); - switch (kind(A)) { - case Func: - return KB == Block; - case Block: - return KB == Phi || KB == Stmt; - case Phi: - case Stmt: - return type(B) == Ref; - } - return false; - } - }; - - struct BuildOptions { - enum : unsigned { - None = 0x00, - KeepDeadPhis = 0x01, // Do not remove dead phis during build. - }; - }; - - template struct NodeAddr { - NodeAddr() : Addr(nullptr) {} - NodeAddr(T A, NodeId I) : Addr(A), Id(I) {} - - // Type cast (casting constructor). The reason for having this class - // instead of std::pair. - template NodeAddr(const NodeAddr &NA) - : Addr(static_cast(NA.Addr)), Id(NA.Id) {} - - bool operator== (const NodeAddr &NA) const { - assert((Addr == NA.Addr) == (Id == NA.Id)); - return Addr == NA.Addr; - } - bool operator!= (const NodeAddr &NA) const { - return !operator==(NA); - } - - T Addr; - NodeId Id = 0; - }; - - struct NodeBase; - - // Fast memory allocation and translation between node id and node address. - // This is really the same idea as the one underlying the "bump pointer - // allocator", the difference being in the translation. A node id is - // composed of two components: the index of the block in which it was - // allocated, and the index within the block. With the default settings, - // where the number of nodes per block is 4096, the node id (minus 1) is: - // - // bit position: 11 0 - // +----------------------------+--------------+ - // | Index of the block |Index in block| - // +----------------------------+--------------+ - // - // The actual node id is the above plus 1, to avoid creating a node id of 0. - // - // This method significantly improved the build time, compared to using maps - // (std::unordered_map or DenseMap) to translate between pointers and ids. - struct NodeAllocator { - // Amount of storage for a single node. - enum { NodeMemSize = 32 }; - - NodeAllocator(uint32_t NPB = 4096) - : NodesPerBlock(NPB), BitsPerIndex(Log2_32(NPB)), - IndexMask((1 << BitsPerIndex)-1) { - assert(isPowerOf2_32(NPB)); - } - - NodeBase *ptr(NodeId N) const { - uint32_t N1 = N-1; - uint32_t BlockN = N1 >> BitsPerIndex; - uint32_t Offset = (N1 & IndexMask) * NodeMemSize; - return reinterpret_cast(Blocks[BlockN]+Offset); - } - - NodeId id(const NodeBase *P) const; - NodeAddr New(); - void clear(); - - private: - void startNewBlock(); - bool needNewBlock(); - - uint32_t makeId(uint32_t Block, uint32_t Index) const { - // Add 1 to the id, to avoid the id of 0, which is treated as "null". - return ((Block << BitsPerIndex) | Index) + 1; - } - - const uint32_t NodesPerBlock; - const uint32_t BitsPerIndex; - const uint32_t IndexMask; - char *ActiveEnd = nullptr; - std::vector Blocks; - typedef BumpPtrAllocatorImpl AllocatorTy; - AllocatorTy MemPool; - }; - - typedef std::set RegisterSet; - - struct TargetOperandInfo { - TargetOperandInfo(const TargetInstrInfo &tii) : TII(tii) {} - virtual ~TargetOperandInfo() = default; - - virtual bool isPreserving(const MachineInstr &In, unsigned OpNum) const; - virtual bool isClobbering(const MachineInstr &In, unsigned OpNum) const; - virtual bool isFixedReg(const MachineInstr &In, unsigned OpNum) const; - - const TargetInstrInfo &TII; - }; - - // Packed register reference. Only used for storage. - struct PackedRegisterRef { - RegisterId Reg; - uint32_t MaskId; - }; - - struct LaneMaskIndex : private IndexedSet { - LaneMaskIndex() = default; - - LaneBitmask getLaneMaskForIndex(uint32_t K) const { - return K == 0 ? LaneBitmask::getAll() : get(K); - } - uint32_t getIndexForLaneMask(LaneBitmask LM) { - assert(LM.any()); - return LM.all() ? 0 : insert(LM); - } - uint32_t getIndexForLaneMask(LaneBitmask LM) const { - assert(LM.any()); - return LM.all() ? 0 : find(LM); - } - }; - - struct NodeBase { - public: - // Make sure this is a POD. - NodeBase() = default; - - uint16_t getType() const { return NodeAttrs::type(Attrs); } - uint16_t getKind() const { return NodeAttrs::kind(Attrs); } - uint16_t getFlags() const { return NodeAttrs::flags(Attrs); } - NodeId getNext() const { return Next; } - - uint16_t getAttrs() const { return Attrs; } - void setAttrs(uint16_t A) { Attrs = A; } - void setFlags(uint16_t F) { setAttrs(NodeAttrs::set_flags(getAttrs(), F)); } - - // Insert node NA after "this" in the circular chain. - void append(NodeAddr NA); - // Initialize all members to 0. - void init() { memset(this, 0, sizeof *this); } - void setNext(NodeId N) { Next = N; } - - protected: - uint16_t Attrs; - uint16_t Reserved; - NodeId Next; // Id of the next node in the circular chain. - // Definitions of nested types. Using anonymous nested structs would make - // this class definition clearer, but unnamed structs are not a part of - // the standard. - struct Def_struct { - NodeId DD, DU; // Ids of the first reached def and use. - }; - struct PhiU_struct { - NodeId PredB; // Id of the predecessor block for a phi use. - }; - struct Code_struct { - void *CP; // Pointer to the actual code. - NodeId FirstM, LastM; // Id of the first member and last. - }; - struct Ref_struct { - NodeId RD, Sib; // Ids of the reaching def and the sibling. - union { - Def_struct Def; - PhiU_struct PhiU; - }; - union { - MachineOperand *Op; // Non-phi refs point to a machine operand. - PackedRegisterRef PR; // Phi refs store register info directly. - }; - }; - - // The actual payload. - union { - Ref_struct Ref; - Code_struct Code; - }; - }; - // The allocator allocates chunks of 32 bytes for each node. The fact that - // each node takes 32 bytes in memory is used for fast translation between - // the node id and the node address. - static_assert(sizeof(NodeBase) <= NodeAllocator::NodeMemSize, - "NodeBase must be at most NodeAllocator::NodeMemSize bytes"); - - typedef std::vector> NodeList; - typedef std::set NodeSet; - - struct RefNode : public NodeBase { - RefNode() = default; - - RegisterRef getRegRef(const DataFlowGraph &G) const; - - MachineOperand &getOp() { - assert(!(getFlags() & NodeAttrs::PhiRef)); - return *Ref.Op; - } - - void setRegRef(RegisterRef RR, DataFlowGraph &G); - void setRegRef(MachineOperand *Op, DataFlowGraph &G); - - NodeId getReachingDef() const { - return Ref.RD; - } - void setReachingDef(NodeId RD) { - Ref.RD = RD; - } - - NodeId getSibling() const { - return Ref.Sib; - } - void setSibling(NodeId Sib) { - Ref.Sib = Sib; - } - - bool isUse() const { - assert(getType() == NodeAttrs::Ref); - return getKind() == NodeAttrs::Use; - } - - bool isDef() const { - assert(getType() == NodeAttrs::Ref); - return getKind() == NodeAttrs::Def; - } - - template - NodeAddr getNextRef(RegisterRef RR, Predicate P, bool NextOnly, - const DataFlowGraph &G); - NodeAddr getOwner(const DataFlowGraph &G); - }; - - struct DefNode : public RefNode { - NodeId getReachedDef() const { - return Ref.Def.DD; - } - void setReachedDef(NodeId D) { - Ref.Def.DD = D; - } - NodeId getReachedUse() const { - return Ref.Def.DU; - } - void setReachedUse(NodeId U) { - Ref.Def.DU = U; - } - - void linkToDef(NodeId Self, NodeAddr DA); - }; - - struct UseNode : public RefNode { - void linkToDef(NodeId Self, NodeAddr DA); - }; - - struct PhiUseNode : public UseNode { - NodeId getPredecessor() const { - assert(getFlags() & NodeAttrs::PhiRef); - return Ref.PhiU.PredB; - } - void setPredecessor(NodeId B) { - assert(getFlags() & NodeAttrs::PhiRef); - Ref.PhiU.PredB = B; - } - }; - - struct CodeNode : public NodeBase { - template T getCode() const { - return static_cast(Code.CP); - } - void setCode(void *C) { - Code.CP = C; - } - - NodeAddr getFirstMember(const DataFlowGraph &G) const; - NodeAddr getLastMember(const DataFlowGraph &G) const; - void addMember(NodeAddr NA, const DataFlowGraph &G); - void addMemberAfter(NodeAddr MA, NodeAddr NA, - const DataFlowGraph &G); - void removeMember(NodeAddr NA, const DataFlowGraph &G); - - NodeList members(const DataFlowGraph &G) const; - template - NodeList members_if(Predicate P, const DataFlowGraph &G) const; - }; - - struct InstrNode : public CodeNode { - NodeAddr getOwner(const DataFlowGraph &G); - }; - - struct PhiNode : public InstrNode { - MachineInstr *getCode() const { - return nullptr; - } - }; - - struct StmtNode : public InstrNode { - MachineInstr *getCode() const { - return CodeNode::getCode(); - } - }; - - struct BlockNode : public CodeNode { - MachineBasicBlock *getCode() const { - return CodeNode::getCode(); - } - - void addPhi(NodeAddr PA, const DataFlowGraph &G); - }; - - struct FuncNode : public CodeNode { - MachineFunction *getCode() const { - return CodeNode::getCode(); - } - - NodeAddr findBlock(const MachineBasicBlock *BB, - const DataFlowGraph &G) const; - NodeAddr getEntryBlock(const DataFlowGraph &G); - }; - - struct DataFlowGraph { - DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii, - const TargetRegisterInfo &tri, const MachineDominatorTree &mdt, - const MachineDominanceFrontier &mdf, const TargetOperandInfo &toi); - - NodeBase *ptr(NodeId N) const; - template T ptr(NodeId N) const { - return static_cast(ptr(N)); - } - - NodeId id(const NodeBase *P) const; - - template NodeAddr addr(NodeId N) const { - return { ptr(N), N }; - } - - NodeAddr getFunc() const { return Func; } - MachineFunction &getMF() const { return MF; } - const TargetInstrInfo &getTII() const { return TII; } - const TargetRegisterInfo &getTRI() const { return TRI; } - const PhysicalRegisterInfo &getPRI() const { return PRI; } - const MachineDominatorTree &getDT() const { return MDT; } - const MachineDominanceFrontier &getDF() const { return MDF; } - const RegisterAggr &getLiveIns() const { return LiveIns; } - - struct DefStack { - DefStack() = default; - - bool empty() const { return Stack.empty() || top() == bottom(); } - - private: - typedef NodeAddr value_type; - struct Iterator { - typedef DefStack::value_type value_type; - - Iterator &up() { Pos = DS.nextUp(Pos); return *this; } - Iterator &down() { Pos = DS.nextDown(Pos); return *this; } - - value_type operator*() const { - assert(Pos >= 1); - return DS.Stack[Pos-1]; - } - const value_type *operator->() const { - assert(Pos >= 1); - return &DS.Stack[Pos-1]; - } - bool operator==(const Iterator &It) const { return Pos == It.Pos; } - bool operator!=(const Iterator &It) const { return Pos != It.Pos; } - - private: - Iterator(const DefStack &S, bool Top); - - // Pos-1 is the index in the StorageType object that corresponds to - // the top of the DefStack. - const DefStack &DS; - unsigned Pos; - friend struct DefStack; - }; - - public: - typedef Iterator iterator; - iterator top() const { return Iterator(*this, true); } - iterator bottom() const { return Iterator(*this, false); } - unsigned size() const; - - void push(NodeAddr DA) { Stack.push_back(DA); } - void pop(); - void start_block(NodeId N); - void clear_block(NodeId N); - - private: - friend struct Iterator; - typedef std::vector StorageType; - - bool isDelimiter(const StorageType::value_type &P, NodeId N = 0) const { - return (P.Addr == nullptr) && (N == 0 || P.Id == N); - } - - unsigned nextUp(unsigned P) const; - unsigned nextDown(unsigned P) const; - - StorageType Stack; - }; - - // Make this std::unordered_map for speed of accessing elements. - // Map: Register (physical or virtual) -> DefStack - typedef std::unordered_map DefStackMap; - - void build(unsigned Options = BuildOptions::None); - void pushDefs(NodeAddr IA, DefStackMap &DM); - void markBlock(NodeId B, DefStackMap &DefM); - void releaseBlock(NodeId B, DefStackMap &DefM); - - PackedRegisterRef pack(RegisterRef RR) { - return { RR.Reg, LMI.getIndexForLaneMask(RR.Mask) }; - } - PackedRegisterRef pack(RegisterRef RR) const { - return { RR.Reg, LMI.getIndexForLaneMask(RR.Mask) }; - } - RegisterRef unpack(PackedRegisterRef PR) const { - return RegisterRef(PR.Reg, LMI.getLaneMaskForIndex(PR.MaskId)); - } - - RegisterRef makeRegRef(unsigned Reg, unsigned Sub) const; - RegisterRef makeRegRef(const MachineOperand &Op) const; - RegisterRef normalizeRef(RegisterRef RR) const; - RegisterRef restrictRef(RegisterRef AR, RegisterRef BR) const; - - NodeAddr getNextRelated(NodeAddr IA, - NodeAddr RA) const; - NodeAddr getNextImp(NodeAddr IA, - NodeAddr RA, bool Create); - NodeAddr getNextImp(NodeAddr IA, - NodeAddr RA) const; - NodeAddr getNextShadow(NodeAddr IA, - NodeAddr RA, bool Create); - NodeAddr getNextShadow(NodeAddr IA, - NodeAddr RA) const; - - NodeList getRelatedRefs(NodeAddr IA, - NodeAddr RA) const; - - void unlinkUse(NodeAddr UA, bool RemoveFromOwner) { - unlinkUseDF(UA); - if (RemoveFromOwner) - removeFromOwner(UA); - } - - void unlinkDef(NodeAddr DA, bool RemoveFromOwner) { - unlinkDefDF(DA); - if (RemoveFromOwner) - removeFromOwner(DA); - } - - // Some useful filters. - template - static bool IsRef(const NodeAddr BA) { - return BA.Addr->getType() == NodeAttrs::Ref && - BA.Addr->getKind() == Kind; - } - - template - static bool IsCode(const NodeAddr BA) { - return BA.Addr->getType() == NodeAttrs::Code && - BA.Addr->getKind() == Kind; - } - - static bool IsDef(const NodeAddr BA) { - return BA.Addr->getType() == NodeAttrs::Ref && - BA.Addr->getKind() == NodeAttrs::Def; - } - - static bool IsUse(const NodeAddr BA) { - return BA.Addr->getType() == NodeAttrs::Ref && - BA.Addr->getKind() == NodeAttrs::Use; - } - - static bool IsPhi(const NodeAddr BA) { - return BA.Addr->getType() == NodeAttrs::Code && - BA.Addr->getKind() == NodeAttrs::Phi; - } - - static bool IsPreservingDef(const NodeAddr DA) { - uint16_t Flags = DA.Addr->getFlags(); - return (Flags & NodeAttrs::Preserving) && !(Flags & NodeAttrs::Undef); - } - - private: - void reset(); - - RegisterSet getLandingPadLiveIns() const; - - NodeAddr newNode(uint16_t Attrs); - NodeAddr cloneNode(const NodeAddr B); - NodeAddr newUse(NodeAddr Owner, - MachineOperand &Op, uint16_t Flags = NodeAttrs::None); - NodeAddr newPhiUse(NodeAddr Owner, - RegisterRef RR, NodeAddr PredB, - uint16_t Flags = NodeAttrs::PhiRef); - NodeAddr newDef(NodeAddr Owner, - MachineOperand &Op, uint16_t Flags = NodeAttrs::None); - NodeAddr newDef(NodeAddr Owner, - RegisterRef RR, uint16_t Flags = NodeAttrs::PhiRef); - NodeAddr newPhi(NodeAddr Owner); - NodeAddr newStmt(NodeAddr Owner, - MachineInstr *MI); - NodeAddr newBlock(NodeAddr Owner, - MachineBasicBlock *BB); - NodeAddr newFunc(MachineFunction *MF); - - template - std::pair,NodeAddr> - locateNextRef(NodeAddr IA, NodeAddr RA, - Predicate P) const; - - typedef std::map BlockRefsMap; - - void buildStmt(NodeAddr BA, MachineInstr &In); - void buildBlockRefs(NodeAddr BA, BlockRefsMap &RefM); - void recordDefsForDF(BlockRefsMap &PhiM, BlockRefsMap &RefM, - NodeAddr BA); - void buildPhis(BlockRefsMap &PhiM, BlockRefsMap &RefM, - NodeAddr BA); - void removeUnusedPhis(); - - template void linkRefUp(NodeAddr IA, - NodeAddr TA, DefStack &DS); - void linkStmtRefs(DefStackMap &DefM, NodeAddr SA); - void linkBlockRefs(DefStackMap &DefM, NodeAddr BA); - - void unlinkUseDF(NodeAddr UA); - void unlinkDefDF(NodeAddr DA); - - void removeFromOwner(NodeAddr RA) { - NodeAddr IA = RA.Addr->getOwner(*this); - IA.Addr->removeMember(RA, *this); - } - - NodeAddr findBlock(MachineBasicBlock *BB) { - return BlockNodes[BB]; - } - - MachineFunction &MF; - const TargetInstrInfo &TII; - const TargetRegisterInfo &TRI; - const PhysicalRegisterInfo PRI; - const MachineDominatorTree &MDT; - const MachineDominanceFrontier &MDF; - const TargetOperandInfo &TOI; - - RegisterAggr LiveIns; - NodeAddr Func; - NodeAllocator Memory; - // Local map: MachineBasicBlock -> NodeAddr - std::map> BlockNodes; - // Lane mask map. - LaneMaskIndex LMI; - }; // struct DataFlowGraph - - template - NodeAddr RefNode::getNextRef(RegisterRef RR, Predicate P, - bool NextOnly, const DataFlowGraph &G) { - // Get the "Next" reference in the circular list that references RR and - // satisfies predicate "Pred". - auto NA = G.addr(getNext()); - - while (NA.Addr != this) { - if (NA.Addr->getType() == NodeAttrs::Ref) { - NodeAddr RA = NA; - if (RA.Addr->getRegRef(G) == RR && P(NA)) - return NA; - if (NextOnly) - break; - NA = G.addr(NA.Addr->getNext()); - } else { - // We've hit the beginning of the chain. - assert(NA.Addr->getType() == NodeAttrs::Code); - NodeAddr CA = NA; - NA = CA.Addr->getFirstMember(G); - } - } - // Return the equivalent of "nullptr" if such a node was not found. - return NodeAddr(); - } - - template - NodeList CodeNode::members_if(Predicate P, const DataFlowGraph &G) const { - NodeList MM; - auto M = getFirstMember(G); - if (M.Id == 0) - return MM; - - while (M.Addr != this) { - if (P(M)) - MM.push_back(M); - M = G.addr(M.Addr->getNext()); - } - return MM; - } - - - template struct Print; - template - raw_ostream &operator<< (raw_ostream &OS, const Print &P); - - template - struct Print { - Print(const T &x, const DataFlowGraph &g) : Obj(x), G(g) {} - const T &Obj; - const DataFlowGraph &G; - }; - - template - struct PrintNode : Print> { - PrintNode(const NodeAddr &x, const DataFlowGraph &g) - : Print>(x, g) {} - }; - -} // end namespace rdf - -} // end namespace llvm - -#endif // LLVM_LIB_TARGET_HEXAGON_RDFGRAPH_H Index: lib/Target/Hexagon/RDFGraph.cpp =================================================================== --- lib/Target/Hexagon/RDFGraph.cpp +++ /dev/null @@ -1,1839 +0,0 @@ -//===--- RDFGraph.cpp -----------------------------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Target-independent, SSA-based data flow graph for register data flow (RDF). -// -#include "RDFGraph.h" -#include "llvm/ADT/SetVector.h" -#include "llvm/ADT/STLExtras.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/IR/Function.h" -#include "llvm/MC/LaneBitmask.h" -#include "llvm/MC/MCInstrDesc.h" -#include "llvm/MC/MCRegisterInfo.h" -#include "llvm/Support/ErrorHandling.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetLowering.h" -#include "llvm/Target/TargetRegisterInfo.h" -#include -#include -#include -#include -#include -#include -#include - -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; -} - -template<> -raw_ostream &operator<< (raw_ostream &OS, const Print &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; -} - -template<> -raw_ostream &operator<< (raw_ostream &OS, const Print &P) { - auto NA = P.G.addr(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 RA, - const DataFlowGraph &G) { - OS << Print(RA.Id, G) << '<' - << Print(RA.Addr->getRegRef(G), G) << '>'; - if (RA.Addr->getFlags() & NodeAttrs::Fixed) - OS << '!'; -} - -template<> -raw_ostream &operator<< (raw_ostream &OS, const Print> &P) { - printRefHeader(OS, P.Obj, P.G); - OS << '('; - if (NodeId N = P.Obj.Addr->getReachingDef()) - OS << Print(N, P.G); - OS << ','; - if (NodeId N = P.Obj.Addr->getReachedDef()) - OS << Print(N, P.G); - OS << ','; - if (NodeId N = P.Obj.Addr->getReachedUse()) - OS << Print(N, P.G); - OS << "):"; - if (NodeId N = P.Obj.Addr->getSibling()) - OS << Print(N, P.G); - return OS; -} - -template<> -raw_ostream &operator<< (raw_ostream &OS, const Print> &P) { - printRefHeader(OS, P.Obj, P.G); - OS << '('; - if (NodeId N = P.Obj.Addr->getReachingDef()) - OS << Print(N, P.G); - OS << "):"; - if (NodeId N = P.Obj.Addr->getSibling()) - OS << Print(N, P.G); - return OS; -} - -template<> -raw_ostream &operator<< (raw_ostream &OS, - const Print> &P) { - printRefHeader(OS, P.Obj, P.G); - OS << '('; - if (NodeId N = P.Obj.Addr->getReachingDef()) - OS << Print(N, P.G); - OS << ','; - if (NodeId N = P.Obj.Addr->getPredecessor()) - OS << Print(N, P.G); - OS << "):"; - if (NodeId N = P.Obj.Addr->getSibling()) - OS << Print(N, P.G); - return OS; -} - -template<> -raw_ostream &operator<< (raw_ostream &OS, const Print> &P) { - switch (P.Obj.Addr->getKind()) { - case NodeAttrs::Def: - OS << PrintNode(P.Obj, P.G); - break; - case NodeAttrs::Use: - if (P.Obj.Addr->getFlags() & NodeAttrs::PhiRef) - OS << PrintNode(P.Obj, P.G); - else - OS << PrintNode(P.Obj, P.G); - break; - } - return OS; -} - -template<> -raw_ostream &operator<< (raw_ostream &OS, const Print &P) { - unsigned N = P.Obj.size(); - for (auto I : P.Obj) { - OS << Print(I.Id, P.G); - if (--N) - OS << ' '; - } - return OS; -} - -template<> -raw_ostream &operator<< (raw_ostream &OS, const Print &P) { - unsigned N = P.Obj.size(); - for (auto I : P.Obj) { - OS << Print(I, P.G); - if (--N) - OS << ' '; - } - return OS; -} - -namespace { - - template - struct PrintListV { - PrintListV(const NodeList &L, const DataFlowGraph &G) : List(L), G(G) {} - - typedef T Type; - const NodeList &List; - const DataFlowGraph &G; - }; - - template - raw_ostream &operator<< (raw_ostream &OS, const PrintListV &P) { - unsigned N = P.List.size(); - for (NodeAddr A : P.List) { - OS << PrintNode(A, P.G); - if (--N) - OS << ", "; - } - return OS; - } - -} // end anonymous namespace - -template<> -raw_ostream &operator<< (raw_ostream &OS, const Print> &P) { - OS << Print(P.Obj.Id, P.G) << ": phi [" - << PrintListV(P.Obj.Addr->members(P.G), P.G) << ']'; - return OS; -} - -template<> -raw_ostream &operator<< (raw_ostream &OS, - const Print> &P) { - const MachineInstr &MI = *P.Obj.Addr->getCode(); - unsigned Opc = MI.getOpcode(); - OS << Print(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 << "BB#" << T->getMBB()->getNumber(); - else if (T->isGlobal()) - OS << T->getGlobal()->getName(); - else if (T->isSymbol()) - OS << T->getSymbolName(); - } - } - OS << " [" << PrintListV(P.Obj.Addr->members(P.G), P.G) << ']'; - return OS; -} - -template<> -raw_ostream &operator<< (raw_ostream &OS, - const Print> &P) { - switch (P.Obj.Addr->getKind()) { - case NodeAttrs::Phi: - OS << PrintNode(P.Obj, P.G); - break; - case NodeAttrs::Stmt: - OS << PrintNode(P.Obj, P.G); - break; - default: - OS << "instr? " << Print(P.Obj.Id, P.G); - break; - } - return OS; -} - -template<> -raw_ostream &operator<< (raw_ostream &OS, - const Print> &P) { - MachineBasicBlock *BB = P.Obj.Addr->getCode(); - unsigned NP = BB->pred_size(); - std::vector Ns; - auto PrintBBs = [&OS] (std::vector Ns) -> void { - unsigned N = Ns.size(); - for (int I : Ns) { - OS << "BB#" << I; - if (--N) - OS << ", "; - } - }; - - OS << Print(P.Obj.Id, P.G) << ": --- BB#" << BB->getNumber() - << " --- 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(I, P.G) << '\n'; - return OS; -} - -template<> -raw_ostream &operator<< (raw_ostream &OS, - const Print> &P) { - OS << "DFG dump:[\n" << Print(P.Obj.Id, P.G) << ": Function: " - << P.Obj.Addr->getCode()->getName() << '\n'; - for (auto I : P.Obj.Addr->members(P.G)) - OS << PrintNode(I, P.G) << '\n'; - OS << "]\n"; - return OS; -} - -template<> -raw_ostream &operator<< (raw_ostream &OS, const Print &P) { - OS << '{'; - for (auto I : P.Obj) - OS << ' ' << Print(I, P.G); - OS << " }"; - return OS; -} - -template<> -raw_ostream &operator<< (raw_ostream &OS, const Print &P) { - P.Obj.print(OS); - return OS; -} - -template<> -raw_ostream &operator<< (raw_ostream &OS, - const Print &P) { - for (auto I = P.Obj.top(), E = P.Obj.bottom(); I != E; ) { - OS << Print(I->Id, P.G) - << '<' << Print(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(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 NodeAllocator::New() { - if (needNewBlock()) - startNewBlock(); - - uint32_t ActiveB = Blocks.size()-1; - uint32_t Index = (ActiveEnd - Blocks[ActiveB])/NodeMemSize; - NodeAddr NA = { reinterpret_cast(ActiveEnd), - makeId(ActiveB, Index) }; - ActiveEnd += NodeMemSize; - return NA; -} - -NodeId NodeAllocator::id(const NodeBase *P) const { - uintptr_t A = reinterpret_cast(P); - for (unsigned i = 0, n = Blocks.size(); i != n; ++i) { - uintptr_t B = reinterpret_cast(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 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 RefNode::getOwner(const DataFlowGraph &G) { - NodeAddr NA = G.addr(getNext()); - - while (NA.Addr != this) { - if (NA.Addr->getType() == NodeAttrs::Code) - return NA; - NA = G.addr(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 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 DA) { - Ref.RD = DA.Id; - Ref.Sib = DA.Addr->getReachedUse(); - DA.Addr->setReachedUse(Self); -} - -// Get the first member of the code node. -NodeAddr CodeNode::getFirstMember(const DataFlowGraph &G) const { - if (Code.FirstM == 0) - return NodeAddr(); - return G.addr(Code.FirstM); -} - -// Get the last member of the code node. -NodeAddr CodeNode::getLastMember(const DataFlowGraph &G) const { - if (Code.LastM == 0) - return NodeAddr(); - return G.addr(Code.LastM); -} - -// Add node NA at the end of the member list of the given code node. -void CodeNode::addMember(NodeAddr NA, const DataFlowGraph &G) { - NodeAddr 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 MA, NodeAddr 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 NA, const DataFlowGraph &G) { - NodeAddr 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(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) -> bool { return true; }; - return members_if(True, G); -} - -// Return the owner of the given instr node. -NodeAddr InstrNode::getOwner(const DataFlowGraph &G) { - NodeAddr NA = G.addr(getNext()); - - while (NA.Addr != this) { - assert(NA.Addr->getType() == NodeAttrs::Code); - if (NA.Addr->getKind() == NodeAttrs::Block) - return NA; - NA = G.addr(NA.Addr->getNext()); - } - llvm_unreachable("No owner in circular list"); -} - -// Add the phi node PA to the given block node. -void BlockNode::addPhi(NodeAddr PA, const DataFlowGraph &G) { - NodeAddr 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 MN = M; - do { - M = MN; - MN = G.addr(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 FuncNode::findBlock(const MachineBasicBlock *BB, - const DataFlowGraph &G) const { - auto EqBB = [BB] (NodeAddr NA) -> bool { - return NodeAddr(NA).Addr->getCode() == BB; - }; - NodeList Ms = members_if(EqBB, G); - if (!Ms.empty()) - return Ms[0]; - return NodeAddr(); -} - -// Get the block node for the entry block in the given function. -NodeAddr 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 { - if (In.isCall()) - if (In.getOperand(OpNum).isImplicit()) - 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; - RegisterId 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(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 (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 DataFlowGraph::newNode(uint16_t Attrs) { - NodeAddr 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 DataFlowGraph::cloneNode(const NodeAddr B) { - NodeAddr 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 RA = NA; - RA.Addr->setReachingDef(0); - RA.Addr->setSibling(0); - if (NA.Addr->getKind() == NodeAttrs::Def) { - NodeAddr DA = NA; - DA.Addr->setReachedDef(0); - DA.Addr->setReachedUse(0); - } - } - return NA; -} - -// Allocation routines for specific node types/kinds. - -NodeAddr DataFlowGraph::newUse(NodeAddr Owner, - MachineOperand &Op, uint16_t Flags) { - NodeAddr UA = newNode(NodeAttrs::Ref | NodeAttrs::Use | Flags); - UA.Addr->setRegRef(&Op, *this); - return UA; -} - -NodeAddr DataFlowGraph::newPhiUse(NodeAddr Owner, - RegisterRef RR, NodeAddr PredB, uint16_t Flags) { - NodeAddr PUA = newNode(NodeAttrs::Ref | NodeAttrs::Use | Flags); - assert(Flags & NodeAttrs::PhiRef); - PUA.Addr->setRegRef(RR, *this); - PUA.Addr->setPredecessor(PredB.Id); - return PUA; -} - -NodeAddr DataFlowGraph::newDef(NodeAddr Owner, - MachineOperand &Op, uint16_t Flags) { - NodeAddr DA = newNode(NodeAttrs::Ref | NodeAttrs::Def | Flags); - DA.Addr->setRegRef(&Op, *this); - return DA; -} - -NodeAddr DataFlowGraph::newDef(NodeAddr Owner, - RegisterRef RR, uint16_t Flags) { - NodeAddr DA = newNode(NodeAttrs::Ref | NodeAttrs::Def | Flags); - assert(Flags & NodeAttrs::PhiRef); - DA.Addr->setRegRef(RR, *this); - return DA; -} - -NodeAddr DataFlowGraph::newPhi(NodeAddr Owner) { - NodeAddr PA = newNode(NodeAttrs::Code | NodeAttrs::Phi); - Owner.Addr->addPhi(PA, *this); - return PA; -} - -NodeAddr DataFlowGraph::newStmt(NodeAddr Owner, - MachineInstr *MI) { - NodeAddr SA = newNode(NodeAttrs::Code | NodeAttrs::Stmt); - SA.Addr->setCode(MI); - Owner.Addr->addMember(SA, *this); - return SA; -} - -NodeAddr DataFlowGraph::newBlock(NodeAddr Owner, - MachineBasicBlock *BB) { - NodeAddr BA = newNode(NodeAttrs::Code | NodeAttrs::Block); - BA.Addr->setCode(BB); - Owner.Addr->addMember(BA, *this); - return BA; -} - -NodeAddr DataFlowGraph::newFunc(MachineFunction *MF) { - NodeAddr 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 BA = newBlock(Func, &B); - BlockNodes.insert(std::make_pair(&B, BA)); - for (MachineInstr &I : B) { - if (I.isDebugValue()) - continue; - buildStmt(BA, I); - } - } - - NodeAddr EA = Func.Addr->getEntryBlock(*this); - NodeList Blocks = Func.Addr->members(*this); - - // Collect information about block references. - BlockRefsMap RefM; - buildBlockRefs(EA, RefM); - - // 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 (auto I = MRI.livein_begin(), E = MRI.livein_end(); I != E; ++I) - LiveIns.insert(RegisterRef(I->first)); - 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 P : LiveIns) { - NodeAddr PA = newPhi(EA); - uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving; - RegisterRef RR(P.first, P.second); - NodeAddr 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 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 PA = newPhi(BA); - uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving; - // Add def: - NodeAddr DA = newDef(PA, RR, PhiFlags); - PA.Addr->addMember(DA, *this); - // Add uses (no reaching defs for phi uses): - for (NodeAddr PBA : Preds) { - NodeAddr 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 BA : Blocks) - recordDefsForDF(PhiM, RefM, BA); - for (NodeAddr BA : Blocks) - buildPhis(PhiM, RefM, 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) || - TargetRegisterInfo::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::normalizeRef(RegisterRef RR) const { - // FIXME copied from RegisterAggr - if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) - return RR; - const TargetRegisterClass *RC = PRI.RegInfos[RR.Reg].RegClass; - LaneBitmask RCMask = RC != nullptr ? RC->LaneMask : LaneBitmask(0x00000001); - LaneBitmask Common = RR.Mask & RCMask; - - RegisterId SuperReg = PRI.RegInfos[RR.Reg].MaxSuper; -// Ex: IP/EIP/RIP -// assert(RC != nullptr || RR.Reg == SuperReg); - uint32_t Sub = PRI.getTRI().getSubRegIndex(SuperReg, RR.Reg); - LaneBitmask SuperMask = PRI.getTRI().composeSubRegIndexLaneMask(Sub, Common); - return RegisterRef(SuperReg, SuperMask); -} - -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 = normalizeRef(AR); - RegisterRef NBR = normalizeRef(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::pushDefs(NodeAddr IA, DefStackMap &DefM) { - NodeList Defs = IA.Addr->members_if(IsDef, *this); - NodeSet Visited; -#ifndef NDEBUG - RegisterSet 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 DA : Defs) { - if (Visited.count(DA.Id)) - continue; - - NodeList Rel = getRelatedRefs(IA, DA); - NodeAddr 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).second) { - MachineInstr *MI = NodeAddr(IA).Addr->getCode(); - dbgs() << "Multiple definitions of register: " - << Print(RR, *this) << " in\n " << *MI - << "in BB#" << MI->getParent()->getNumber() << '\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 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 IA, - NodeAddr 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(); -} - -// 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 DataFlowGraph::getNextRelated(NodeAddr IA, - NodeAddr RA) const { - assert(IA.Id != 0 && RA.Id != 0); - - auto Related = [this,RA](NodeAddr 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 TA) -> bool { - return Related(TA) && - &RA.Addr->getOp() == &TA.Addr->getOp(); - }; - auto RelatedPhi = [&Related,RA](NodeAddr TA) -> bool { - if (!Related(TA)) - return false; - if (TA.Addr->getKind() != NodeAttrs::Use) - return true; - // For phi uses, compare predecessor blocks. - const NodeAddr TUA = TA; - const NodeAddr 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 -std::pair,NodeAddr> -DataFlowGraph::locateNextRef(NodeAddr IA, NodeAddr RA, - Predicate P) const { - assert(IA.Id != 0 && RA.Id != 0); - - NodeAddr 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()); -} - -// Get the next shadow node in IA corresponding to RA, and optionally create -// such a node if it does not exist. -NodeAddr DataFlowGraph::getNextShadow(NodeAddr IA, - NodeAddr RA, bool Create) { - assert(IA.Id != 0 && RA.Id != 0); - - uint16_t Flags = RA.Addr->getFlags() | NodeAttrs::Shadow; - auto IsShadow = [Flags] (NodeAddr 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 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 DataFlowGraph::getNextShadow(NodeAddr IA, - NodeAddr RA) const { - assert(IA.Id != 0 && RA.Id != 0); - uint16_t Flags = RA.Addr->getFlags() | NodeAttrs::Shadow; - auto IsShadow = [Flags] (NodeAddr 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 BA, MachineInstr &In) { - NodeAddr 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; - }; - - // Collect a set of registers that this instruction implicitly uses - // or defines. Implicit operands from an instruction will be ignored - // unless they are listed here. - RegisterSet ImpUses, ImpDefs; - if (const uint16_t *ImpD = In.getDesc().getImplicitDefs()) - while (uint16_t R = *ImpD++) - ImpDefs.insert(RegisterRef(R)); - if (const uint16_t *ImpU = In.getDesc().getImplicitUses()) - while (uint16_t R = *ImpU++) - ImpUses.insert(RegisterRef(R)); - - bool IsCall = isCall(In); - bool NeedsImplicit = IsCall || In.isInlineAsm() || In.isReturn(); - bool IsPredicated = TII.isPredicated(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; - unsigned R = Op.getReg(); - if (!R || !TargetRegisterInfo::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 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 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; - unsigned R = Op.getReg(); - if (!R || !TargetRegisterInfo::isPhysicalRegister(R) || DoneDefs.test(R)) - continue; - RegisterRef RR = makeRegRef(Op); - if (!NeedsImplicit && !ImpDefs.count(RR)) - 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, 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 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; - unsigned R = Op.getReg(); - if (!R || !TargetRegisterInfo::isPhysicalRegister(R)) - continue; - RegisterRef RR = makeRegRef(Op); - // Add implicit uses on return and call instructions, and on predicated - // instructions regardless of whether or not they appear in the instruction - // descriptor's list. - bool Implicit = Op.isImplicit(); - bool TakeImplicit = NeedsImplicit || IsPredicated; - if (Implicit && !TakeImplicit && !ImpUses.count(RR)) - continue; - uint16_t Flags = NodeAttrs::None; - if (Op.isUndef()) - Flags |= NodeAttrs::Undef; - if (TOI.isFixedReg(In, OpN)) - Flags |= NodeAttrs::Fixed; - NodeAddr UA = newUse(SA, Op, Flags); - SA.Addr->addMember(UA, *this); - } -} - -// Build a map that for each block will have the set of all references from -// that block, and from all blocks dominated by it. -void DataFlowGraph::buildBlockRefs(NodeAddr BA, - BlockRefsMap &RefM) { - RegisterSet &Refs = RefM[BA.Id]; - MachineDomTreeNode *N = MDT.getNode(BA.Addr->getCode()); - assert(N); - for (auto I : *N) { - MachineBasicBlock *SB = I->getBlock(); - NodeAddr SBA = findBlock(SB); - buildBlockRefs(SBA, RefM); - const RegisterSet &RefsS = RefM[SBA.Id]; - Refs.insert(RefsS.begin(), RefsS.end()); - } - - for (NodeAddr IA : BA.Addr->members(*this)) - for (NodeAddr RA : IA.Addr->members(*this)) - Refs.insert(RA.Addr->getRegRef(*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, BlockRefsMap &RefM, - NodeAddr 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 IA : BA.Addr->members(*this)) - for (NodeAddr 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 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()); - } - - // Get the register references that are reachable from this block. - RegisterSet &Refs = RefM[BA.Id]; - for (auto DB : IDF) { - NodeAddr DBA = findBlock(DB); - const RegisterSet &RefsD = RefM[DBA.Id]; - Refs.insert(RefsD.begin(), RefsD.end()); - } - - // Finally, add the set of defs to each block in the iterated dominance - // frontier. - for (auto DB : IDF) { - NodeAddr 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, BlockRefsMap &RefM, - NodeAddr 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 MaxRefs; - RegisterSet &RefB = RefM[BA.Id]; - for (RegisterRef I : MaxDF) - MaxRefs.push_back(MaxCoverIn(I, RefB)); - - // 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. - std::sort(MaxRefs.begin(), MaxRefs.end()); - // Remove duplicates. - auto NewEnd = std::unique(MaxRefs.begin(), MaxRefs.end()); - MaxRefs.erase(NewEnd, MaxRefs.end()); - - auto Aliased = [this,&MaxRefs](RegisterRef RR, - std::vector &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 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 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 DA = newDef(PA, RR, PhiFlags); - PA.Addr->addMember(DA, *this); - } - // Add phi uses. - for (NodeAddr PBA : Preds) { - for (unsigned X = 0; X != CS; ++X) { - RegisterRef RR = MaxRefs[ClosureIdx[X]]; - NodeAddr 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 PhiQ; - for (NodeAddr 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 M : Ms) { - if (M.Addr->getKind() != NodeAttrs::Def) - continue; - NodeAddr 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(PhiQ[0]); - PhiQ.remove(PA.Id); - NodeList Refs = PA.Addr->members(*this); - if (HasUsedDef(Refs)) - continue; - for (NodeAddr RA : Refs) { - if (NodeId RD = RA.Addr->getReachingDef()) { - auto RDA = addr(RD); - NodeAddr OA = RDA.Addr->getOwner(*this); - if (IsPhi(OA)) - PhiQ.insert(OA.Id); - } - if (RA.Addr->isDef()) - unlinkDef(RA, true); - else - unlinkUse(RA, true); - } - NodeAddr 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 -void DataFlowGraph::linkRefUp(NodeAddr IA, NodeAddr TA, - DefStack &DS) { - if (DS.empty()) - return; - RegisterRef RR = TA.Addr->getRegRef(*this); - NodeAddr 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 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. -void DataFlowGraph::linkStmtRefs(DefStackMap &DefM, NodeAddr SA) { -#ifndef NDEBUG - RegisterSet Defs; -#endif - - // Link all nodes (upwards in the data-flow) with their reaching defs. - for (NodeAddr RA : SA.Addr->members(*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(SA, RA, DS); - else if (Kind == NodeAttrs::Def) - linkRefUp(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 BA) { - // Push block delimiters. - markBlock(BA.Id, DefM); - - 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 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); - - // Push the definitions on the stack. - 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 SBA = findBlock(SB); - linkBlockRefs(DefM, SBA); - } - - // Link the phi uses from the successor blocks. - auto IsUseForBA = [BA](NodeAddr NA) -> bool { - if (NA.Addr->getKind() != NodeAttrs::Use) - return false; - assert(NA.Addr->getFlags() & NodeAttrs::PhiRef); - NodeAddr 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 SBA = findBlock(SB); - for (NodeAddr 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 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 PUA = U; - RegisterRef RR = PUA.Addr->getRegRef(*this); - linkRefUp(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 UA) { - NodeId RD = UA.Addr->getReachingDef(); - NodeId Sib = UA.Addr->getSibling(); - - if (RD == 0) { - assert(Sib == 0); - return; - } - - auto RDA = addr(RD); - auto TA = addr(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(S); - } -} - -// Remove the def node DA from any data-flow and structural links. -void DataFlowGraph::unlinkDefDF(NodeAddr 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(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 I : ReachedDefs) - I.Addr->setSibling(0); - for (NodeAddr I : ReachedUses) - I.Addr->setSibling(0); - } - for (NodeAddr I : ReachedDefs) - I.Addr->setReachingDef(RD); - for (NodeAddr 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(RD); - auto TA = addr(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(S); - } - } - - // Splice the DA's reached defs into the RDA's reached def chain. - if (!ReachedDefs.empty()) { - auto Last = NodeAddr(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(ReachedUses.back()); - Last.Addr->setSibling(RDA.Addr->getReachedUse()); - RDA.Addr->setReachedUse(ReachedUses.front().Id); - } -} Index: lib/Target/Hexagon/RDFLiveness.h =================================================================== --- lib/Target/Hexagon/RDFLiveness.h +++ /dev/null @@ -1,135 +0,0 @@ -//===--- RDFLiveness.h ----------------------------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Recalculate the liveness information given a data flow graph. -// This includes block live-ins and kill flags. - -#ifndef RDF_LIVENESS_H -#define RDF_LIVENESS_H - -#include "RDFGraph.h" -#include "llvm/ADT/DenseMap.h" -#include - -using namespace llvm; - -namespace llvm { - class MachineBasicBlock; - class MachineFunction; - class MachineRegisterInfo; - class TargetRegisterInfo; - class MachineDominatorTree; - class MachineDominanceFrontier; - -namespace rdf { - struct Liveness { - public: - // This is really a std::map, except that it provides a non-trivial - // default constructor to the element accessed via []. - struct LiveMapType { - LiveMapType(const PhysicalRegisterInfo &pri) : Empty(pri) {} - - RegisterAggr &operator[] (MachineBasicBlock *B) { - return Map.emplace(B, Empty).first->second; - } - private: - RegisterAggr Empty; - std::map Map; - }; - - typedef std::pair NodeRef; - typedef std::set NodeRefSet; - // RegisterId in RefMap must be normalized. - typedef std::map RefMap; - - Liveness(MachineRegisterInfo &mri, const DataFlowGraph &g) - : DFG(g), TRI(g.getTRI()), PRI(g.getPRI()), MDT(g.getDT()), - MDF(g.getDF()), MRI(mri), LiveMap(g.getPRI()), Empty(), - NoRegs(g.getPRI()), Trace(false) {} - - NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr RefA, - bool FullChain, const RegisterAggr &DefRRs); - NodeList getAllReachingDefs(NodeAddr RefA) { - return getAllReachingDefs(RefA.Addr->getRegRef(DFG), RefA, false, NoRegs); - } - NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr RefA) { - return getAllReachingDefs(RefRR, RefA, false, NoRegs); - } - NodeSet getAllReachingDefsRec(RegisterRef RefRR, NodeAddr RefA, - NodeSet &Visited, const NodeSet &Defs); - NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr DefA, - const RegisterAggr &DefRRs); - NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr DefA) { - return getAllReachedUses(RefRR, DefA, NoRegs); - } - - LiveMapType &getLiveMap() { return LiveMap; } - const LiveMapType &getLiveMap() const { return LiveMap; } - const RefMap &getRealUses(NodeId P) const { - auto F = RealUseMap.find(P); - return F == RealUseMap.end() ? Empty : F->second; - } - - void computePhiInfo(); - void computeLiveIns(); - void resetLiveIns(); - void resetKills(); - void resetKills(MachineBasicBlock *B); - - void trace(bool T) { Trace = T; } - - private: - const DataFlowGraph &DFG; - const TargetRegisterInfo &TRI; - const PhysicalRegisterInfo &PRI; - const MachineDominatorTree &MDT; - const MachineDominanceFrontier &MDF; - MachineRegisterInfo &MRI; - LiveMapType LiveMap; - const RefMap Empty; - const RegisterAggr NoRegs; - bool Trace; - - // Cache of mapping from node ids (for RefNodes) to the containing - // basic blocks. Not computing it each time for each node reduces - // the liveness calculation time by a large fraction. - typedef DenseMap NodeBlockMap; - NodeBlockMap NBMap; - - // Phi information: - // - // RealUseMap - // map: NodeId -> (map: RegisterId -> NodeRefSet) - // phi id -> (map: register -> set of reached non-phi uses) - std::map RealUseMap; - - // Inverse iterated dominance frontier. - std::map> IIDF; - - // Live on entry. - std::map PhiLON; - - // Phi uses are considered to be located at the end of the block that - // they are associated with. The reaching def of a phi use dominates the - // block that the use corresponds to, but not the block that contains - // the phi itself. To include these uses in the liveness propagation (up - // the dominator tree), create a map: block -> set of uses live on exit. - std::map PhiLOX; - - bool isRestrictedToRef(NodeAddr IA, NodeAddr RA, - RegisterRef RR) const; - RegisterRef getRestrictedRegRef(NodeAddr RA) const; - MachineBasicBlock *getBlockWithRef(NodeId RN) const; - void traverse(MachineBasicBlock *B, RefMap &LiveIn); - void emptify(RefMap &M); - }; -} // namespace rdf -} // namespace llvm - -#endif // RDF_LIVENESS_H Index: lib/Target/Hexagon/RDFLiveness.cpp =================================================================== --- lib/Target/Hexagon/RDFLiveness.cpp +++ /dev/null @@ -1,1027 +0,0 @@ -//===--- RDFLiveness.cpp --------------------------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// 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>. -// -#include "RDFGraph.h" -#include "RDFLiveness.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/MachineRegisterInfo.h" -#include "llvm/Target/TargetRegisterInfo.h" - -using namespace llvm; -using namespace rdf; - -namespace llvm { -namespace rdf { - template<> - raw_ostream &operator<< (raw_ostream &OS, const Print &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(J->first, P.G) << PrintLaneMaskOpt(J->second); - if (++J != E) - OS << ','; - } - OS << '}'; - } - OS << " }"; - return OS; - } -} // namespace rdf -} // 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 RefA, bool FullChain, const RegisterAggr &DefRRs) { - NodeList RDefs; // Return value. - SetVector DefQ; - SetVector 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(Start); - if (NodeId RD = SNA.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(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(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 Defs; - for (NodeId N : DefQ) { - auto TA = DFG.addr(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 IA) -> MachineBasicBlock* { - if (IA.Addr->getKind() == NodeAttrs::Stmt) - return NodeAddr(IA).Addr->getCode()->getParent(); - assert(IA.Addr->getKind() == NodeAttrs::Phi); - NodeAddr PA = IA; - NodeAddr 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(A), OB = DFG.addr(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(OA).Addr->getCode(); - MachineInstr *CB = NodeAddr(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 Tmp(Owners.begin(), Owners.end()); - std::sort(Tmp.begin(), Tmp.end(), 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, *d2, ... Assume A and B are aliased (can happen in phi nodes). - // *d3 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 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(T); - bool IsPhi = DFG.IsCode(TA); - NodeList Ds; - for (NodeAddr 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(,d2,), ... Phi def d1 is covered by d2. - // d2(d1,,u3), ... - // ..., u3(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 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 DA) -> bool { - return DA.Addr->getFlags() & NodeAttrs::Dead; - }; - RDefs.resize(std::distance(RDefs.begin(), remove_if(RDefs, DeadP))); - - return RDefs; -} - - -NodeSet Liveness::getAllReachingDefsRec(RegisterRef RefRR, - NodeAddr RefA, NodeSet &Visited, const NodeSet &Defs) { - // 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(D); - if (!(DA.Addr->getFlags() & NodeAttrs::PhiRef)) - DefRRs.insert(DA.Addr->getRegRef(DFG)); - } - - NodeList RDs = getAllReachingDefs(RefRR, RefA, true, DefRRs); - if (RDs.empty()) - return Defs; - - // Make a copy of the preexisting definitions and add the newly found ones. - NodeSet TmpDefs = Defs; - for (NodeAddr R : RDs) - TmpDefs.insert(R.Id); - - NodeSet Result = Defs; - - for (NodeAddr DA : RDs) { - Result.insert(DA.Id); - if (!(DA.Addr->getFlags() & NodeAttrs::PhiRef)) - continue; - NodeAddr 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, DFG)) { - const auto &T = getAllReachingDefsRec(RefRR, U, Visited, TmpDefs); - Result.insert(T.begin(), T.end()); - } - } - - return Result; -} - - -NodeSet Liveness::getAllReachedUses(RegisterRef RefRR, - NodeAddr 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(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(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 FA = DFG.getFunc(); - NodeList Blocks = FA.Addr->members(DFG); - for (NodeAddr BA : Blocks) { - auto Ps = BA.Addr->members_if(DFG.IsCode, DFG); - Phis.insert(Phis.end(), Ps.begin(), Ps.end()); - } - - // phi use -> (map: reaching phi -> set of registers defined in between) - std::map> PhiUp; - std::vector PhiUQ; // Work list of phis for upward propagation. - - // Go over all phis. - for (NodeAddr 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 DefQ; - NodeSet PhiDefs; - for (NodeAddr R : PhiRefs) { - if (!DFG.IsRef(R)) - continue; - DefQ.insert(R.Id); - PhiDefs.insert(R.Id); - } - - // 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 DA = DFG.addr(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 A = DFG.addr(UN); - uint16_t F = A.Addr->getFlags(); - if ((F & (NodeAttrs::Undef | NodeAttrs::PhiRef)) == 0) { - RegisterRef R = DFG.normalizeRef(getRestrictedRegRef(A)); - 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 A = DFG.addr(DN); - for (auto T : DFG.getRelatedRefs(A.Addr->getOwner(DFG), A)) { - uint16_t Flags = NodeAddr(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. - auto InPhiDefs = [&PhiDefs] (NodeAddr DA) -> bool { - return PhiDefs.count(DA.Id); - }; - 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; - for (auto I = Uses.begin(), E = Uses.end(); I != E; ) { - auto UA = DFG.addr(I->first); - // Undef flag is checked above. - assert((UA.Addr->getFlags() & NodeAttrs::Undef) == 0); - RegisterRef R(UI->first, I->second); - NodeList RDs = getAllReachingDefs(R, UA); - if (any_of(RDs, InPhiDefs)) - ++I; - else - I = Uses.erase(I); - } - if (Uses.empty()) - UI = RealUses.erase(UI); - else - ++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(I) || SeenUses.count(I.Id)) - continue; - NodeAddr UA = I; - - // Given a phi use UA, traverse all related phi uses (including UA). - // The related phi uses may reach different phi nodes or may reach the - // same phi node. If multiple uses reach the same phi P, the intervening - // defs must be accumulated for all such uses. To group all such uses - // into one set, map their node ids to the first use id that reaches P. - std::map FirstUse; // Phi reached up -> first phi use. - - for (NodeAddr VA : DFG.getRelatedRefs(PhiA, UA)) { - SeenUses.insert(VA.Id); - RegisterAggr DefRRs(PRI); - for (NodeAddr DA : getAllReachingDefs(VA)) { - if (DA.Addr->getFlags() & NodeAttrs::PhiRef) { - NodeId RP = DA.Addr->getOwner(DFG).Id; - NodeId FU = FirstUse.insert({RP,VA.Id}).first->second; - std::map &M = PhiUp[FU]; - auto F = M.find(RP); - if (F == M.end()) - M.insert(std::make_pair(RP, DefRRs)); - else - F->second.insert(DefRRs); - } - DefRRs.insert(DA.Addr->getRegRef(DFG)); - } - } - } - } - - if (Trace) { - dbgs() << "Phi-up-to-phi map with intervening defs:\n"; - for (auto I : PhiUp) { - dbgs() << "phi " << Print(I.first, DFG) << " -> {"; - for (auto R : I.second) - dbgs() << ' ' << Print(R.first, DFG) - << Print(R.second, DFG); - dbgs() << " }\n"; - } - } - - // Propagate the reached registers up in the phi chain. - // - // The following type of situation needs careful handling: - // - // phi d1 (1) - // | - // ... d2 - // | - // phi u3 (2) - // | - // ... u4 - // - // 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(PhiUQ[i]); - NodeList PUs = PA.Addr->members_if(DFG.IsRef, DFG); - RefMap &RUM = RealUseMap[PA.Id]; - - for (NodeAddr UA : PUs) { - std::map &PUM = PhiUp[UA.Id]; - RegisterRef UR = DFG.normalizeRef(getRestrictedRegRef(UA)); - for (const std::pair &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 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 &T : RUM) { - RegisterRef R = DFG.restrictRef(RegisterRef(T.first), UR); - if (!R) - continue; - for (std::pair V : T.second) { - RegisterRef S = DFG.restrictRef(RegisterRef(R.Reg, V.second), R); - if (!S) - continue; - if (RegisterRef SS = MidDefs.clearIn(S)) { - 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(I.first, DFG); - NodeAddr PA = DFG.addr(I.first); - NodeList Ds = PA.Addr->members_if(DFG.IsRef, DFG); - if (!Ds.empty()) { - RegisterRef RR = NodeAddr(Ds[0]).Addr->getRegRef(DFG); - dbgs() << '<' << Print(RR, DFG) << '>'; - } else { - dbgs() << ""; - } - dbgs() << " -> " << Print(I.second, DFG) << '\n'; - } - } -} - - -void Liveness::computeLiveIns() { - // Populate the node-to-block map. This speeds up the calculations - // significantly. - NBMap.clear(); - for (NodeAddr BA : DFG.getFunc().Addr->members(DFG)) { - MachineBasicBlock *BB = BA.Addr->getCode(); - for (NodeAddr IA : BA.Addr->members(DFG)) { - for (NodeAddr 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 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 FA = DFG.getFunc(); - NodeList Blocks = FA.Addr->members(DFG); - - // Build the phi live-on-entry map. - for (NodeAddr BA : Blocks) { - MachineBasicBlock *MB = BA.Addr->getCode(); - RefMap &LON = PhiLON[MB]; - for (auto P : BA.Addr->members_if(DFG.IsCode, 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(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 BA : Blocks) { - NodeList Phis = BA.Addr->members_if(DFG.IsCode, DFG); - for (NodeAddr PA : Phis) { - RefMap &RUs = RealUseMap[PA.Id]; - if (RUs.empty()) - continue; - - for (auto U : PA.Addr->members_if(DFG.IsRef, DFG)) { - NodeAddr PUA = U; - if (PUA.Addr->getReachingDef() == 0) - continue; - - // Mark all reached "real" uses of P as live on exit in the - // predecessor. - // Remap all the RUs so that they have a correct reaching def. - auto PrA = DFG.addr(PUA.Addr->getPredecessor()); - RefMap &LOX = PhiLOX[PrA.Addr->getCode()]; - - RegisterRef UR = DFG.normalizeRef(getRestrictedRegRef(PUA)); - for (const std::pair &T : RUs) { - // Check if T.first aliases UR? - LaneBitmask M; - for (std::pair P : T.second) - M |= P.second; - - RegisterRef S = DFG.restrictRef(RegisterRef(T.first, M), UR); - if (!S) - continue; - for (NodeAddr D : getAllReachingDefs(S, PUA)) - LOX[S.Reg].insert({D.Id, S.Mask}); - } - } // 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(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 LV; - for (auto I = B.livein_begin(), E = B.livein_end(); I != E; ++I) - LV.push_back(RegisterRef(I->PhysReg, I->LaneMask)); - std::sort(LV.begin(), LV.end()); - dbgs() << "BB#" << B.getNumber() << "\t rec = {"; - for (auto I : LV) - dbgs() << ' ' << Print(I, DFG); - dbgs() << " }\n"; - //dbgs() << "\tcomp = " << Print(LiveMap[&B], DFG) << '\n'; - - LV.clear(); - for (std::pair P : LiveMap[&B]) { - MCSubRegIndexIterator S(P.first, &TRI); - if (!S.isValid()) { - LV.push_back(RegisterRef(P.first)); - continue; - } - do { - LaneBitmask M = TRI.getSubRegIndexLaneMask(S.getSubRegIndex()); - if ((M & P.second).any()) - LV.push_back(RegisterRef(S.getSubReg())); - ++S; - } while (S.isValid()); - } - std::sort(LV.begin(), LV.end()); - dbgs() << "\tcomp = {"; - for (auto I : LV) - dbgs() << ' ' << Print(I, DFG); - dbgs() << " }\n"; - - } - } -} - - -void Liveness::resetLiveIns() { - for (auto &B : DFG.getMF()) { - // Remove all live-ins. - std::vector 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. - auto &LiveIns = LiveMap[&B]; - for (auto I : LiveIns) { - B.addLiveIn({MCPhysReg(I.first), I.second}); - } - } -} - - -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->isDebugValue()) - 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; - unsigned R = Op.getReg(); - if (!TargetRegisterInfo::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()) - continue; - unsigned R = Op.getReg(); - if (!TargetRegisterInfo::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); - } - } -} - - -RegisterRef Liveness::getRestrictedRegRef(NodeAddr RA) const { - assert(DFG.IsRef(RA)); - if (RA.Addr->getFlags() & NodeAttrs::Shadow) { - NodeId RD = RA.Addr->getReachingDef(); - assert(RD); - RA = DFG.addr(RD); - } - return RA.Addr->getRegRef(DFG); -} - - -// 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-- BB#" << B->getNumber() << ": " << __func__ - << " after recursion into: {"; - for (auto I : *N) - dbgs() << ' ' << I->getBlock()->getNumber(); - dbgs() << " }\n"; - dbgs() << " LiveIn: " << Print(LiveIn, DFG) << '\n'; - dbgs() << " Local: " << Print(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(LiveIn, DFG) << '\n'; - dbgs() << " Local: " << Print(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 &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(OR.first); - NodeAddr IA = DA.Addr->getOwner(DFG); - NodeAddr 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 TA : getAllReachingDefs(DA)) { - // DefNode -> InstrNode -> BlockNode. - NodeAddr ITA = TA.Addr->getOwner(DFG); - NodeAddr 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. - RegisterAggr L(PRI); - L.insert(LRef).clear(RRs); - assert(!L.empty()); - NewDefs.insert({TA.Id,L.begin()->second}); - 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(LiveIn, DFG) << '\n'; - dbgs() << " Local: " << Print(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 IA = I; - if (IA.Addr->getKind() != NodeAttrs::Stmt) - continue; - for (NodeAddr UA : IA.Addr->members_if(DFG.IsUse, DFG)) { - if (UA.Addr->getFlags() & NodeAttrs::Undef) - continue; - RegisterRef RR = DFG.normalizeRef(UA.Addr->getRegRef(DFG)); - for (NodeAddr 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(LiveIn, DFG) << '\n'; - dbgs() << " Local: " << Print(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(LiveIn, DFG) << '\n'; - dbgs() << " Local: " << Print(Local, DFG) << '\n'; - } - - for (auto C : IIDF[B]) { - RegisterAggr &LiveC = LiveMap[C]; - for (const std::pair &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); -} - Index: lib/Target/Hexagon/RDFRegisters.h =================================================================== --- lib/Target/Hexagon/RDFRegisters.h +++ /dev/null @@ -1,170 +0,0 @@ -//===--- RDFRegisters.h -----------------------------------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_LIB_TARGET_HEXAGON_RDFREGISTERS_H -#define LLVM_LIB_TARGET_HEXAGON_RDFREGISTERS_H - -#include "llvm/ADT/BitVector.h" -#include "llvm/Target/TargetRegisterInfo.h" - -#include -#include -#include - -namespace llvm { -namespace rdf { - - typedef uint32_t RegisterId; - - // Template class for a map translating uint32_t into arbitrary types. - // The map will act like an indexed set: upon insertion of a new object, - // it will automatically assign a new index to it. Index of 0 is treated - // as invalid and is never allocated. - template - struct IndexedSet { - IndexedSet() : Map() { Map.reserve(N); } - - T get(uint32_t Idx) const { - // Index Idx corresponds to Map[Idx-1]. - assert(Idx != 0 && !Map.empty() && Idx-1 < Map.size()); - return Map[Idx-1]; - } - - uint32_t insert(T Val) { - // Linear search. - auto F = llvm::find(Map, Val); - if (F != Map.end()) - return F - Map.begin() + 1; - Map.push_back(Val); - return Map.size(); // Return actual_index + 1. - } - - uint32_t find(T Val) const { - auto F = llvm::find(Map, Val); - assert(F != Map.end()); - return F - Map.begin() + 1; - } - - private: - std::vector Map; - }; - - struct RegisterRef { - RegisterId Reg = 0; - LaneBitmask Mask = LaneBitmask::getNone(); - - RegisterRef() = default; - explicit RegisterRef(RegisterId R, LaneBitmask M = LaneBitmask::getAll()) - : Reg(R), Mask(R != 0 ? M : LaneBitmask::getNone()) {} - - operator bool() const { - return Reg != 0 && Mask.any(); - } - bool operator== (const RegisterRef &RR) const { - return Reg == RR.Reg && Mask == RR.Mask; - } - bool operator!= (const RegisterRef &RR) const { - return !operator==(RR); - } - bool operator< (const RegisterRef &RR) const { - return Reg < RR.Reg || (Reg == RR.Reg && Mask < RR.Mask); - } - }; - - - struct PhysicalRegisterInfo { - PhysicalRegisterInfo(const TargetRegisterInfo &tri, - const MachineFunction &mf); - - static bool isRegMaskId(RegisterId R) { - return TargetRegisterInfo::isStackSlot(R); - } - RegisterId getRegMaskId(const uint32_t *RM) const { - return TargetRegisterInfo::index2StackSlot(RegMasks.find(RM)); - } - const uint32_t *getRegMaskBits(RegisterId R) const { - return RegMasks.get(TargetRegisterInfo::stackSlot2Index(R)); - } - - bool alias(RegisterRef RA, RegisterRef RB) const { - if (!isRegMaskId(RA.Reg)) - return !isRegMaskId(RB.Reg) ? aliasRR(RA, RB) : aliasRM(RA, RB); - return !isRegMaskId(RB.Reg) ? aliasRM(RB, RA) : aliasMM(RA, RB); - } - std::set getAliasSet(RegisterId Reg) const; - - const TargetRegisterInfo &getTRI() const { return TRI; } - -// private: - struct RegInfo { - unsigned MaxSuper = 0; - const TargetRegisterClass *RegClass = nullptr; - }; - - const TargetRegisterInfo &TRI; - std::vector RegInfos; - IndexedSet RegMasks; - - bool aliasRR(RegisterRef RA, RegisterRef RB) const; - bool aliasRM(RegisterRef RR, RegisterRef RM) const; - bool aliasMM(RegisterRef RM, RegisterRef RN) const; - }; - - - struct RegisterAggr { - RegisterAggr(const PhysicalRegisterInfo &pri) - : ExpAliasUnits(pri.getTRI().getNumRegUnits()), PRI(pri) {} - RegisterAggr(const RegisterAggr &RG) = default; - - bool empty() const { return Masks.empty(); } - bool hasAliasOf(RegisterRef RR) const; - bool hasCoverOf(RegisterRef RR) const; - static bool isCoverOf(RegisterRef RA, RegisterRef RB, - const PhysicalRegisterInfo &PRI) { - return RegisterAggr(PRI).insert(RA).hasCoverOf(RB); - } - - RegisterAggr &insert(RegisterRef RR); - RegisterAggr &insert(const RegisterAggr &RG); - RegisterAggr &clear(RegisterRef RR); - RegisterAggr &clear(const RegisterAggr &RG); - - RegisterRef clearIn(RegisterRef RR) const; - - void print(raw_ostream &OS) const; - - private: - typedef std::unordered_map MapType; - - public: - typedef MapType::const_iterator iterator; - iterator begin() const { return Masks.begin(); } - iterator end() const { return Masks.end(); } - RegisterRef normalize(RegisterRef RR) const; - - private: - MapType Masks; - BitVector ExpAliasUnits; // Register units for explicit aliases. - bool CheckUnits = false; - const PhysicalRegisterInfo &PRI; - }; - - - // Optionally print the lane mask, if it is not ~0. - struct PrintLaneMaskOpt { - PrintLaneMaskOpt(LaneBitmask M) : Mask(M) {} - LaneBitmask Mask; - }; - raw_ostream &operator<< (raw_ostream &OS, const PrintLaneMaskOpt &P); - -} // namespace rdf -} // namespace llvm - -#endif - Index: lib/Target/Hexagon/RDFRegisters.cpp =================================================================== --- lib/Target/Hexagon/RDFRegisters.cpp +++ /dev/null @@ -1,337 +0,0 @@ -//===--- RDFRegisters.cpp ---------------------------------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "RDFRegisters.h" -#include "llvm/ADT/BitVector.h" -#include "llvm/CodeGen/MachineFunction.h" - -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; - } - } - - for (MCPhysReg R = 1, NR = TRI.getNumRegs(); R != NR; ++R) { - MCPhysReg SuperR = R; - for (MCSuperRegIterator S(R, &TRI, false); S.isValid(); ++S) - SuperR = *S; - RegInfos[R].MaxSuper = SuperR; - } - - 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()); -} - -std::set PhysicalRegisterInfo::getAliasSet(RegisterId Reg) const { - // Do not include RR in the alias set. - std::set AS; - assert(isRegMaskId(Reg) || TargetRegisterInfo::isPhysicalRegister(Reg)); - if (isRegMaskId(Reg)) { - // XXX SLOW - // XXX Add other regmasks to the set. - 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); - } - return AS; - } - - for (MCRegAliasIterator AI(Reg, &TRI, false); AI.isValid(); ++AI) - AS.insert(*AI); - return AS; -} - -bool PhysicalRegisterInfo::aliasRR(RegisterRef RA, RegisterRef RB) const { - assert(TargetRegisterInfo::isPhysicalRegister(RA.Reg)); - assert(TargetRegisterInfo::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()) { - std::pair PA = *UMA; - std::pair PB = *UMB; - if (PA.first == PB.first) { - // Lane mask of 0 (given by the iterator) should be treated as "full". - // This can happen when the register has only one unit, or when the - // unit corresponds to explicit aliasing. In such cases, the lane mask - // from RegisterRef should be ignored. - if (PA.second.none() || PB.second.none()) - return true; - - // At this point the common unit corresponds to a subregister. The lane - // masks correspond to the lane mask of that unit within the original - // register, for example assuming register quadruple q0 = r3:0, and - // a register pair d1 = r3:2, the lane mask of r2 in q0 may be 0b0100, - // while the lane mask of r2 in d1 may be 0b0001. - LaneBitmask LA = PA.second & RA.Mask; - LaneBitmask LB = PB.second & RB.Mask; - if (LA.any() && LB.any()) { - unsigned Root = *MCRegUnitRootIterator(PA.first, &TRI); - // If register units were guaranteed to only have 1 bit in any lane - // mask, the code below would not be necessary. This is because LA - // and LB would have at most 1 bit set each, and that bit would be - // guaranteed to correspond to the given register unit. - uint32_t SubA = TRI.getSubRegIndex(RA.Reg, Root); - uint32_t SubB = TRI.getSubRegIndex(RB.Reg, Root); - const TargetRegisterClass *RC = RegInfos[Root].RegClass; - LaneBitmask RCMask = RC != nullptr ? RC->LaneMask : LaneBitmask(0x1); - LaneBitmask MaskA = TRI.reverseComposeSubRegIndexLaneMask(SubA, LA); - LaneBitmask MaskB = TRI.reverseComposeSubRegIndexLaneMask(SubB, LB); - if ((MaskA & MaskB & RCMask).any()) - return true; - } - - ++UMA; - ++UMB; - continue; - } - if (PA.first < PB.first) - ++UMA; - else if (PB.first < PA.first) - ++UMB; - } - return false; -} - -bool PhysicalRegisterInfo::aliasRM(RegisterRef RR, RegisterRef RM) const { - assert(TargetRegisterInfo::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 RegisterAggr::normalize(RegisterRef RR) const { - if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) - return RR; - const TargetRegisterClass *RC = PRI.RegInfos[RR.Reg].RegClass; - LaneBitmask RCMask = RC != nullptr ? RC->LaneMask : LaneBitmask(0x00000001); - LaneBitmask Common = RR.Mask & RCMask; - - RegisterId SuperReg = PRI.RegInfos[RR.Reg].MaxSuper; -// Ex: IP/EIP/RIP -// assert(RC != nullptr || RR.Reg == SuperReg); - uint32_t Sub = PRI.getTRI().getSubRegIndex(SuperReg, RR.Reg); - LaneBitmask SuperMask = PRI.getTRI().composeSubRegIndexLaneMask(Sub, Common); - return RegisterRef(SuperReg, SuperMask); -} - -bool RegisterAggr::hasAliasOf(RegisterRef RR) const { - if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) { - // XXX SLOW - const uint32_t *MB = PRI.getRegMaskBits(RR.Reg); - for (unsigned i = 1, e = PRI.getTRI().getNumRegs(); i != e; ++i) { - if (MB[i/32] & (1u << (i%32))) - continue; - if (hasAliasOf(RegisterRef(i, LaneBitmask::getAll()))) - return true; - } - } - - RegisterRef NR = normalize(RR); - auto F = Masks.find(NR.Reg); - if (F != Masks.end()) { - if ((F->second & NR.Mask).any()) - return true; - } - if (CheckUnits) { - for (MCRegUnitIterator U(RR.Reg, &PRI.getTRI()); U.isValid(); ++U) - if (ExpAliasUnits.test(*U)) - return true; - } - return false; -} - -bool RegisterAggr::hasCoverOf(RegisterRef RR) const { - if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) { - // XXX SLOW - const uint32_t *MB = PRI.getRegMaskBits(RR.Reg); - for (unsigned i = 1, e = PRI.getTRI().getNumRegs(); i != e; ++i) { - if (MB[i/32] & (1u << (i%32))) - continue; - if (!hasCoverOf(RegisterRef(i, LaneBitmask::getAll()))) - return false; - } - return true; - } - - // Always have a cover for empty lane mask. - RegisterRef NR = normalize(RR); - if (NR.Mask.none()) - return true; - auto F = Masks.find(NR.Reg); - if (F == Masks.end()) - return false; - return (NR.Mask & F->second) == NR.Mask; -} - -RegisterAggr &RegisterAggr::insert(RegisterRef RR) { - if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) { - // XXX SLOW - const uint32_t *MB = PRI.getRegMaskBits(RR.Reg); - for (unsigned i = 1, e = PRI.getTRI().getNumRegs(); i != e; ++i) { - if (MB[i/32] & (1u << (i%32))) - continue; - insert(RegisterRef(i, LaneBitmask::getAll())); - } - return *this; - } - - RegisterRef NR = normalize(RR); - auto F = Masks.find(NR.Reg); - if (F == Masks.end()) - Masks.insert({NR.Reg, NR.Mask}); - else - F->second |= NR.Mask; - - // Visit all register units to see if there are any that were created - // by explicit aliases. Add those that were to the bit vector. - const TargetRegisterInfo &TRI = PRI.getTRI(); - for (MCRegUnitIterator U(RR.Reg, &TRI); U.isValid(); ++U) { - MCRegUnitRootIterator R(*U, &TRI); - ++R; - if (!R.isValid()) - continue; - ExpAliasUnits.set(*U); - CheckUnits = true; - } - return *this; -} - -RegisterAggr &RegisterAggr::insert(const RegisterAggr &RG) { - for (std::pair P : RG.Masks) - insert(RegisterRef(P.first, P.second)); - return *this; -} - -RegisterAggr &RegisterAggr::clear(RegisterRef RR) { - if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) { - // XXX SLOW - const uint32_t *MB = PRI.getRegMaskBits(RR.Reg); - for (unsigned i = 1, e = PRI.getTRI().getNumRegs(); i != e; ++i) { - if (MB[i/32] & (1u << (i%32))) - continue; - clear(RegisterRef(i, LaneBitmask::getAll())); - } - return *this; - } - - RegisterRef NR = normalize(RR); - auto F = Masks.find(NR.Reg); - if (F == Masks.end()) - return *this; - LaneBitmask NewM = F->second & ~NR.Mask; - if (NewM.none()) - Masks.erase(F); - else - F->second = NewM; - return *this; -} - -RegisterAggr &RegisterAggr::clear(const RegisterAggr &RG) { - for (std::pair P : RG.Masks) - clear(RegisterRef(P.first, P.second)); - return *this; -} - -RegisterRef RegisterAggr::clearIn(RegisterRef RR) const { - RegisterAggr T(PRI); - T.insert(RR).clear(*this); - if (T.empty()) - return RegisterRef(); - return RegisterRef(T.begin()->first, T.begin()->second); -} - -void RegisterAggr::print(raw_ostream &OS) const { - OS << '{'; - for (auto I : Masks) - OS << ' ' << PrintReg(I.first, &PRI.getTRI()) - << PrintLaneMaskOpt(I.second); - OS << " }"; -} -