CbC/CbC_llvm: lib/Target/Hexagon/RDFGraph.h annotate

annotate lib/Target/Hexagon/RDFGraph.h @ 147:c2174574ed3a

LLVM 10

author	Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date	Wed, 14 Aug 2019 16:55:33 +0900
parents	3a76565eade5
children

rev	line source
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	1 //===- RDFGraph.h ------------------------------------------------ C++ --===//
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	2 //
147 c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	4 // See https://llvm.org/LICENSE.txt for license information.
c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	6 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	7 //===----------------------------------------------------------------------===//
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	8 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	9 // Target-independent, SSA-based data flow graph for register data flow (RDF)
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	10 // for a non-SSA program representation (e.g. post-RA machine code).
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	11 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	12 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	13 // *** Introduction
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	14 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	15 // The RDF graph is a collection of nodes, each of which denotes some element
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	16 // of the program. There are two main types of such elements: code and refe-
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	17 // rences. Conceptually, "code" is something that represents the structure
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	18 // of the program, e.g. basic block or a statement, while "reference" is an
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	19 // instance of accessing a register, e.g. a definition or a use. Nodes are
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	20 // connected with each other based on the structure of the program (such as
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	21 // blocks, instructions, etc.), and based on the data flow (e.g. reaching
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	22 // definitions, reached uses, etc.). The single-reaching-definition principle
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	23 // of SSA is generally observed, although, due to the non-SSA representation
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	24 // of the program, there are some differences between the graph and a "pure"
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	25 // SSA representation.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	26 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	27 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	28 // *** Implementation remarks
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	29 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	30 // Since the graph can contain a large number of nodes, memory consumption
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	31 // was one of the major design considerations. As a result, there is a single
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	32 // base class NodeBase which defines all members used by all possible derived
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	33 // classes. The members are arranged in a union, and a derived class cannot
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	34 // add any data members of its own. Each derived class only defines the
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	35 // functional interface, i.e. member functions. NodeBase must be a POD,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	36 // which implies that all of its members must also be PODs.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	37 // Since nodes need to be connected with other nodes, pointers have been
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	38 // replaced with 32-bit identifiers: each node has an id of type NodeId.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	39 // There are mapping functions in the graph that translate between actual
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	40 // memory addresses and the corresponding identifiers.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	41 // A node id of 0 is equivalent to nullptr.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	42 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	43 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	44 // *** Structure of the graph
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	45 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	46 // A code node is always a collection of other nodes. For example, a code
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	47 // node corresponding to a basic block will contain code nodes corresponding
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	48 // to instructions. In turn, a code node corresponding to an instruction will
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	49 // contain a list of reference nodes that correspond to the definitions and
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	50 // uses of registers in that instruction. The members are arranged into a
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	51 // circular list, which is yet another consequence of the effort to save
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	52 // memory: for each member node it should be possible to obtain its owner,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	53 // and it should be possible to access all other members. There are other
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	54 // ways to accomplish that, but the circular list seemed the most natural.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	55 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	56 // +- CodeNode -+
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	57 // \| \| <---------------------------------------------------+
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	58 // +-+--------+-+ \|
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	59 // \|FirstM \|LastM \|
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	60 // \| +-------------------------------------+ \|
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	61 // \| \| \|
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	62 // V V \|
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	63 // +----------+ Next +----------+ Next Next +----------+ Next \|
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	64 // \| \|----->\| \|-----> ... ----->\| \|----->-+
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	65 // +- Member -+ +- Member -+ +- Member -+
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	66 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	67 // The order of members is such that related reference nodes (see below)
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	68 // should be contiguous on the member list.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	69 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	70 // A reference node is a node that encapsulates an access to a register,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	71 // in other words, data flowing into or out of a register. There are two
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	72 // major kinds of reference nodes: defs and uses. A def node will contain
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	73 // the id of the first reached use, and the id of the first reached def.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	74 // Each def and use will contain the id of the reaching def, and also the
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	75 // id of the next reached def (for def nodes) or use (for use nodes).
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	76 // The "next node sharing the same reaching def" is denoted as "sibling".
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	77 // In summary:
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	78 // - Def node contains: reaching def, sibling, first reached def, and first
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	79 // reached use.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	80 // - Use node contains: reaching def and sibling.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	81 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	82 // +-- DefNode --+
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	83 // \| R2 = ... \| <---+--------------------+
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	84 // ++---------+--+ \| \|
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	85 // \|Reached \|Reached \| \|
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	86 // \|Def \|Use \| \|
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	87 // \| \| \|Reaching \|Reaching
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	88 // \| V \|Def \|Def
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	89 // \| +-- UseNode --+ Sib +-- UseNode --+ Sib Sib
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	90 // \| \| ... = R2 \|----->\| ... = R2 \|----> ... ----> 0
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	91 // \| +-------------+ +-------------+
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	92 // V
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	93 // +-- DefNode --+ Sib
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	94 // \| R2 = ... \|----> ...
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	95 // ++---------+--+
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	96 // \| \|
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	97 // \| \|
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	98 // ... ...
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	99 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	100 // To get a full picture, the circular lists connecting blocks within a
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	101 // function, instructions within a block, etc. should be superimposed with
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	102 // the def-def, def-use links shown above.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	103 // To illustrate this, consider a small example in a pseudo-assembly:
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	104 // foo:
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	105 // add r2, r0, r1 ; r2 = r0+r1
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	106 // addi r0, r2, 1 ; r0 = r2+1
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	107 // ret r0 ; return value in r0
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	108 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	109 // The graph (in a format used by the debugging functions) would look like:
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	110 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	111 // DFG dump:[
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	112 // f1: Function foo
134 3a76565eade5 update 5.0.1 mir3636 parents: 121 diff changeset	113 // b2: === %bb.0 === preds(0), succs(0):
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	114 // p3: phi [d4<r0>(,d12,u9):]
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	115 // p5: phi [d6<r1>(,,u10):]
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	116 // s7: add [d8<r2>(,,u13):, u9<r0>(d4):, u10<r1>(d6):]
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	117 // s11: addi [d12<r0>(d4,,u15):, u13<r2>(d8):]
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	118 // s14: ret [u15<r0>(d12):]
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	119 // ]
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	120 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	121 // The f1, b2, p3, etc. are node ids. The letter is prepended to indicate the
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	122 // kind of the node (i.e. f - function, b - basic block, p - phi, s - state-
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	123 // ment, d - def, u - use).
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	124 // The format of a def node is:
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	125 // dN<R>(rd,d,u):sib,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	126 // where
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	127 // N - numeric node id,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	128 // R - register being defined
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	129 // rd - reaching def,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	130 // d - reached def,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	131 // u - reached use,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	132 // sib - sibling.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	133 // The format of a use node is:
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	134 // uN<R>[!](rd):sib,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	135 // where
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	136 // N - numeric node id,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	137 // R - register being used,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	138 // rd - reaching def,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	139 // sib - sibling.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	140 // Possible annotations (usually preceding the node id):
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	141 // + - preserving def,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	142 // ~ - clobbering def,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	143 // " - shadow ref (follows the node id),
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	144 // ! - fixed register (appears after register name).
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	145 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	146 // The circular lists are not explicit in the dump.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	147 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	148 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	149 // *** Node attributes
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	150 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	151 // NodeBase has a member "Attrs", which is the primary way of determining
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	152 // the node's characteristics. The fields in this member decide whether
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	153 // the node is a code node or a reference node (i.e. node's "type"), then
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	154 // within each type, the "kind" determines what specifically this node
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	155 // represents. The remaining bits, "flags", contain additional information
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	156 // that is even more detailed than the "kind".
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	157 // CodeNode's kinds are:
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	158 // - Phi: Phi node, members are reference nodes.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	159 // - Stmt: Statement, members are reference nodes.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	160 // - Block: Basic block, members are instruction nodes (i.e. Phi or Stmt).
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	161 // - Func: The whole function. The members are basic block nodes.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	162 // RefNode's kinds are:
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	163 // - Use.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	164 // - Def.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	165 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	166 // Meaning of flags:
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	167 // - Preserving: applies only to defs. A preserving def is one that can
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	168 // preserve some of the original bits among those that are included in
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	169 // the register associated with that def. For example, if R0 is a 32-bit
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	170 // register, but a def can only change the lower 16 bits, then it will
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	171 // be marked as preserving.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	172 // - Shadow: a reference that has duplicates holding additional reaching
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	173 // defs (see more below).
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	174 // - Clobbering: applied only to defs, indicates that the value generated
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	175 // by this def is unspecified. A typical example would be volatile registers
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	176 // after function calls.
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	177 // - Fixed: the register in this def/use cannot be replaced with any other
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	178 // register. A typical case would be a parameter register to a call, or
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	179 // the register with the return value from a function.
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	180 // - Undef: the register in this reference the register is assumed to have
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	181 // no pre-existing value, even if it appears to be reached by some def.
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	182 // This is typically used to prevent keeping registers artificially live
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	183 // in cases when they are defined via predicated instructions. For example:
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	184 // r0 = add-if-true cond, r10, r11 (1)
134 3a76565eade5 update 5.0.1 mir3636 parents: 121 diff changeset	185 // r0 = add-if-false cond, r12, r13, implicit r0 (2)
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	186 // ... = r0 (3)
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	187 // Before (1), r0 is not intended to be live, and the use of r0 in (3) is
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	188 // not meant to be reached by any def preceding (1). However, since the
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	189 // defs in (1) and (2) are both preserving, these properties alone would
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	190 // imply that the use in (3) may indeed be reached by some prior def.
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	191 // Adding Undef flag to the def in (1) prevents that. The Undef flag
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	192 // may be applied to both defs and uses.
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	193 // - Dead: applies only to defs. The value coming out of a "dead" def is
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	194 // assumed to be unused, even if the def appears to be reaching other defs
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	195 // or uses. The motivation for this flag comes from dead defs on function
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	196 // calls: there is no way to determine if such a def is dead without
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	197 // analyzing the target's ABI. Hence the graph should contain this info,
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	198 // as it is unavailable otherwise. On the other hand, a def without any
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	199 // uses on a typical instruction is not the intended target for this flag.
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	200 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	201 // *** Shadow references
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	202 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	203 // It may happen that a super-register can have two (or more) non-overlapping
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	204 // sub-registers. When both of these sub-registers are defined and followed
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	205 // by a use of the super-register, the use of the super-register will not
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	206 // have a unique reaching def: both defs of the sub-registers need to be
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	207 // accounted for. In such cases, a duplicate use of the super-register is
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	208 // added and it points to the extra reaching def. Both uses are marked with
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	209 // a flag "shadow". Example:
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	210 // Assume t0 is a super-register of r0 and r1, r0 and r1 do not overlap:
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	211 // set r0, 1 ; r0 = 1
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	212 // set r1, 1 ; r1 = 1
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	213 // addi t1, t0, 1 ; t1 = t0+1
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	214 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	215 // The DFG:
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	216 // s1: set [d2<r0>(,,u9):]
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	217 // s3: set [d4<r1>(,,u10):]
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	218 // s5: addi [d6<t1>(,,):, u7"<t0>(d2):, u8"<t0>(d4):]
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	219 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	220 // The statement s5 has two use nodes for t0: u7" and u9". The quotation
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	221 // mark " indicates that the node is a shadow.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	222 //
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	223
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	224 #ifndef LLVM_LIB_TARGET_HEXAGON_RDFGRAPH_H
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	225 #define LLVM_LIB_TARGET_HEXAGON_RDFGRAPH_H
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	226
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	227 #include "RDFRegisters.h"
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	228 #include "llvm/ADT/SmallVector.h"
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	229 #include "llvm/MC/LaneBitmask.h"
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	230 #include "llvm/Support/Allocator.h"
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	231 #include "llvm/Support/MathExtras.h"
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	232 #include <cassert>
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	233 #include <cstdint>
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	234 #include <cstring>
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	235 #include <map>
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	236 #include <set>
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	237 #include <unordered_map>
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	238 #include <utility>
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	239 #include <vector>
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	240
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	241 // RDF uses uint32_t to refer to registers. This is to ensure that the type
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	242 // size remains specific. In other places, registers are often stored using
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	243 // unsigned.
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	244 static_assert(sizeof(uint32_t) == sizeof(unsigned), "Those should be equal");
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	245
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	246 namespace llvm {
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	247
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	248 class MachineBasicBlock;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	249 class MachineDominanceFrontier;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	250 class MachineDominatorTree;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	251 class MachineFunction;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	252 class MachineInstr;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	253 class MachineOperand;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	254 class raw_ostream;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	255 class TargetInstrInfo;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	256 class TargetRegisterInfo;
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	257
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	258 namespace rdf {
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	259
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	260 using NodeId = uint32_t;
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	261
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	262 struct DataFlowGraph;
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	263
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	264 struct NodeAttrs {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	265 enum : uint16_t {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	266 None = 0x0000, // Nothing
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	267
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	268 // Types: 2 bits
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	269 TypeMask = 0x0003,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	270 Code = 0x0001, // 01, Container
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	271 Ref = 0x0002, // 10, Reference
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	272
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	273 // Kind: 3 bits
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	274 KindMask = 0x0007 << 2,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	275 Def = 0x0001 << 2, // 001
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	276 Use = 0x0002 << 2, // 010
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	277 Phi = 0x0003 << 2, // 011
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	278 Stmt = 0x0004 << 2, // 100
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	279 Block = 0x0005 << 2, // 101
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	280 Func = 0x0006 << 2, // 110
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	281
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	282 // Flags: 7 bits for now
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	283 FlagMask = 0x007F << 5,
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	284 Shadow = 0x0001 << 5, // 0000001, Has extra reaching defs.
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	285 Clobbering = 0x0002 << 5, // 0000010, Produces unspecified values.
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	286 PhiRef = 0x0004 << 5, // 0000100, Member of PhiNode.
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	287 Preserving = 0x0008 << 5, // 0001000, Def can keep original bits.
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	288 Fixed = 0x0010 << 5, // 0010000, Fixed register.
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	289 Undef = 0x0020 << 5, // 0100000, Has no pre-existing value.
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	290 Dead = 0x0040 << 5, // 1000000, Does not define a value.
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	291 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	292
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	293 static uint16_t type(uint16_t T) { return T & TypeMask; }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	294 static uint16_t kind(uint16_t T) { return T & KindMask; }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	295 static uint16_t flags(uint16_t T) { return T & FlagMask; }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	296
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	297 static uint16_t set_type(uint16_t A, uint16_t T) {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	298 return (A & ~TypeMask) \| T;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	299 }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	300
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	301 static uint16_t set_kind(uint16_t A, uint16_t K) {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	302 return (A & ~KindMask) \| K;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	303 }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	304
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	305 static uint16_t set_flags(uint16_t A, uint16_t F) {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	306 return (A & ~FlagMask) \| F;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	307 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	308
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	309 // Test if A contains B.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	310 static bool contains(uint16_t A, uint16_t B) {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	311 if (type(A) != Code)
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	312 return false;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	313 uint16_t KB = kind(B);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	314 switch (kind(A)) {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	315 case Func:
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	316 return KB == Block;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	317 case Block:
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	318 return KB == Phi \|\| KB == Stmt;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	319 case Phi:
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	320 case Stmt:
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	321 return type(B) == Ref;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	322 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	323 return false;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	324 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	325 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	326
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	327 struct BuildOptions {
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	328 enum : unsigned {
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	329 None = 0x00,
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	330 KeepDeadPhis = 0x01, // Do not remove dead phis during build.
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	331 };
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	332 };
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	333
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	334 template <typename T> struct NodeAddr {
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	335 NodeAddr() = default;
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	336 NodeAddr(T A, NodeId I) : Addr(A), Id(I) {}
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	337
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	338 // Type cast (casting constructor). The reason for having this class
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	339 // instead of std::pair.
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	340 template <typename S> NodeAddr(const NodeAddr<S> &NA)
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	341 : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	342
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	343 bool operator== (const NodeAddr<T> &NA) const {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	344 assert((Addr == NA.Addr) == (Id == NA.Id));
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	345 return Addr == NA.Addr;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	346 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	347 bool operator!= (const NodeAddr<T> &NA) const {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	348 return !operator==(NA);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	349 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	350
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	351 T Addr = nullptr;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	352 NodeId Id = 0;
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	353 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	354
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	355 struct NodeBase;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	356
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	357 // Fast memory allocation and translation between node id and node address.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	358 // This is really the same idea as the one underlying the "bump pointer
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	359 // allocator", the difference being in the translation. A node id is
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	360 // composed of two components: the index of the block in which it was
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	361 // allocated, and the index within the block. With the default settings,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	362 // where the number of nodes per block is 4096, the node id (minus 1) is:
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	363 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	364 // bit position: 11 0
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	365 // +----------------------------+--------------+
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	366 // \| Index of the block \|Index in block\|
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	367 // +----------------------------+--------------+
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	368 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	369 // The actual node id is the above plus 1, to avoid creating a node id of 0.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	370 //
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	371 // This method significantly improved the build time, compared to using maps
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	372 // (std::unordered_map or DenseMap) to translate between pointers and ids.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	373 struct NodeAllocator {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	374 // Amount of storage for a single node.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	375 enum { NodeMemSize = 32 };
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	376
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	377 NodeAllocator(uint32_t NPB = 4096)
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	378 : NodesPerBlock(NPB), BitsPerIndex(Log2_32(NPB)),
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	379 IndexMask((1 << BitsPerIndex)-1) {
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	380 assert(isPowerOf2_32(NPB));
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	381 }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	382
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	383 NodeBase *ptr(NodeId N) const {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	384 uint32_t N1 = N-1;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	385 uint32_t BlockN = N1 >> BitsPerIndex;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	386 uint32_t Offset = (N1 & IndexMask) * NodeMemSize;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	387 return reinterpret_cast<NodeBase*>(Blocks[BlockN]+Offset);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	388 }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	389
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	390 NodeId id(const NodeBase *P) const;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	391 NodeAddr<NodeBase*> New();
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	392 void clear();
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	393
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	394 private:
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	395 void startNewBlock();
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	396 bool needNewBlock();
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	397
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	398 uint32_t makeId(uint32_t Block, uint32_t Index) const {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	399 // Add 1 to the id, to avoid the id of 0, which is treated as "null".
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	400 return ((Block << BitsPerIndex) \| Index) + 1;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	401 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	402
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	403 const uint32_t NodesPerBlock;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	404 const uint32_t BitsPerIndex;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	405 const uint32_t IndexMask;
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	406 char *ActiveEnd = nullptr;
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	407 std::vector<char*> Blocks;
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	408 using AllocatorTy = BumpPtrAllocatorImpl<MallocAllocator, 65536>;
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	409 AllocatorTy MemPool;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	410 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	411
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	412 using RegisterSet = std::set<RegisterRef>;
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	413
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	414 struct TargetOperandInfo {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	415 TargetOperandInfo(const TargetInstrInfo &tii) : TII(tii) {}
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	416 virtual ~TargetOperandInfo() = default;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	417
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	418 virtual bool isPreserving(const MachineInstr &In, unsigned OpNum) const;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	419 virtual bool isClobbering(const MachineInstr &In, unsigned OpNum) const;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	420 virtual bool isFixedReg(const MachineInstr &In, unsigned OpNum) const;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	421
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	422 const TargetInstrInfo &TII;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	423 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	424
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	425 // Packed register reference. Only used for storage.
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	426 struct PackedRegisterRef {
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	427 RegisterId Reg;
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	428 uint32_t MaskId;
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	429 };
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	430
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	431 struct LaneMaskIndex : private IndexedSet<LaneBitmask> {
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	432 LaneMaskIndex() = default;
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	433
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	434 LaneBitmask getLaneMaskForIndex(uint32_t K) const {
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	435 return K == 0 ? LaneBitmask::getAll() : get(K);
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	436 }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	437
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	438 uint32_t getIndexForLaneMask(LaneBitmask LM) {
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	439 assert(LM.any());
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	440 return LM.all() ? 0 : insert(LM);
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	441 }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	442
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	443 uint32_t getIndexForLaneMask(LaneBitmask LM) const {
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	444 assert(LM.any());
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	445 return LM.all() ? 0 : find(LM);
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	446 }
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	447 };
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	448
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	449 struct NodeBase {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	450 public:
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	451 // Make sure this is a POD.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	452 NodeBase() = default;
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	453
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	454 uint16_t getType() const { return NodeAttrs::type(Attrs); }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	455 uint16_t getKind() const { return NodeAttrs::kind(Attrs); }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	456 uint16_t getFlags() const { return NodeAttrs::flags(Attrs); }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	457 NodeId getNext() const { return Next; }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	458
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	459 uint16_t getAttrs() const { return Attrs; }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	460 void setAttrs(uint16_t A) { Attrs = A; }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	461 void setFlags(uint16_t F) { setAttrs(NodeAttrs::set_flags(getAttrs(), F)); }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	462
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	463 // Insert node NA after "this" in the circular chain.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	464 void append(NodeAddr<NodeBase*> NA);
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	465
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	466 // Initialize all members to 0.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	467 void init() { memset(this, 0, sizeof *this); }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	468
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	469 void setNext(NodeId N) { Next = N; }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	470
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	471 protected:
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	472 uint16_t Attrs;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	473 uint16_t Reserved;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	474 NodeId Next; // Id of the next node in the circular chain.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	475 // Definitions of nested types. Using anonymous nested structs would make
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	476 // this class definition clearer, but unnamed structs are not a part of
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	477 // the standard.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	478 struct Def_struct {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	479 NodeId DD, DU; // Ids of the first reached def and use.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	480 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	481 struct PhiU_struct {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	482 NodeId PredB; // Id of the predecessor block for a phi use.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	483 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	484 struct Code_struct {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	485 void *CP; // Pointer to the actual code.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	486 NodeId FirstM, LastM; // Id of the first member and last.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	487 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	488 struct Ref_struct {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	489 NodeId RD, Sib; // Ids of the reaching def and the sibling.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	490 union {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	491 Def_struct Def;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	492 PhiU_struct PhiU;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	493 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	494 union {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	495 MachineOperand *Op; // Non-phi refs point to a machine operand.
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	496 PackedRegisterRef PR; // Phi refs store register info directly.
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	497 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	498 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	499
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	500 // The actual payload.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	501 union {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	502 Ref_struct Ref;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	503 Code_struct Code;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	504 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	505 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	506 // The allocator allocates chunks of 32 bytes for each node. The fact that
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	507 // each node takes 32 bytes in memory is used for fast translation between
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	508 // the node id and the node address.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	509 static_assert(sizeof(NodeBase) <= NodeAllocator::NodeMemSize,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	510 "NodeBase must be at most NodeAllocator::NodeMemSize bytes");
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	511
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	512 using NodeList = SmallVector<NodeAddr<NodeBase *>, 4>;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	513 using NodeSet = std::set<NodeId>;
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	514
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	515 struct RefNode : public NodeBase {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	516 RefNode() = default;
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	517
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	518 RegisterRef getRegRef(const DataFlowGraph &G) const;
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	519
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	520 MachineOperand &getOp() {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	521 assert(!(getFlags() & NodeAttrs::PhiRef));
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	522 return *Ref.Op;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	523 }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	524
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	525 void setRegRef(RegisterRef RR, DataFlowGraph &G);
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	526 void setRegRef(MachineOperand *Op, DataFlowGraph &G);
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	527
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	528 NodeId getReachingDef() const {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	529 return Ref.RD;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	530 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	531 void setReachingDef(NodeId RD) {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	532 Ref.RD = RD;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	533 }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	534
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	535 NodeId getSibling() const {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	536 return Ref.Sib;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	537 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	538 void setSibling(NodeId Sib) {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	539 Ref.Sib = Sib;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	540 }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	541
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	542 bool isUse() const {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	543 assert(getType() == NodeAttrs::Ref);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	544 return getKind() == NodeAttrs::Use;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	545 }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	546
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	547 bool isDef() const {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	548 assert(getType() == NodeAttrs::Ref);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	549 return getKind() == NodeAttrs::Def;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	550 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	551
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	552 template <typename Predicate>
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	553 NodeAddr<RefNode*> getNextRef(RegisterRef RR, Predicate P, bool NextOnly,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	554 const DataFlowGraph &G);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	555 NodeAddr<NodeBase*> getOwner(const DataFlowGraph &G);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	556 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	557
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	558 struct DefNode : public RefNode {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	559 NodeId getReachedDef() const {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	560 return Ref.Def.DD;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	561 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	562 void setReachedDef(NodeId D) {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	563 Ref.Def.DD = D;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	564 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	565 NodeId getReachedUse() const {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	566 return Ref.Def.DU;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	567 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	568 void setReachedUse(NodeId U) {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	569 Ref.Def.DU = U;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	570 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	571
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	572 void linkToDef(NodeId Self, NodeAddr<DefNode*> DA);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	573 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	574
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	575 struct UseNode : public RefNode {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	576 void linkToDef(NodeId Self, NodeAddr<DefNode*> DA);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	577 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	578
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	579 struct PhiUseNode : public UseNode {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	580 NodeId getPredecessor() const {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	581 assert(getFlags() & NodeAttrs::PhiRef);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	582 return Ref.PhiU.PredB;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	583 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	584 void setPredecessor(NodeId B) {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	585 assert(getFlags() & NodeAttrs::PhiRef);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	586 Ref.PhiU.PredB = B;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	587 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	588 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	589
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	590 struct CodeNode : public NodeBase {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	591 template <typename T> T getCode() const {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	592 return static_cast<T>(Code.CP);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	593 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	594 void setCode(void *C) {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	595 Code.CP = C;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	596 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	597
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	598 NodeAddr<NodeBase*> getFirstMember(const DataFlowGraph &G) const;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	599 NodeAddr<NodeBase*> getLastMember(const DataFlowGraph &G) const;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	600 void addMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	601 void addMemberAfter(NodeAddr<NodeBase> MA, NodeAddr<NodeBase> NA,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	602 const DataFlowGraph &G);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	603 void removeMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	604
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	605 NodeList members(const DataFlowGraph &G) const;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	606 template <typename Predicate>
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	607 NodeList members_if(Predicate P, const DataFlowGraph &G) const;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	608 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	609
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	610 struct InstrNode : public CodeNode {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	611 NodeAddr<NodeBase*> getOwner(const DataFlowGraph &G);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	612 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	613
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	614 struct PhiNode : public InstrNode {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	615 MachineInstr *getCode() const {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	616 return nullptr;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	617 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	618 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	619
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	620 struct StmtNode : public InstrNode {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	621 MachineInstr *getCode() const {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	622 return CodeNode::getCode<MachineInstr*>();
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	623 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	624 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	625
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	626 struct BlockNode : public CodeNode {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	627 MachineBasicBlock *getCode() const {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	628 return CodeNode::getCode<MachineBasicBlock*>();
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	629 }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	630
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	631 void addPhi(NodeAddr<PhiNode*> PA, const DataFlowGraph &G);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	632 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	633
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	634 struct FuncNode : public CodeNode {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	635 MachineFunction *getCode() const {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	636 return CodeNode::getCode<MachineFunction*>();
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	637 }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	638
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	639 NodeAddr<BlockNode> findBlock(const MachineBasicBlock BB,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	640 const DataFlowGraph &G) const;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	641 NodeAddr<BlockNode*> getEntryBlock(const DataFlowGraph &G);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	642 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	643
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	644 struct DataFlowGraph {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	645 DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	646 const TargetRegisterInfo &tri, const MachineDominatorTree &mdt,
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	647 const MachineDominanceFrontier &mdf, const TargetOperandInfo &toi);
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	648
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	649 NodeBase *ptr(NodeId N) const;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	650 template <typename T> T ptr(NodeId N) const {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	651 return static_cast<T>(ptr(N));
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	652 }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	653
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	654 NodeId id(const NodeBase *P) const;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	655
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	656 template <typename T> NodeAddr<T> addr(NodeId N) const {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	657 return { ptr<T>(N), N };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	658 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	659
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	660 NodeAddr<FuncNode*> getFunc() const { return Func; }
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	661 MachineFunction &getMF() const { return MF; }
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	662 const TargetInstrInfo &getTII() const { return TII; }
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	663 const TargetRegisterInfo &getTRI() const { return TRI; }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	664 const PhysicalRegisterInfo &getPRI() const { return PRI; }
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	665 const MachineDominatorTree &getDT() const { return MDT; }
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	666 const MachineDominanceFrontier &getDF() const { return MDF; }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	667 const RegisterAggr &getLiveIns() const { return LiveIns; }
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	668
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	669 struct DefStack {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	670 DefStack() = default;
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	671
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	672 bool empty() const { return Stack.empty() \|\| top() == bottom(); }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	673
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	674 private:
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	675 using value_type = NodeAddr<DefNode *>;
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	676 struct Iterator {
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	677 using value_type = DefStack::value_type;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	678
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	679 Iterator &up() { Pos = DS.nextUp(Pos); return *this; }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	680 Iterator &down() { Pos = DS.nextDown(Pos); return *this; }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	681
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	682 value_type operator*() const {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	683 assert(Pos >= 1);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	684 return DS.Stack[Pos-1];
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	685 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	686 const value_type *operator->() const {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	687 assert(Pos >= 1);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	688 return &DS.Stack[Pos-1];
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	689 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	690 bool operator==(const Iterator &It) const { return Pos == It.Pos; }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	691 bool operator!=(const Iterator &It) const { return Pos != It.Pos; }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	692
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	693 private:
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	694 friend struct DefStack;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	695
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	696 Iterator(const DefStack &S, bool Top);
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	697
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	698 // Pos-1 is the index in the StorageType object that corresponds to
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	699 // the top of the DefStack.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	700 const DefStack &DS;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	701 unsigned Pos;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	702 };
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	703
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	704 public:
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	705 using iterator = Iterator;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	706
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	707 iterator top() const { return Iterator(*this, true); }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	708 iterator bottom() const { return Iterator(*this, false); }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	709 unsigned size() const;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	710
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	711 void push(NodeAddr<DefNode*> DA) { Stack.push_back(DA); }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	712 void pop();
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	713 void start_block(NodeId N);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	714 void clear_block(NodeId N);
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	715
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	716 private:
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	717 friend struct Iterator;
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	718
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	719 using StorageType = std::vector<value_type>;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	720
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	721 bool isDelimiter(const StorageType::value_type &P, NodeId N = 0) const {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	722 return (P.Addr == nullptr) && (N == 0 \|\| P.Id == N);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	723 }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	724
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	725 unsigned nextUp(unsigned P) const;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	726 unsigned nextDown(unsigned P) const;
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	727
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	728 StorageType Stack;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	729 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	730
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	731 // Make this std::unordered_map for speed of accessing elements.
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	732 // Map: Register (physical or virtual) -> DefStack
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	733 using DefStackMap = std::unordered_map<RegisterId, DefStack>;
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	734
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	735 void build(unsigned Options = BuildOptions::None);
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	736 void pushAllDefs(NodeAddr<InstrNode*> IA, DefStackMap &DM);
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	737 void markBlock(NodeId B, DefStackMap &DefM);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	738 void releaseBlock(NodeId B, DefStackMap &DefM);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	739
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	740 PackedRegisterRef pack(RegisterRef RR) {
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	741 return { RR.Reg, LMI.getIndexForLaneMask(RR.Mask) };
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	742 }
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	743 PackedRegisterRef pack(RegisterRef RR) const {
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	744 return { RR.Reg, LMI.getIndexForLaneMask(RR.Mask) };
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	745 }
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	746 RegisterRef unpack(PackedRegisterRef PR) const {
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	747 return RegisterRef(PR.Reg, LMI.getLaneMaskForIndex(PR.MaskId));
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	748 }
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	749
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	750 RegisterRef makeRegRef(unsigned Reg, unsigned Sub) const;
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	751 RegisterRef makeRegRef(const MachineOperand &Op) const;
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	752 RegisterRef restrictRef(RegisterRef AR, RegisterRef BR) const;
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	753
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	754 NodeAddr<RefNode> getNextRelated(NodeAddr<InstrNode> IA,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	755 NodeAddr<RefNode*> RA) const;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	756 NodeAddr<RefNode> getNextImp(NodeAddr<InstrNode> IA,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	757 NodeAddr<RefNode*> RA, bool Create);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	758 NodeAddr<RefNode> getNextImp(NodeAddr<InstrNode> IA,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	759 NodeAddr<RefNode*> RA) const;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	760 NodeAddr<RefNode> getNextShadow(NodeAddr<InstrNode> IA,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	761 NodeAddr<RefNode*> RA, bool Create);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	762 NodeAddr<RefNode> getNextShadow(NodeAddr<InstrNode> IA,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	763 NodeAddr<RefNode*> RA) const;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	764
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	765 NodeList getRelatedRefs(NodeAddr<InstrNode*> IA,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	766 NodeAddr<RefNode*> RA) const;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	767
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	768 NodeAddr<BlockNode> findBlock(MachineBasicBlock BB) const {
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	769 return BlockNodes.at(BB);
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	770 }
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	771
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	772 void unlinkUse(NodeAddr<UseNode*> UA, bool RemoveFromOwner) {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	773 unlinkUseDF(UA);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	774 if (RemoveFromOwner)
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	775 removeFromOwner(UA);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	776 }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	777
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	778 void unlinkDef(NodeAddr<DefNode*> DA, bool RemoveFromOwner) {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	779 unlinkDefDF(DA);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	780 if (RemoveFromOwner)
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	781 removeFromOwner(DA);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	782 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	783
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	784 // Some useful filters.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	785 template <uint16_t Kind>
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	786 static bool IsRef(const NodeAddr<NodeBase*> BA) {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	787 return BA.Addr->getType() == NodeAttrs::Ref &&
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	788 BA.Addr->getKind() == Kind;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	789 }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	790
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	791 template <uint16_t Kind>
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	792 static bool IsCode(const NodeAddr<NodeBase*> BA) {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	793 return BA.Addr->getType() == NodeAttrs::Code &&
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	794 BA.Addr->getKind() == Kind;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	795 }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	796
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	797 static bool IsDef(const NodeAddr<NodeBase*> BA) {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	798 return BA.Addr->getType() == NodeAttrs::Ref &&
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	799 BA.Addr->getKind() == NodeAttrs::Def;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	800 }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	801
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	802 static bool IsUse(const NodeAddr<NodeBase*> BA) {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	803 return BA.Addr->getType() == NodeAttrs::Ref &&
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	804 BA.Addr->getKind() == NodeAttrs::Use;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	805 }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	806
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	807 static bool IsPhi(const NodeAddr<NodeBase*> BA) {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	808 return BA.Addr->getType() == NodeAttrs::Code &&
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	809 BA.Addr->getKind() == NodeAttrs::Phi;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	810 }
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	811
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	812 static bool IsPreservingDef(const NodeAddr<DefNode*> DA) {
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	813 uint16_t Flags = DA.Addr->getFlags();
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	814 return (Flags & NodeAttrs::Preserving) && !(Flags & NodeAttrs::Undef);
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	815 }
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	816
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	817 private:
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	818 void reset();
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	819
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	820 RegisterSet getLandingPadLiveIns() const;
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	821
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	822 NodeAddr<NodeBase*> newNode(uint16_t Attrs);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	823 NodeAddr<NodeBase> cloneNode(const NodeAddr<NodeBase> B);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	824 NodeAddr<UseNode> newUse(NodeAddr<InstrNode> Owner,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	825 MachineOperand &Op, uint16_t Flags = NodeAttrs::None);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	826 NodeAddr<PhiUseNode> newPhiUse(NodeAddr<PhiNode> Owner,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	827 RegisterRef RR, NodeAddr<BlockNode*> PredB,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	828 uint16_t Flags = NodeAttrs::PhiRef);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	829 NodeAddr<DefNode> newDef(NodeAddr<InstrNode> Owner,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	830 MachineOperand &Op, uint16_t Flags = NodeAttrs::None);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	831 NodeAddr<DefNode> newDef(NodeAddr<InstrNode> Owner,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	832 RegisterRef RR, uint16_t Flags = NodeAttrs::PhiRef);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	833 NodeAddr<PhiNode> newPhi(NodeAddr<BlockNode> Owner);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	834 NodeAddr<StmtNode> newStmt(NodeAddr<BlockNode> Owner,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	835 MachineInstr *MI);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	836 NodeAddr<BlockNode> newBlock(NodeAddr<FuncNode> Owner,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	837 MachineBasicBlock *BB);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	838 NodeAddr<FuncNode> newFunc(MachineFunction MF);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	839
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	840 template <typename Predicate>
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	841 std::pair<NodeAddr<RefNode>,NodeAddr<RefNode>>
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	842 locateNextRef(NodeAddr<InstrNode> IA, NodeAddr<RefNode> RA,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	843 Predicate P) const;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	844
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	845 using BlockRefsMap = std::map<NodeId, RegisterSet>;
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	846
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	847 void buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In);
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	848 void recordDefsForDF(BlockRefsMap &PhiM, NodeAddr<BlockNode*> BA);
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	849 void buildPhis(BlockRefsMap &PhiM, RegisterSet &AllRefs,
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	850 NodeAddr<BlockNode*> BA);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	851 void removeUnusedPhis();
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	852
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	853 void pushClobbers(NodeAddr<InstrNode*> IA, DefStackMap &DM);
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	854 void pushDefs(NodeAddr<InstrNode*> IA, DefStackMap &DM);
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	855 template <typename T> void linkRefUp(NodeAddr<InstrNode*> IA,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	856 NodeAddr<T> TA, DefStack &DS);
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	857 template <typename Predicate> void linkStmtRefs(DefStackMap &DefM,
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	858 NodeAddr<StmtNode*> SA, Predicate P);
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	859 void linkBlockRefs(DefStackMap &DefM, NodeAddr<BlockNode*> BA);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	860
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	861 void unlinkUseDF(NodeAddr<UseNode*> UA);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	862 void unlinkDefDF(NodeAddr<DefNode*> DA);
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	863
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	864 void removeFromOwner(NodeAddr<RefNode*> RA) {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	865 NodeAddr<InstrNode> IA = RA.Addr->getOwner(this);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	866 IA.Addr->removeMember(RA, *this);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	867 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	868
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	869 MachineFunction &MF;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	870 const TargetInstrInfo &TII;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	871 const TargetRegisterInfo &TRI;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	872 const PhysicalRegisterInfo PRI;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	873 const MachineDominatorTree &MDT;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	874 const MachineDominanceFrontier &MDF;
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	875 const TargetOperandInfo &TOI;
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	876
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	877 RegisterAggr LiveIns;
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	878 NodeAddr<FuncNode*> Func;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	879 NodeAllocator Memory;
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	880 // Local map: MachineBasicBlock -> NodeAddr<BlockNode*>
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	881 std::map<MachineBasicBlock,NodeAddr<BlockNode>> BlockNodes;
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	882 // Lane mask map.
1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	883 LaneMaskIndex LMI;
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	884 }; // struct DataFlowGraph
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	885
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	886 template <typename Predicate>
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	887 NodeAddr<RefNode*> RefNode::getNextRef(RegisterRef RR, Predicate P,
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	888 bool NextOnly, const DataFlowGraph &G) {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	889 // Get the "Next" reference in the circular list that references RR and
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	890 // satisfies predicate "Pred".
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	891 auto NA = G.addr<NodeBase*>(getNext());
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	892
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	893 while (NA.Addr != this) {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	894 if (NA.Addr->getType() == NodeAttrs::Ref) {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	895 NodeAddr<RefNode*> RA = NA;
120 1172e4bd9c6f update 4.0.0 mir3636 parents: 100 diff changeset	896 if (RA.Addr->getRegRef(G) == RR && P(NA))
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	897 return NA;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	898 if (NextOnly)
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	899 break;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	900 NA = G.addr<NodeBase*>(NA.Addr->getNext());
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	901 } else {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	902 // We've hit the beginning of the chain.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	903 assert(NA.Addr->getType() == NodeAttrs::Code);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	904 NodeAddr<CodeNode*> CA = NA;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	905 NA = CA.Addr->getFirstMember(G);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	906 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	907 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	908 // Return the equivalent of "nullptr" if such a node was not found.
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	909 return NodeAddr<RefNode*>();
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	910 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	911
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	912 template <typename Predicate>
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	913 NodeList CodeNode::members_if(Predicate P, const DataFlowGraph &G) const {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	914 NodeList MM;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	915 auto M = getFirstMember(G);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	916 if (M.Id == 0)
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	917 return MM;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	918
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	919 while (M.Addr != this) {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	920 if (P(M))
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	921 MM.push_back(M);
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	922 M = G.addr<NodeBase*>(M.Addr->getNext());
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	923 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	924 return MM;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	925 }
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	926
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	927 template <typename T>
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	928 struct Print {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	929 Print(const T &x, const DataFlowGraph &g) : Obj(x), G(g) {}
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	930
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	931 const T &Obj;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	932 const DataFlowGraph &G;
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	933 };
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	934
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	935 template <typename T>
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	936 struct PrintNode : Print<NodeAddr<T>> {
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	937 PrintNode(const NodeAddr<T> &x, const DataFlowGraph &g)
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	938 : Print<NodeAddr<T>>(x, g) {}
7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	939 };
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	940
147 c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	941 raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterRef> &P);
c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	942 raw_ostream &operator<<(raw_ostream &OS, const Print<NodeId> &P);
c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	943 raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<DefNode *>> &P);
c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	944 raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<UseNode *>> &P);
c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	945 raw_ostream &operator<<(raw_ostream &OS,
c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	946 const Print<NodeAddr<PhiUseNode *>> &P);
c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	947 raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<RefNode *>> &P);
c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	948 raw_ostream &operator<<(raw_ostream &OS, const Print<NodeList> &P);
c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	949 raw_ostream &operator<<(raw_ostream &OS, const Print<NodeSet> &P);
c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	950 raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<PhiNode *>> &P);
c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	951 raw_ostream &operator<<(raw_ostream &OS,
c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	952 const Print<NodeAddr<StmtNode *>> &P);
c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	953 raw_ostream &operator<<(raw_ostream &OS,
c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	954 const Print<NodeAddr<InstrNode *>> &P);
c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	955 raw_ostream &operator<<(raw_ostream &OS,
c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	956 const Print<NodeAddr<BlockNode *>> &P);
c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	957 raw_ostream &operator<<(raw_ostream &OS,
c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	958 const Print<NodeAddr<FuncNode *>> &P);
c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	959 raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterSet> &P);
c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	960 raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterAggr> &P);
c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	961 raw_ostream &operator<<(raw_ostream &OS,
c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	962 const Print<DataFlowGraph::DefStack> &P);
c2174574ed3a LLVM 10 Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 134 diff changeset	963
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	964 } // end namespace rdf
100 7d135dc70f03 LLVM 3.9 Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp> parents: diff changeset	965
121 803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	966 } // end namespace llvm
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	967
803732b1fca8 LLVM 5.0 kono parents: 120 diff changeset	968 #endif // LLVM_LIB_TARGET_HEXAGON_RDFGRAPH_H

Mercurial > hg > CbC > CbC_llvm

annotate lib/Target/Hexagon/RDFGraph.h @ 147:c2174574ed3a