From owner-svn-src-head@freebsd.org Thu Jun 25 08:15:11 2020 Return-Path: Delivered-To: svn-src-head@mailman.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.nyi.freebsd.org (Postfix) with ESMTP id C138C355159; Thu, 25 Jun 2020 08:15:11 +0000 (UTC) (envelope-from dim@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "Let's Encrypt Authority X3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 49st9W4tyKz3X0Q; Thu, 25 Jun 2020 08:15:11 +0000 (UTC) (envelope-from dim@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id A2AA62012A; Thu, 25 Jun 2020 08:15:11 +0000 (UTC) (envelope-from dim@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id 05P8FBu5059934; Thu, 25 Jun 2020 08:15:11 GMT (envelope-from dim@FreeBSD.org) Received: (from dim@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id 05P8FAcW059926; Thu, 25 Jun 2020 08:15:10 GMT (envelope-from dim@FreeBSD.org) Message-Id: <202006250815.05P8FAcW059926@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: dim set sender to dim@FreeBSD.org using -f From: Dimitry Andric Date: Thu, 25 Jun 2020 08:15:10 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r362609 - in head: contrib/llvm-project/clang/include/clang/Driver contrib/llvm-project/clang/lib/Basic/Targets contrib/llvm-project/clang/lib/Driver contrib/llvm-project/clang/lib/Driv... X-SVN-Group: head X-SVN-Commit-Author: dim X-SVN-Commit-Paths: in head: contrib/llvm-project/clang/include/clang/Driver contrib/llvm-project/clang/lib/Basic/Targets contrib/llvm-project/clang/lib/Driver contrib/llvm-project/clang/lib/Driver/ToolChains/Arch contri... X-SVN-Commit-Revision: 362609 X-SVN-Commit-Repository: base MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-head@freebsd.org X-Mailman-Version: 2.1.33 Precedence: list List-Id: SVN commit messages for the src tree for head/-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 25 Jun 2020 08:15:11 -0000 Author: dim Date: Thu Jun 25 08:15:10 2020 New Revision: 362609 URL: https://svnweb.freebsd.org/changeset/base/362609 Log: Merge llvm, clang, compiler-rt, libc++, libunwind, lld, lldb and openmp llvmorg-10.0.0-129-gd24d5c8e308. Getting closer to 10.0.1-rc2. MFC after: 3 weeks Added: head/contrib/llvm-project/llvm/include/llvm/CodeGen/RDFGraph.h - copied unchanged from r362594, vendor/llvm-project/release-10.x/llvm/include/llvm/CodeGen/RDFGraph.h head/contrib/llvm-project/llvm/include/llvm/CodeGen/RDFLiveness.h - copied unchanged from r362594, vendor/llvm-project/release-10.x/llvm/include/llvm/CodeGen/RDFLiveness.h head/contrib/llvm-project/llvm/include/llvm/CodeGen/RDFRegisters.h - copied unchanged from r362594, vendor/llvm-project/release-10.x/llvm/include/llvm/CodeGen/RDFRegisters.h head/contrib/llvm-project/llvm/lib/CodeGen/RDFGraph.cpp - copied unchanged from r362594, vendor/llvm-project/release-10.x/llvm/lib/CodeGen/RDFGraph.cpp head/contrib/llvm-project/llvm/lib/CodeGen/RDFLiveness.cpp - copied unchanged from r362594, vendor/llvm-project/release-10.x/llvm/lib/CodeGen/RDFLiveness.cpp head/contrib/llvm-project/llvm/lib/CodeGen/RDFRegisters.cpp - copied unchanged from r362594, vendor/llvm-project/release-10.x/llvm/lib/CodeGen/RDFRegisters.cpp head/contrib/llvm-project/llvm/lib/Target/X86/ImmutableGraph.h - copied unchanged from r362594, vendor/llvm-project/release-10.x/llvm/lib/Target/X86/ImmutableGraph.h head/contrib/llvm-project/llvm/lib/Target/X86/X86IndirectThunks.cpp - copied unchanged from r362594, vendor/llvm-project/release-10.x/llvm/lib/Target/X86/X86IndirectThunks.cpp head/contrib/llvm-project/llvm/lib/Target/X86/X86LoadValueInjectionLoadHardening.cpp - copied unchanged from r362594, vendor/llvm-project/release-10.x/llvm/lib/Target/X86/X86LoadValueInjectionLoadHardening.cpp head/contrib/llvm-project/llvm/lib/Target/X86/X86LoadValueInjectionRetHardening.cpp - copied unchanged from r362594, vendor/llvm-project/release-10.x/llvm/lib/Target/X86/X86LoadValueInjectionRetHardening.cpp Deleted: head/contrib/llvm-project/llvm/lib/Target/Hexagon/RDFGraph.cpp head/contrib/llvm-project/llvm/lib/Target/Hexagon/RDFGraph.h head/contrib/llvm-project/llvm/lib/Target/Hexagon/RDFLiveness.cpp head/contrib/llvm-project/llvm/lib/Target/Hexagon/RDFLiveness.h head/contrib/llvm-project/llvm/lib/Target/Hexagon/RDFRegisters.cpp head/contrib/llvm-project/llvm/lib/Target/Hexagon/RDFRegisters.h head/contrib/llvm-project/llvm/lib/Target/X86/X86RetpolineThunks.cpp Modified: head/contrib/llvm-project/clang/include/clang/Driver/Options.td head/contrib/llvm-project/clang/lib/Basic/Targets/PPC.h head/contrib/llvm-project/clang/lib/Driver/SanitizerArgs.cpp head/contrib/llvm-project/clang/lib/Driver/ToolChain.cpp head/contrib/llvm-project/clang/lib/Driver/ToolChains/Arch/X86.cpp head/contrib/llvm-project/llvm/include/llvm/IR/IntrinsicsPowerPC.td head/contrib/llvm-project/llvm/include/llvm/Support/ManagedStatic.h head/contrib/llvm-project/llvm/include/llvm/Target/TargetSelectionDAG.td head/contrib/llvm-project/llvm/lib/LTO/LTO.cpp head/contrib/llvm-project/llvm/lib/Target/BPF/BPFISelDAGToDAG.cpp head/contrib/llvm-project/llvm/lib/Target/BPF/BTFDebug.cpp head/contrib/llvm-project/llvm/lib/Target/Hexagon/HexagonOptAddrMode.cpp head/contrib/llvm-project/llvm/lib/Target/Hexagon/HexagonRDFOpt.cpp head/contrib/llvm-project/llvm/lib/Target/Hexagon/RDFCopy.cpp head/contrib/llvm-project/llvm/lib/Target/Hexagon/RDFCopy.h head/contrib/llvm-project/llvm/lib/Target/Hexagon/RDFDeadCode.cpp head/contrib/llvm-project/llvm/lib/Target/Hexagon/RDFDeadCode.h head/contrib/llvm-project/llvm/lib/Target/PowerPC/P9InstrResources.td head/contrib/llvm-project/llvm/lib/Target/PowerPC/PPC.td head/contrib/llvm-project/llvm/lib/Target/PowerPC/PPCISelLowering.cpp head/contrib/llvm-project/llvm/lib/Target/PowerPC/PPCISelLowering.h head/contrib/llvm-project/llvm/lib/Target/PowerPC/PPCInstrAltivec.td head/contrib/llvm-project/llvm/lib/Target/PowerPC/PPCInstrInfo.cpp head/contrib/llvm-project/llvm/lib/Target/PowerPC/PPCInstrVSX.td head/contrib/llvm-project/llvm/lib/Target/PowerPC/PPCSubtarget.h head/contrib/llvm-project/llvm/lib/Target/X86/X86.h head/contrib/llvm-project/llvm/lib/Target/X86/X86.td head/contrib/llvm-project/llvm/lib/Target/X86/X86FastISel.cpp head/contrib/llvm-project/llvm/lib/Target/X86/X86FrameLowering.cpp head/contrib/llvm-project/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp head/contrib/llvm-project/llvm/lib/Target/X86/X86ISelLowering.cpp head/contrib/llvm-project/llvm/lib/Target/X86/X86ISelLowering.h head/contrib/llvm-project/llvm/lib/Target/X86/X86InstrCompiler.td head/contrib/llvm-project/llvm/lib/Target/X86/X86InstrControl.td head/contrib/llvm-project/llvm/lib/Target/X86/X86InstrInfo.td head/contrib/llvm-project/llvm/lib/Target/X86/X86MCInstLower.cpp head/contrib/llvm-project/llvm/lib/Target/X86/X86Subtarget.h head/contrib/llvm-project/llvm/lib/Target/X86/X86TargetMachine.cpp head/contrib/llvm-project/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp head/lib/clang/include/VCSVersion.inc head/lib/clang/include/llvm/Support/VCSRevision.h head/lib/clang/libllvm/Makefile Directory Properties: head/contrib/llvm-project/ (props changed) head/contrib/llvm-project/clang/ (props changed) head/contrib/llvm-project/llvm/ (props changed) Modified: head/contrib/llvm-project/clang/include/clang/Driver/Options.td ============================================================================== --- head/contrib/llvm-project/clang/include/clang/Driver/Options.td Thu Jun 25 06:39:18 2020 (r362608) +++ head/contrib/llvm-project/clang/include/clang/Driver/Options.td Thu Jun 25 08:15:10 2020 (r362609) @@ -2267,6 +2267,14 @@ def mspeculative_load_hardening : Flag<["-"], "mspecul Group, Flags<[CoreOption,CC1Option]>; def mno_speculative_load_hardening : Flag<["-"], "mno-speculative-load-hardening">, Group, Flags<[CoreOption]>; +def mlvi_hardening : Flag<["-"], "mlvi-hardening">, Group, Flags<[CoreOption,DriverOption]>, + HelpText<"Enable all mitigations for Load Value Injection (LVI)">; +def mno_lvi_hardening : Flag<["-"], "mno-lvi-hardening">, Group, Flags<[CoreOption,DriverOption]>, + HelpText<"Disable mitigations for Load Value Injection (LVI)">; +def mlvi_cfi : Flag<["-"], "mlvi-cfi">, Group, Flags<[CoreOption,DriverOption]>, + HelpText<"Enable only control-flow mitigations for Load Value Injection (LVI)">; +def mno_lvi_cfi : Flag<["-"], "mno-lvi-cfi">, Group, Flags<[CoreOption,DriverOption]>, + HelpText<"Disable control-flow mitigations for Load Value Injection (LVI)">; def mrelax : Flag<["-"], "mrelax">, Group, HelpText<"Enable linker relaxation">; Modified: head/contrib/llvm-project/clang/lib/Basic/Targets/PPC.h ============================================================================== --- head/contrib/llvm-project/clang/lib/Basic/Targets/PPC.h Thu Jun 25 06:39:18 2020 (r362608) +++ head/contrib/llvm-project/clang/lib/Basic/Targets/PPC.h Thu Jun 25 08:15:10 2020 (r362609) @@ -276,11 +276,12 @@ class LLVM_LIBRARY_VISIBILITY PPCTargetInfo : public T break; case 'Q': // Memory operand that is an offset from a register (it is // usually better to use `m' or `es' in asm statements) + Info.setAllowsRegister(); + LLVM_FALLTHROUGH; case 'Z': // Memory operand that is an indexed or indirect from a // register (it is usually better to use `m' or `es' in // asm statements) Info.setAllowsMemory(); - Info.setAllowsRegister(); break; case 'R': // AIX TOC entry case 'a': // Address operand that is an indexed or indirect from a Modified: head/contrib/llvm-project/clang/lib/Driver/SanitizerArgs.cpp ============================================================================== --- head/contrib/llvm-project/clang/lib/Driver/SanitizerArgs.cpp Thu Jun 25 06:39:18 2020 (r362608) +++ head/contrib/llvm-project/clang/lib/Driver/SanitizerArgs.cpp Thu Jun 25 08:15:10 2020 (r362609) @@ -454,8 +454,7 @@ SanitizerArgs::SanitizerArgs(const ToolChain &TC, << lastArgumentForMask(D, Args, Kinds & NeedsLTO) << "-flto"; } - if ((Kinds & SanitizerKind::ShadowCallStack) && - TC.getTriple().getArch() == llvm::Triple::aarch64 && + if ((Kinds & SanitizerKind::ShadowCallStack) && TC.getTriple().isAArch64() && !llvm::AArch64::isX18ReservedByDefault(TC.getTriple()) && !Args.hasArg(options::OPT_ffixed_x18)) { D.Diag(diag::err_drv_argument_only_allowed_with) Modified: head/contrib/llvm-project/clang/lib/Driver/ToolChain.cpp ============================================================================== --- head/contrib/llvm-project/clang/lib/Driver/ToolChain.cpp Thu Jun 25 06:39:18 2020 (r362608) +++ head/contrib/llvm-project/clang/lib/Driver/ToolChain.cpp Thu Jun 25 08:15:10 2020 (r362609) @@ -954,15 +954,12 @@ SanitizerMask ToolChain::getSupportedSanitizers() cons if (getTriple().getArch() == llvm::Triple::x86 || getTriple().getArch() == llvm::Triple::x86_64 || getTriple().getArch() == llvm::Triple::arm || - getTriple().getArch() == llvm::Triple::aarch64 || getTriple().getArch() == llvm::Triple::wasm32 || - getTriple().getArch() == llvm::Triple::wasm64) + getTriple().getArch() == llvm::Triple::wasm64 || getTriple().isAArch64()) Res |= SanitizerKind::CFIICall; - if (getTriple().getArch() == llvm::Triple::x86_64 || - getTriple().getArch() == llvm::Triple::aarch64) + if (getTriple().getArch() == llvm::Triple::x86_64 || getTriple().isAArch64()) Res |= SanitizerKind::ShadowCallStack; - if (getTriple().getArch() == llvm::Triple::aarch64 || - getTriple().getArch() == llvm::Triple::aarch64_be) + if (getTriple().isAArch64()) Res |= SanitizerKind::MemTag; return Res; } Modified: head/contrib/llvm-project/clang/lib/Driver/ToolChains/Arch/X86.cpp ============================================================================== --- head/contrib/llvm-project/clang/lib/Driver/ToolChains/Arch/X86.cpp Thu Jun 25 06:39:18 2020 (r362608) +++ head/contrib/llvm-project/clang/lib/Driver/ToolChains/Arch/X86.cpp Thu Jun 25 08:15:10 2020 (r362609) @@ -147,6 +147,7 @@ void x86::getX86TargetFeatures(const Driver &D, const // flags). This is a bit hacky but keeps existing usages working. We should // consider deprecating this and instead warn if the user requests external // retpoline thunks and *doesn't* request some form of retpolines. + auto SpectreOpt = clang::driver::options::ID::OPT_INVALID; if (Args.hasArgNoClaim(options::OPT_mretpoline, options::OPT_mno_retpoline, options::OPT_mspeculative_load_hardening, options::OPT_mno_speculative_load_hardening)) { @@ -154,12 +155,14 @@ void x86::getX86TargetFeatures(const Driver &D, const false)) { Features.push_back("+retpoline-indirect-calls"); Features.push_back("+retpoline-indirect-branches"); + SpectreOpt = options::OPT_mretpoline; } else if (Args.hasFlag(options::OPT_mspeculative_load_hardening, options::OPT_mno_speculative_load_hardening, false)) { // On x86, speculative load hardening relies on at least using retpolines // for indirect calls. Features.push_back("+retpoline-indirect-calls"); + SpectreOpt = options::OPT_mspeculative_load_hardening; } } else if (Args.hasFlag(options::OPT_mretpoline_external_thunk, options::OPT_mno_retpoline_external_thunk, false)) { @@ -167,6 +170,26 @@ void x86::getX86TargetFeatures(const Driver &D, const // eventually switch to an error here. Features.push_back("+retpoline-indirect-calls"); Features.push_back("+retpoline-indirect-branches"); + SpectreOpt = options::OPT_mretpoline_external_thunk; + } + + auto LVIOpt = clang::driver::options::ID::OPT_INVALID; + if (Args.hasFlag(options::OPT_mlvi_hardening, options::OPT_mno_lvi_hardening, + false)) { + Features.push_back("+lvi-load-hardening"); + Features.push_back("+lvi-cfi"); // load hardening implies CFI protection + LVIOpt = options::OPT_mlvi_hardening; + } else if (Args.hasFlag(options::OPT_mlvi_cfi, options::OPT_mno_lvi_cfi, + false)) { + Features.push_back("+lvi-cfi"); + LVIOpt = options::OPT_mlvi_cfi; + } + + if (SpectreOpt != clang::driver::options::ID::OPT_INVALID && + LVIOpt != clang::driver::options::ID::OPT_INVALID) { + D.Diag(diag::err_drv_argument_not_allowed_with) + << D.getOpts().getOptionName(SpectreOpt) + << D.getOpts().getOptionName(LVIOpt); } // Now add any that the user explicitly requested on the command line, Copied: head/contrib/llvm-project/llvm/include/llvm/CodeGen/RDFGraph.h (from r362594, vendor/llvm-project/release-10.x/llvm/include/llvm/CodeGen/RDFGraph.h) ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/contrib/llvm-project/llvm/include/llvm/CodeGen/RDFGraph.h Thu Jun 25 08:15:10 2020 (r362609, copy of r362594, vendor/llvm-project/release-10.x/llvm/include/llvm/CodeGen/RDFGraph.h) @@ -0,0 +1,968 @@ +//===- 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(,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, 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(,,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/SmallVector.h" +#include "llvm/MC/LaneBitmask.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/MathExtras.h" +#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 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 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 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 = 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(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; + using AllocatorTy = BumpPtrAllocatorImpl; + AllocatorTy MemPool; + }; + + using RegisterSet = std::set; + + 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"); + + using NodeList = SmallVector, 4>; + using NodeSet = std::set; + + 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: + using value_type = NodeAddr; + 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 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; + + 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; + + void build(unsigned Options = BuildOptions::None); + void pushAllDefs(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 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; + + NodeAddr findBlock(MachineBasicBlock *BB) const { + return BlockNodes.at(BB); + } + + 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; + + using BlockRefsMap = std::map; + + void buildStmt(NodeAddr BA, MachineInstr &In); + void recordDefsForDF(BlockRefsMap &PhiM, NodeAddr BA); + void buildPhis(BlockRefsMap &PhiM, RegisterSet &AllRefs, + NodeAddr BA); + void removeUnusedPhis(); + + void pushClobbers(NodeAddr IA, DefStackMap &DM); + void pushDefs(NodeAddr IA, DefStackMap &DM); + template void linkRefUp(NodeAddr IA, + NodeAddr TA, DefStack &DS); + template void linkStmtRefs(DefStackMap &DefM, + NodeAddr SA, Predicate P); + 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); + } + + 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; *** DIFF OUTPUT TRUNCATED AT 1000 LINES ***