diff options
Diffstat (limited to 'llvm/lib')
| -rw-r--r-- | llvm/lib/CodeGen/CMakeLists.txt | 3 | ||||
| -rw-r--r-- | llvm/lib/CodeGen/RDFGraph.cpp (renamed from llvm/lib/Target/Hexagon/RDFGraph.cpp) | 10 | ||||
| -rw-r--r-- | llvm/lib/CodeGen/RDFLiveness.cpp (renamed from llvm/lib/Target/Hexagon/RDFLiveness.cpp) | 6 | ||||
| -rw-r--r-- | llvm/lib/CodeGen/RDFRegisters.cpp (renamed from llvm/lib/Target/Hexagon/RDFRegisters.cpp) | 2 | ||||
| -rw-r--r-- | llvm/lib/Target/Hexagon/CMakeLists.txt | 3 | ||||
| -rw-r--r-- | llvm/lib/Target/Hexagon/HexagonOptAddrMode.cpp | 6 | ||||
| -rw-r--r-- | llvm/lib/Target/Hexagon/HexagonRDFOpt.cpp | 6 | ||||
| -rw-r--r-- | llvm/lib/Target/Hexagon/RDFCopy.cpp | 6 | ||||
| -rw-r--r-- | llvm/lib/Target/Hexagon/RDFCopy.h | 6 | ||||
| -rw-r--r-- | llvm/lib/Target/Hexagon/RDFDeadCode.cpp | 4 | ||||
| -rw-r--r-- | llvm/lib/Target/Hexagon/RDFDeadCode.h | 4 | ||||
| -rw-r--r-- | llvm/lib/Target/Hexagon/RDFGraph.h | 968 | ||||
| -rw-r--r-- | llvm/lib/Target/Hexagon/RDFLiveness.h | 151 | ||||
| -rw-r--r-- | llvm/lib/Target/Hexagon/RDFRegisters.h | 240 |
14 files changed, 29 insertions, 1386 deletions
diff --git a/llvm/lib/CodeGen/CMakeLists.txt b/llvm/lib/CodeGen/CMakeLists.txt index 470b027e38c..a3916b7c624 100644 --- a/llvm/lib/CodeGen/CMakeLists.txt +++ b/llvm/lib/CodeGen/CMakeLists.txt @@ -114,6 +114,9 @@ add_llvm_component_library(LLVMCodeGen ProcessImplicitDefs.cpp PrologEpilogInserter.cpp PseudoSourceValue.cpp + RDFGraph.cpp + RDFLiveness.cpp + RDFRegisters.cpp ReachingDefAnalysis.cpp RegAllocBase.cpp RegAllocBasic.cpp diff --git a/llvm/lib/Target/Hexagon/RDFGraph.cpp b/llvm/lib/CodeGen/RDFGraph.cpp index 0cb35dc9881..437a6b03009 100644 --- a/llvm/lib/Target/Hexagon/RDFGraph.cpp +++ b/llvm/lib/CodeGen/RDFGraph.cpp @@ -8,8 +8,6 @@ // // Target-independent, SSA-based data flow graph for register data flow (RDF). // -#include "RDFGraph.h" -#include "RDFRegisters.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" @@ -20,6 +18,8 @@ #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineOperand.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/RDFGraph.h" +#include "llvm/CodeGen/RDFRegisters.h" #include "llvm/CodeGen/TargetInstrInfo.h" #include "llvm/CodeGen/TargetLowering.h" #include "llvm/CodeGen/TargetRegisterInfo.h" @@ -753,8 +753,10 @@ RegisterSet DataFlowGraph::getLandingPadLiveIns() const { 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)); + if (!isFuncletEHPersonality(classifyEHPersonality(PF))) { + if (RegisterId R = TLI.getExceptionSelectorRegister(PF)) + LR.insert(RegisterRef(R)); + } return LR; } diff --git a/llvm/lib/Target/Hexagon/RDFLiveness.cpp b/llvm/lib/CodeGen/RDFLiveness.cpp index e2c007c9d01..0bcd27f8ea4 100644 --- a/llvm/lib/Target/Hexagon/RDFLiveness.cpp +++ b/llvm/lib/CodeGen/RDFLiveness.cpp @@ -22,9 +22,6 @@ // and Embedded Architectures and Compilers", 8 (4), // <10.1145/2086696.2086706>. <hal-00647369> // -#include "RDFLiveness.h" -#include "RDFGraph.h" -#include "RDFRegisters.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" @@ -33,6 +30,9 @@ #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/RDFLiveness.h" +#include "llvm/CodeGen/RDFGraph.h" +#include "llvm/CodeGen/RDFRegisters.h" #include "llvm/CodeGen/TargetRegisterInfo.h" #include "llvm/MC/LaneBitmask.h" #include "llvm/MC/MCRegisterInfo.h" diff --git a/llvm/lib/Target/Hexagon/RDFRegisters.cpp b/llvm/lib/CodeGen/RDFRegisters.cpp index b5675784e34..bd8661816e7 100644 --- a/llvm/lib/Target/Hexagon/RDFRegisters.cpp +++ b/llvm/lib/CodeGen/RDFRegisters.cpp @@ -6,11 +6,11 @@ // //===----------------------------------------------------------------------===// -#include "RDFRegisters.h" #include "llvm/ADT/BitVector.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineOperand.h" +#include "llvm/CodeGen/RDFRegisters.h" #include "llvm/CodeGen/TargetRegisterInfo.h" #include "llvm/MC/LaneBitmask.h" #include "llvm/MC/MCRegisterInfo.h" diff --git a/llvm/lib/Target/Hexagon/CMakeLists.txt b/llvm/lib/Target/Hexagon/CMakeLists.txt index 3536aa81fb2..747f14e0cec 100644 --- a/llvm/lib/Target/Hexagon/CMakeLists.txt +++ b/llvm/lib/Target/Hexagon/CMakeLists.txt @@ -64,9 +64,6 @@ add_llvm_target(HexagonCodeGen HexagonVLIWPacketizer.cpp RDFCopy.cpp RDFDeadCode.cpp - RDFGraph.cpp - RDFLiveness.cpp - RDFRegisters.cpp ) add_subdirectory(AsmParser) diff --git a/llvm/lib/Target/Hexagon/HexagonOptAddrMode.cpp b/llvm/lib/Target/Hexagon/HexagonOptAddrMode.cpp index 886034d9601..f1fe51f5e54 100644 --- a/llvm/lib/Target/Hexagon/HexagonOptAddrMode.cpp +++ b/llvm/lib/Target/Hexagon/HexagonOptAddrMode.cpp @@ -12,9 +12,6 @@ #include "HexagonInstrInfo.h" #include "HexagonSubtarget.h" #include "MCTargetDesc/HexagonBaseInfo.h" -#include "RDFGraph.h" -#include "RDFLiveness.h" -#include "RDFRegisters.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/StringRef.h" @@ -27,6 +24,9 @@ #include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineOperand.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/RDFGraph.h" +#include "llvm/CodeGen/RDFLiveness.h" +#include "llvm/CodeGen/RDFRegisters.h" #include "llvm/CodeGen/TargetSubtargetInfo.h" #include "llvm/InitializePasses.h" #include "llvm/MC/MCInstrDesc.h" diff --git a/llvm/lib/Target/Hexagon/HexagonRDFOpt.cpp b/llvm/lib/Target/Hexagon/HexagonRDFOpt.cpp index 517ad1c6ee7..f26e23befde 100644 --- a/llvm/lib/Target/Hexagon/HexagonRDFOpt.cpp +++ b/llvm/lib/Target/Hexagon/HexagonRDFOpt.cpp @@ -11,9 +11,6 @@ #include "MCTargetDesc/HexagonBaseInfo.h" #include "RDFCopy.h" #include "RDFDeadCode.h" -#include "RDFGraph.h" -#include "RDFLiveness.h" -#include "RDFRegisters.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" @@ -24,6 +21,9 @@ #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineOperand.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/RDFGraph.h" +#include "llvm/CodeGen/RDFLiveness.h" +#include "llvm/CodeGen/RDFRegisters.h" #include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/CommandLine.h" diff --git a/llvm/lib/Target/Hexagon/RDFCopy.cpp b/llvm/lib/Target/Hexagon/RDFCopy.cpp index a9d39fd4b2d..34d58f0a7a2 100644 --- a/llvm/lib/Target/Hexagon/RDFCopy.cpp +++ b/llvm/lib/Target/Hexagon/RDFCopy.cpp @@ -11,13 +11,13 @@ //===----------------------------------------------------------------------===// #include "RDFCopy.h" -#include "RDFGraph.h" -#include "RDFLiveness.h" -#include "RDFRegisters.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineOperand.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/RDFGraph.h" +#include "llvm/CodeGen/RDFLiveness.h" +#include "llvm/CodeGen/RDFRegisters.h" #include "llvm/CodeGen/TargetOpcodes.h" #include "llvm/CodeGen/TargetRegisterInfo.h" #include "llvm/MC/MCRegisterInfo.h" diff --git a/llvm/lib/Target/Hexagon/RDFCopy.h b/llvm/lib/Target/Hexagon/RDFCopy.h index 1450ab88484..99b18a75d8c 100644 --- a/llvm/lib/Target/Hexagon/RDFCopy.h +++ b/llvm/lib/Target/Hexagon/RDFCopy.h @@ -9,9 +9,9 @@ #ifndef LLVM_LIB_TARGET_HEXAGON_RDFCOPY_H #define LLVM_LIB_TARGET_HEXAGON_RDFCOPY_H -#include "RDFGraph.h" -#include "RDFLiveness.h" -#include "RDFRegisters.h" +#include "llvm/CodeGen/RDFGraph.h" +#include "llvm/CodeGen/RDFLiveness.h" +#include "llvm/CodeGen/RDFRegisters.h" #include "llvm/CodeGen/MachineFunction.h" #include <map> #include <vector> diff --git a/llvm/lib/Target/Hexagon/RDFDeadCode.cpp b/llvm/lib/Target/Hexagon/RDFDeadCode.cpp index af86c7b1956..5a98debd3c0 100644 --- a/llvm/lib/Target/Hexagon/RDFDeadCode.cpp +++ b/llvm/lib/Target/Hexagon/RDFDeadCode.cpp @@ -9,13 +9,13 @@ // RDF-based generic dead code elimination. #include "RDFDeadCode.h" -#include "RDFGraph.h" -#include "RDFLiveness.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 "llvm/Support/Debug.h" #include <queue> diff --git a/llvm/lib/Target/Hexagon/RDFDeadCode.h b/llvm/lib/Target/Hexagon/RDFDeadCode.h index 7f91977e1d6..859c8161d35 100644 --- a/llvm/lib/Target/Hexagon/RDFDeadCode.h +++ b/llvm/lib/Target/Hexagon/RDFDeadCode.h @@ -23,8 +23,8 @@ #ifndef RDF_DEADCODE_H #define RDF_DEADCODE_H -#include "RDFGraph.h" -#include "RDFLiveness.h" +#include "llvm/CodeGen/RDFGraph.h" +#include "llvm/CodeGen/RDFLiveness.h" #include "llvm/ADT/SetVector.h" namespace llvm { diff --git a/llvm/lib/Target/Hexagon/RDFGraph.h b/llvm/lib/Target/Hexagon/RDFGraph.h deleted file mode 100644 index 585f43e116f..00000000000 --- a/llvm/lib/Target/Hexagon/RDFGraph.h +++ /dev/null @@ -1,968 +0,0 @@ -//===- RDFGraph.h -----------------------------------------------*- C++ -*-===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// -// -// Target-independent, SSA-based data flow graph for register data flow (RDF) -// 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<r0>(,d12,u9):] -// p5: phi [d6<r1>(,,u10):] -// s7: add [d8<r2>(,,u13):, u9<r0>(d4):, u10<r1>(d6):] -// s11: addi [d12<r0>(d4,,u15):, u13<r2>(d8):] -// s14: ret [u15<r0>(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<R>(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<R>[!](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, implicit 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<r0>(,,u9):] -// s3: set [d4<r1>(,,u10):] -// s5: addi [d6<t1>(,,):, u7"<t0>(d2):, u8"<t0>(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/SmallVector.h" -#include "llvm/MC/LaneBitmask.h" -#include "llvm/Support/Allocator.h" -#include "llvm/Support/MathExtras.h" -#include <cassert> -#include <cstdint> -#include <cstring> -#include <map> -#include <set> -#include <unordered_map> -#include <utility> -#include <vector> - -// 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 MachineDominanceFrontier; -class MachineDominatorTree; -class MachineFunction; -class MachineInstr; -class MachineOperand; -class raw_ostream; -class TargetInstrInfo; -class TargetRegisterInfo; - -namespace rdf { - - using NodeId = uint32_t; - - 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 <typename T> struct NodeAddr { - NodeAddr() = default; - NodeAddr(T A, NodeId I) : Addr(A), Id(I) {} - - // Type cast (casting constructor). The reason for having this class - // instead of std::pair. - template <typename S> NodeAddr(const NodeAddr<S> &NA) - : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {} - - bool operator== (const NodeAddr<T> &NA) const { - assert((Addr == NA.Addr) == (Id == NA.Id)); - return Addr == NA.Addr; - } - bool operator!= (const NodeAddr<T> &NA) const { - return !operator==(NA); - } - - T Addr = nullptr; - 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<NodeBase*>(Blocks[BlockN]+Offset); - } - - NodeId id(const NodeBase *P) const; - NodeAddr<NodeBase*> 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<char*> Blocks; - using AllocatorTy = BumpPtrAllocatorImpl<MallocAllocator, 65536>; - AllocatorTy MemPool; - }; - - using RegisterSet = std::set<RegisterRef>; - - 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<LaneBitmask> { - 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<NodeBase*> 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"); - - using NodeList = SmallVector<NodeAddr<NodeBase *>, 4>; - using NodeSet = std::set<NodeId>; - - 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 <typename Predicate> - NodeAddr<RefNode*> getNextRef(RegisterRef RR, Predicate P, bool NextOnly, - const DataFlowGraph &G); - NodeAddr<NodeBase*> 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<DefNode*> DA); - }; - - struct UseNode : public RefNode { - void linkToDef(NodeId Self, NodeAddr<DefNode*> 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 <typename T> T getCode() const { - return static_cast<T>(Code.CP); - } - void setCode(void *C) { - Code.CP = C; - } - - NodeAddr<NodeBase*> getFirstMember(const DataFlowGraph &G) const; - NodeAddr<NodeBase*> getLastMember(const DataFlowGraph &G) const; - void addMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G); - void addMemberAfter(NodeAddr<NodeBase*> MA, NodeAddr<NodeBase*> NA, - const DataFlowGraph &G); - void removeMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G); - - NodeList members(const DataFlowGraph &G) const; - template <typename Predicate> - NodeList members_if(Predicate P, const DataFlowGraph &G) const; - }; - - struct InstrNode : public CodeNode { - NodeAddr<NodeBase*> getOwner(const DataFlowGraph &G); - }; - - struct PhiNode : public InstrNode { - MachineInstr *getCode() const { - return nullptr; - } - }; - - struct StmtNode : public InstrNode { - MachineInstr *getCode() const { - return CodeNode::getCode<MachineInstr*>(); - } - }; - - struct BlockNode : public CodeNode { - MachineBasicBlock *getCode() const { - return CodeNode::getCode<MachineBasicBlock*>(); - } - - void addPhi(NodeAddr<PhiNode*> PA, const DataFlowGraph &G); - }; - - struct FuncNode : public CodeNode { - MachineFunction *getCode() const { - return CodeNode::getCode<MachineFunction*>(); - } - - NodeAddr<BlockNode*> findBlock(const MachineBasicBlock *BB, - const DataFlowGraph &G) const; - NodeAddr<BlockNode*> 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 <typename T> T ptr(NodeId N) const { - return static_cast<T>(ptr(N)); - } - - NodeId id(const NodeBase *P) const; - - template <typename T> NodeAddr<T> addr(NodeId N) const { - return { ptr<T>(N), N }; - } - - NodeAddr<FuncNode*> 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: - using value_type = NodeAddr<DefNode *>; - struct Iterator { - using value_type = DefStack::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: - friend struct DefStack; - - 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; - }; - - public: - using iterator = Iterator; - - iterator top() const { return Iterator(*this, true); } - iterator bottom() const { return Iterator(*this, false); } - unsigned size() const; - - void push(NodeAddr<DefNode*> DA) { Stack.push_back(DA); } - void pop(); - void start_block(NodeId N); - void clear_block(NodeId N); - - private: - friend struct Iterator; - - using StorageType = std::vector<value_type>; - - 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 - using DefStackMap = std::unordered_map<RegisterId, DefStack>; - - void build(unsigned Options = BuildOptions::None); - void pushAllDefs(NodeAddr<InstrNode*> 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 restrictRef(RegisterRef AR, RegisterRef BR) const; - - NodeAddr<RefNode*> getNextRelated(NodeAddr<InstrNode*> IA, - NodeAddr<RefNode*> RA) const; - NodeAddr<RefNode*> getNextImp(NodeAddr<InstrNode*> IA, - NodeAddr<RefNode*> RA, bool Create); - NodeAddr<RefNode*> getNextImp(NodeAddr<InstrNode*> IA, - NodeAddr<RefNode*> RA) const; - NodeAddr<RefNode*> getNextShadow(NodeAddr<InstrNode*> IA, - NodeAddr<RefNode*> RA, bool Create); - NodeAddr<RefNode*> getNextShadow(NodeAddr<InstrNode*> IA, - NodeAddr<RefNode*> RA) const; - - NodeList getRelatedRefs(NodeAddr<InstrNode*> IA, - NodeAddr<RefNode*> RA) const; - - NodeAddr<BlockNode*> findBlock(MachineBasicBlock *BB) const { - return BlockNodes.at(BB); - } - - void unlinkUse(NodeAddr<UseNode*> UA, bool RemoveFromOwner) { - unlinkUseDF(UA); - if (RemoveFromOwner) - removeFromOwner(UA); - } - - void unlinkDef(NodeAddr<DefNode*> DA, bool RemoveFromOwner) { - unlinkDefDF(DA); - if (RemoveFromOwner) - removeFromOwner(DA); - } - - // Some useful filters. - template <uint16_t Kind> - static bool IsRef(const NodeAddr<NodeBase*> BA) { - return BA.Addr->getType() == NodeAttrs::Ref && - BA.Addr->getKind() == Kind; - } - - template <uint16_t Kind> - static bool IsCode(const NodeAddr<NodeBase*> BA) { - return BA.Addr->getType() == NodeAttrs::Code && - BA.Addr->getKind() == Kind; - } - - static bool IsDef(const NodeAddr<NodeBase*> BA) { - return BA.Addr->getType() == NodeAttrs::Ref && - BA.Addr->getKind() == NodeAttrs::Def; - } - - static bool IsUse(const NodeAddr<NodeBase*> BA) { - return BA.Addr->getType() == NodeAttrs::Ref && - BA.Addr->getKind() == NodeAttrs::Use; - } - - static bool IsPhi(const NodeAddr<NodeBase*> BA) { - return BA.Addr->getType() == NodeAttrs::Code && - BA.Addr->getKind() == NodeAttrs::Phi; - } - - static bool IsPreservingDef(const NodeAddr<DefNode*> DA) { - uint16_t Flags = DA.Addr->getFlags(); - return (Flags & NodeAttrs::Preserving) && !(Flags & NodeAttrs::Undef); - } - - private: - void reset(); - - RegisterSet getLandingPadLiveIns() const; - - NodeAddr<NodeBase*> newNode(uint16_t Attrs); - NodeAddr<NodeBase*> cloneNode(const NodeAddr<NodeBase*> B); - NodeAddr<UseNode*> newUse(NodeAddr<InstrNode*> Owner, - MachineOperand &Op, uint16_t Flags = NodeAttrs::None); - NodeAddr<PhiUseNode*> newPhiUse(NodeAddr<PhiNode*> Owner, - RegisterRef RR, NodeAddr<BlockNode*> PredB, - uint16_t Flags = NodeAttrs::PhiRef); - NodeAddr<DefNode*> newDef(NodeAddr<InstrNode*> Owner, - MachineOperand &Op, uint16_t Flags = NodeAttrs::None); - NodeAddr<DefNode*> newDef(NodeAddr<InstrNode*> Owner, - RegisterRef RR, uint16_t Flags = NodeAttrs::PhiRef); - NodeAddr<PhiNode*> newPhi(NodeAddr<BlockNode*> Owner); - NodeAddr<StmtNode*> newStmt(NodeAddr<BlockNode*> Owner, - MachineInstr *MI); - NodeAddr<BlockNode*> newBlock(NodeAddr<FuncNode*> Owner, - MachineBasicBlock *BB); - NodeAddr<FuncNode*> newFunc(MachineFunction *MF); - - template <typename Predicate> - std::pair<NodeAddr<RefNode*>,NodeAddr<RefNode*>> - locateNextRef(NodeAddr<InstrNode*> IA, NodeAddr<RefNode*> RA, - Predicate P) const; - - using BlockRefsMap = std::map<NodeId, RegisterSet>; - - void buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In); - void recordDefsForDF(BlockRefsMap &PhiM, NodeAddr<BlockNode*> BA); - void buildPhis(BlockRefsMap &PhiM, RegisterSet &AllRefs, - NodeAddr<BlockNode*> BA); - void removeUnusedPhis(); - - void pushClobbers(NodeAddr<InstrNode*> IA, DefStackMap &DM); - void pushDefs(NodeAddr<InstrNode*> IA, DefStackMap &DM); - template <typename T> void linkRefUp(NodeAddr<InstrNode*> IA, - NodeAddr<T> TA, DefStack &DS); - template <typename Predicate> void linkStmtRefs(DefStackMap &DefM, - NodeAddr<StmtNode*> SA, Predicate P); - void linkBlockRefs(DefStackMap &DefM, NodeAddr<BlockNode*> BA); - - void unlinkUseDF(NodeAddr<UseNode*> UA); - void unlinkDefDF(NodeAddr<DefNode*> DA); - - void removeFromOwner(NodeAddr<RefNode*> RA) { - NodeAddr<InstrNode*> IA = RA.Addr->getOwner(*this); - IA.Addr->removeMember(RA, *this); - } - - MachineFunction &MF; - const TargetInstrInfo &TII; - const TargetRegisterInfo &TRI; - const PhysicalRegisterInfo PRI; - const MachineDominatorTree &MDT; - const MachineDominanceFrontier &MDF; - const TargetOperandInfo &TOI; - - RegisterAggr LiveIns; - NodeAddr<FuncNode*> Func; - NodeAllocator Memory; - // Local map: MachineBasicBlock -> NodeAddr<BlockNode*> - std::map<MachineBasicBlock*,NodeAddr<BlockNode*>> BlockNodes; - // Lane mask map. - LaneMaskIndex LMI; - }; // struct DataFlowGraph - - template <typename Predicate> - NodeAddr<RefNode*> 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<NodeBase*>(getNext()); - - while (NA.Addr != this) { - if (NA.Addr->getType() == NodeAttrs::Ref) { - NodeAddr<RefNode*> RA = NA; - if (RA.Addr->getRegRef(G) == RR && P(NA)) - return NA; - if (NextOnly) - break; - NA = G.addr<NodeBase*>(NA.Addr->getNext()); - } else { - // We've hit the beginning of the chain. - assert(NA.Addr->getType() == NodeAttrs::Code); - NodeAddr<CodeNode*> CA = NA; - NA = CA.Addr->getFirstMember(G); - } - } - // Return the equivalent of "nullptr" if such a node was not found. - return NodeAddr<RefNode*>(); - } - - template <typename Predicate> - 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<NodeBase*>(M.Addr->getNext()); - } - return MM; - } - - template <typename T> - struct Print { - Print(const T &x, const DataFlowGraph &g) : Obj(x), G(g) {} - - const T &Obj; - const DataFlowGraph &G; - }; - - template <typename T> - struct PrintNode : Print<NodeAddr<T>> { - PrintNode(const NodeAddr<T> &x, const DataFlowGraph &g) - : Print<NodeAddr<T>>(x, g) {} - }; - - raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterRef> &P); - raw_ostream &operator<<(raw_ostream &OS, const Print<NodeId> &P); - raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<DefNode *>> &P); - raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<UseNode *>> &P); - raw_ostream &operator<<(raw_ostream &OS, - const Print<NodeAddr<PhiUseNode *>> &P); - raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<RefNode *>> &P); - raw_ostream &operator<<(raw_ostream &OS, const Print<NodeList> &P); - raw_ostream &operator<<(raw_ostream &OS, const Print<NodeSet> &P); - raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<PhiNode *>> &P); - raw_ostream &operator<<(raw_ostream &OS, - const Print<NodeAddr<StmtNode *>> &P); - raw_ostream &operator<<(raw_ostream &OS, - const Print<NodeAddr<InstrNode *>> &P); - raw_ostream &operator<<(raw_ostream &OS, - const Print<NodeAddr<BlockNode *>> &P); - raw_ostream &operator<<(raw_ostream &OS, - const Print<NodeAddr<FuncNode *>> &P); - raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterSet> &P); - raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterAggr> &P); - raw_ostream &operator<<(raw_ostream &OS, - const Print<DataFlowGraph::DefStack> &P); - -} // end namespace rdf - -} // end namespace llvm - -#endif // LLVM_LIB_TARGET_HEXAGON_RDFGRAPH_H diff --git a/llvm/lib/Target/Hexagon/RDFLiveness.h b/llvm/lib/Target/Hexagon/RDFLiveness.h deleted file mode 100644 index ea489027172..00000000000 --- a/llvm/lib/Target/Hexagon/RDFLiveness.h +++ /dev/null @@ -1,151 +0,0 @@ -//===- RDFLiveness.h --------------------------------------------*- C++ -*-===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// -// -// Recalculate the liveness information given a data flow graph. -// This includes block live-ins and kill flags. - -#ifndef LLVM_LIB_TARGET_HEXAGON_RDFLIVENESS_H -#define LLVM_LIB_TARGET_HEXAGON_RDFLIVENESS_H - -#include "RDFGraph.h" -#include "RDFRegisters.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/MC/LaneBitmask.h" -#include <map> -#include <set> -#include <utility> - -namespace llvm { - -class MachineBasicBlock; -class MachineDominanceFrontier; -class MachineDominatorTree; -class MachineRegisterInfo; -class TargetRegisterInfo; - -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<MachineBasicBlock*,RegisterAggr> Map; - }; - - using NodeRef = std::pair<NodeId, LaneBitmask>; - using NodeRefSet = std::set<NodeRef>; - // RegisterId in RefMap must be normalized. - using RefMap = std::map<RegisterId, NodeRefSet>; - - Liveness(MachineRegisterInfo &mri, const DataFlowGraph &g) - : DFG(g), TRI(g.getTRI()), PRI(g.getPRI()), MDT(g.getDT()), - MDF(g.getDF()), LiveMap(g.getPRI()), Empty(), NoRegs(g.getPRI()) {} - - NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr<RefNode*> RefA, - bool TopShadows, bool FullChain, const RegisterAggr &DefRRs); - - NodeList getAllReachingDefs(NodeAddr<RefNode*> RefA) { - return getAllReachingDefs(RefA.Addr->getRegRef(DFG), RefA, false, - false, NoRegs); - } - - NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr<RefNode*> RefA) { - return getAllReachingDefs(RefRR, RefA, false, false, NoRegs); - } - - NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr<DefNode*> DefA, - const RegisterAggr &DefRRs); - - NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr<DefNode*> DefA) { - return getAllReachedUses(RefRR, DefA, NoRegs); - } - - std::pair<NodeSet,bool> getAllReachingDefsRec(RegisterRef RefRR, - NodeAddr<RefNode*> RefA, NodeSet &Visited, const NodeSet &Defs); - - NodeAddr<RefNode*> getNearestAliasedRef(RegisterRef RefRR, - NodeAddr<InstrNode*> IA); - - 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; - LiveMapType LiveMap; - const RefMap Empty; - const RegisterAggr NoRegs; - bool Trace = false; - - // 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. - using NodeBlockMap = DenseMap<NodeId, MachineBasicBlock *>; - NodeBlockMap NBMap; - - // Phi information: - // - // RealUseMap - // map: NodeId -> (map: RegisterId -> NodeRefSet) - // phi id -> (map: register -> set of reached non-phi uses) - std::map<NodeId, RefMap> RealUseMap; - - // Inverse iterated dominance frontier. - std::map<MachineBasicBlock*,std::set<MachineBasicBlock*>> IIDF; - - // Live on entry. - std::map<MachineBasicBlock*,RefMap> 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<MachineBasicBlock*,RefMap> PhiLOX; - - MachineBasicBlock *getBlockWithRef(NodeId RN) const; - void traverse(MachineBasicBlock *B, RefMap &LiveIn); - void emptify(RefMap &M); - - std::pair<NodeSet,bool> getAllReachingDefsRecImpl(RegisterRef RefRR, - NodeAddr<RefNode*> RefA, NodeSet &Visited, const NodeSet &Defs, - unsigned Nest, unsigned MaxNest); - }; - - raw_ostream &operator<<(raw_ostream &OS, const Print<Liveness::RefMap> &P); - -} // end namespace rdf - -} // end namespace llvm - -#endif // LLVM_LIB_TARGET_HEXAGON_RDFLIVENESS_H diff --git a/llvm/lib/Target/Hexagon/RDFRegisters.h b/llvm/lib/Target/Hexagon/RDFRegisters.h deleted file mode 100644 index 4afaf80e465..00000000000 --- a/llvm/lib/Target/Hexagon/RDFRegisters.h +++ /dev/null @@ -1,240 +0,0 @@ -//===- RDFRegisters.h -------------------------------------------*- C++ -*-===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_LIB_TARGET_HEXAGON_RDFREGISTERS_H -#define LLVM_LIB_TARGET_HEXAGON_RDFREGISTERS_H - -#include "llvm/ADT/BitVector.h" -#include "llvm/ADT/STLExtras.h" -#include "llvm/CodeGen/TargetRegisterInfo.h" -#include "llvm/MC/LaneBitmask.h" -#include <cassert> -#include <cstdint> -#include <map> -#include <set> -#include <vector> - -namespace llvm { - -class MachineFunction; -class raw_ostream; - -namespace rdf { - - using RegisterId = uint32_t; - - // 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 <typename T, unsigned N = 32> - struct IndexedSet { - IndexedSet() { 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; - } - - uint32_t size() const { return Map.size(); } - - using const_iterator = typename std::vector<T>::const_iterator; - - const_iterator begin() const { return Map.begin(); } - const_iterator end() const { return Map.end(); } - - private: - std::vector<T> 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 Register::isStackSlot(R); - } - - RegisterId getRegMaskId(const uint32_t *RM) const { - return Register::index2StackSlot(RegMasks.find(RM)); - } - - const uint32_t *getRegMaskBits(RegisterId R) const { - return RegMasks.get(Register::stackSlot2Index(R)); - } - - RegisterRef normalize(RegisterRef RR) const; - - 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<RegisterId> getAliasSet(RegisterId Reg) const; - - RegisterRef getRefForUnit(uint32_t U) const { - return RegisterRef(UnitInfos[U].Reg, UnitInfos[U].Mask); - } - - const BitVector &getMaskUnits(RegisterId MaskId) const { - return MaskInfos[Register::stackSlot2Index(MaskId)].Units; - } - - RegisterRef mapTo(RegisterRef RR, unsigned R) const; - const TargetRegisterInfo &getTRI() const { return TRI; } - - private: - struct RegInfo { - const TargetRegisterClass *RegClass = nullptr; - }; - struct UnitInfo { - RegisterId Reg = 0; - LaneBitmask Mask; - }; - struct MaskInfo { - BitVector Units; - }; - - const TargetRegisterInfo &TRI; - IndexedSet<const uint32_t*> RegMasks; - std::vector<RegInfo> RegInfos; - std::vector<UnitInfo> UnitInfos; - std::vector<MaskInfo> MaskInfos; - - 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) - : Units(pri.getTRI().getNumRegUnits()), PRI(pri) {} - RegisterAggr(const RegisterAggr &RG) = default; - - bool empty() const { return Units.none(); } - 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 &intersect(RegisterRef RR); - RegisterAggr &intersect(const RegisterAggr &RG); - RegisterAggr &clear(RegisterRef RR); - RegisterAggr &clear(const RegisterAggr &RG); - - RegisterRef intersectWith(RegisterRef RR) const; - RegisterRef clearIn(RegisterRef RR) const; - RegisterRef makeRegRef() const; - - void print(raw_ostream &OS) const; - - struct rr_iterator { - using MapType = std::map<RegisterId, LaneBitmask>; - - private: - MapType Masks; - MapType::iterator Pos; - unsigned Index; - const RegisterAggr *Owner; - - public: - rr_iterator(const RegisterAggr &RG, bool End); - - RegisterRef operator*() const { - return RegisterRef(Pos->first, Pos->second); - } - - rr_iterator &operator++() { - ++Pos; - ++Index; - return *this; - } - - bool operator==(const rr_iterator &I) const { - assert(Owner == I.Owner); - (void)Owner; - return Index == I.Index; - } - - bool operator!=(const rr_iterator &I) const { - return !(*this == I); - } - }; - - rr_iterator rr_begin() const { - return rr_iterator(*this, false); - } - rr_iterator rr_end() const { - return rr_iterator(*this, true); - } - - private: - BitVector Units; - 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); - -} // end namespace rdf - -} // end namespace llvm - -#endif // LLVM_LIB_TARGET_HEXAGON_RDFREGISTERS_H |
