Viewing file:  insns.h (18.72 KB) -rw-r--r--
Select action/file-type:
 (+) |  (+) |  (+) | Code (+) | Session (+) |  (+) | SDB (+) |  (+) |  (+) |  (+) |  (+) |  (+) |
// Instruction-related RTL SSA classes -*- C++ -*-
// Copyright (C) 2020-2022 Free Software Foundation, Inc.
//
// This file is part of GCC.
//
// GCC is free software; you can redistribute it and/or modify it under
// the terms of the GNU General Public License as published by the Free
// Software Foundation; either version 3, or (at your option) any later
// version.
//
// GCC is distributed in the hope that it will be useful, but WITHOUT ANY
// WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
// for more details.
//
// You should have received a copy of the GNU General Public License
// along with GCC; see the file COPYING3. If not see
// <http://www.gnu.org/licenses/>.
namespace rtl_ssa {
// A fake cost for instructions that we haven't costed yet.
const int UNKNOWN_COST = INT_MAX;
// Enumerates the kinds of note that can be added to an instruction.
// See the comment above insn_info for details.
enum class insn_note_kind : uint8_t
{
ORDER_NODE,
CALL_CLOBBERS
};
// The base class for notes that can be added to an instruction.
// See the comment above insn_info for details.
class insn_note
{
// Size: 2 LP64 words.
friend class insn_info;
friend class function_info;
public:
// Return what kind of note this is.
insn_note_kind kind () const { return m_kind; }
// Return the next note in the list, or null if none.
insn_note *next_note () const { return m_next_note; }
// Used with T = Derived *, where Derived is derived from insn_note.
// Convert the note to Derived, asserting that it has the right kind.
template<typename T>
T as_a ();
// Used with T = Derived *, where Derived is derived from insn_note.
// If the note is a Derived note, return it in that form, otherwise
// return null.
template<typename T>
T dyn_cast ();
protected:
// Construct a note with the given kind.
insn_note (insn_note_kind);
private:
// The next note in the list, or null if none.
insn_note *m_next_note;
// The kind of note this is.
insn_note_kind m_kind : 8;
protected:
// Fill in the remaining LP64 word with data that derived classes can use.
unsigned int m_data8 : 8;
unsigned int m_data16 : 16;
unsigned int m_data32 : 32;
};
// Instructions have one of these notes if insn_info::has_call_clobbers ()
// is true. All such instructions in an EBB are first grouped together
// by the predefined_function_abis of the functions that they call.
// Then, for each such predefined ABI, the call_clobbers notes are put
// into a splay tree whose nodes follow execution order.
class insn_call_clobbers_note : public insn_note
{
friend class function_info;
friend class default_splay_tree_accessors<insn_call_clobbers_note *>;
public:
static const insn_note_kind kind = insn_note_kind::CALL_CLOBBERS;
// Return the identifier of the predefined_function_abi.
unsigned int abi_id () const { return m_data32; }
// Return the instruction to which the note is attached.
insn_info *insn () const { return m_insn; }
protected:
insn_call_clobbers_note (unsigned int abi_id, insn_info *insn);
// The splay tree pointers.
insn_call_clobbers_note *m_children[2];
// The value returned by insn ().
insn_info *m_insn;
};
// A splay tree of insn_call_clobbers_notes.
using insn_call_clobbers_tree = default_splay_tree<insn_call_clobbers_note *>;
// SSA-related information about an instruction. It also represents
// artificial instructions that are added to make the dataflow correct;
// these artificial instructions fall into three categories:
//
// - Instructions that hold the phi nodes for an extended basic block (is_phi).
//
// - Instructions that represent the head of a basic block and that hold
// all the associated artificial uses and definitions.
//
// - Instructions that represent the end of a basic block and that again
// hold all the associated artificial uses and definitions.
//
// Dataflow-wise, each instruction goes through three stages:
//
// (1) Use all the values in uses ().
//
// (2) If has_call_clobbers (), clobber the registers indicated by
// insn_callee_abi.
//
// (3) Define all the values in defs ().
//
// Having stage (2) is a trade-off: it makes processing the instructions
// more complicated, but it saves having to allocate memory for every
// individual call clobber. Without it, clobbers for calls would often
// make up a large proportion of the total definitions in a function.
//
// All the instructions in a function are chained together in a list
// that follows a reverse postorder traversal of the CFG. The list
// contains both debug and nondebug instructions, but it is possible
// to hop from one nondebug instruction to the next with constant complexity.
//
// Instructions can have supplemental information attached in the form
// of "notes", a bit like REG_NOTES for the underlying RTL insns.
class insn_info
{
// Size: 9 LP64 words.
friend class ebb_info;
friend class function_info;
public:
// Compare instructions by their positions in the function list described
// above. Thus for two instructions in the same basic block, I1 < I2 if
// I1 comes before I2 in the block.
bool operator< (const insn_info &) const;
bool operator<= (const insn_info &) const;
bool operator>= (const insn_info &) const;
bool operator> (const insn_info &) const;
// Return -1 if this instruction comes before INSN in the reverse
// postorder, 0 if this instruction is INSN, or 1 if this instruction
// comes after INSN in the reverse postorder.
int compare_with (const insn_info *insn) const;
// Return the previous and next instructions in the list described above,
// or null if there are no such instructions.
insn_info *prev_any_insn () const;
insn_info *next_any_insn () const;
// Only valid if !is_debug_insn (). Return the previous and next
// nondebug instructions in the list described above, skipping over
// any intervening debug instructions. These are constant-time operations.
insn_info *prev_nondebug_insn () const;
insn_info *next_nondebug_insn () const;
// Return the underlying RTL insn. This instruction is null if is_phi ()
// or is_bb_end () are true. The instruction is a basic block note if
// is_bb_head () is true.
rtx_insn *rtl () const { return m_rtl; }
// Return true if the instruction is a real insn with an rtl pattern.
// Return false if it is an artificial instruction that represents the
// phi nodes in an extended basic block or the head or end of a basic block.
bool is_real () const { return m_cost_or_uid >= 0; }
// Return the opposite of is_real ().
bool is_artificial () const { return m_cost_or_uid < 0; }
// Return true if the instruction was a real instruction but has now
// been deleted. In this case the instruction is no longer part of
// the SSA information.
bool has_been_deleted () const { return m_rtl && !INSN_P (m_rtl); }
// Return true if the instruction is a debug instruction (and thus
// also a real instruction).
bool is_debug_insn () const { return m_is_debug_insn; }
// Return true if the instruction is something that we can optimize.
// This implies that it is a real instruction that contains an asm
// or that contains something that matches an .md define_insn pattern.
bool can_be_optimized () const { return m_can_be_optimized; }
// Return true if the instruction is a call instruction.
//
// ??? We could cache this information, but since most callers would
// go on to access PATTERN (rtl ()), a cache might not be helpful and
// could even be counterproductive.
bool is_call () const { return CALL_P (m_rtl); }
// Return true if the instruction is a jump instruction.
//
// ??? See is_call for the reason we don't cache this.
bool is_jump () const { return JUMP_P (m_rtl); }
// Return true if the instruction is real and contains an inline asm.
bool is_asm () const { return m_is_asm; }
// Return true if the instruction is real and includes an RTX_AUTOINC
// operation.
bool has_pre_post_modify () const { return m_has_pre_post_modify; }
// Return true if the instruction is real and has volatile references,
// in the sense of volatile_refs_p. This includes volatile memory,
// volatile asms and UNSPEC_VOLATILEs.
bool has_volatile_refs () const { return m_has_volatile_refs; }
// Return true if the instruction is aritificial and if its (sole)
// purpose is to hold the phi nodes in an extended basic block.
bool is_phi () const;
// Return true if the instruction is artificial and if it represents
// the head of a basic block. If so, the instruction conceptually
// executes before the real instructions in the block. The uses
// and definitions represent the df_get_artificial_uses and
// df_get_artificial_defs entries for the head of the block.
bool is_bb_head () const;
// Return true if the instruction is artificial and if it represents
// the end of a basic block. The uses and definitions represent the
// the df_get_artificial_uses and df_get_artificial_defs entries for
// the end of the block.
bool is_bb_end () const;
// Return the basic block that the instruction is in.
bb_info *bb () const { return m_bb; }
// Return the extended basic block that the instruction is in;
// see bb_info for details.
ebb_info *ebb () const;
// If the instruction is real, return the unique identifier of the
// underlying RTL insn. If the instruction is artificial, return
// a unique negative identifier for the instructions.
//
// Note that the identifiers are not linear: it can be the case that
// an instruction with a higher uid comes earlier in a block than an
// instruction with a lower uid. The identifiers are however persistent;
// the identifier remains the same after the instruction has been moved
// or changed.
int uid () const;
// Return the list of things that this instruction uses. Registers
// come first, in register number order, followed by memory.
use_array uses () const;
// Return true if the instruction is a call and if the clobbers
// described by insn_callee_abi have been omitted from the list
// of definitions.
bool has_call_clobbers () const;
// Return the list of things that this instruction sets or clobbers.
// Registers come first, in register number order, followed by memory.
//
// If has_call_clobbers () is true, the list omits both the full and
// partial register clobbers described by insn_callee_abi.
def_array defs () const;
// The number of entries in uses ().
unsigned int num_uses () const { return m_num_uses; }
// The number of entries in defs ().
unsigned int num_defs () const { return m_num_defs; }
// Return the cost of the instruction, as calculated by the target.
// For performance reasons, the cost is evaluated lazily on first use.
//
// Artificial instructions have a cost of 0.
unsigned int cost () const;
// Return the first insn_note attached to the instruction, or null
// if none.
insn_note *first_note () const { return m_first_note; }
// See if a note of type T is attached to the instruction. Return it
// if so, otherwise return null.
template<typename T>
const T *find_note () const;
// Print "i" + uid () for real instructions and "a" + -uid () for
// artificial instructions.
void print_identifier (pretty_printer *) const;
// Print a short(ish) description of where the instruction is.
void print_location (pretty_printer *) const;
// Combine print_identifier and print_location.
void print_identifier_and_location (pretty_printer *) const;
// Print a full description of the instruction.
void print_full (pretty_printer *) const;
private:
// The first-order way of representing the order between instructions
// is to assign "program points", with higher point numbers coming
// later in the reverse postorder than lower point numbers. However,
// after a sequence of instruction movements, we may end up in a situation
// that adjacent instructions have the same program point.
//
// When that happens, we put the instructions into a splay tree that
// records their relative order. Each node of the splay tree is an
// order_node note that is attached to its respective instruction.
// The root of the splay tree is not stored, since the only thing
// we need the tree for is to compare two nodes.
class order_node : public insn_note
{
public:
static const insn_note_kind kind = insn_note_kind::ORDER_NODE;
order_node (int uid);
// Return the uid of the instruction that this node describes.
int uid () const { return m_data32; }
// The splay tree pointers.
order_node *m_children[2];
order_node *m_parent;
};
using order_splay_tree = default_rootless_splay_tree<order_node *>;
// prev_insn_or_last_debug_insn represents a choice between two things:
//
// (1) A pointer to the previous instruction in the list that has the
// same is_debug_insn () value, or null if no such instruction exists.
//
// (2) A pointer to the end of a sublist of debug instructions.
//
// (2) is used if this instruction is a debug instruction and the
// previous instruction is not. (1) is used otherwise.
//
// next_nondebug_or_debug_insn points to the next instruction but also
// records whether that next instruction is a debug instruction or a
// nondebug instruction.
//
// Thus the list is chained as follows:
//
// ----> ----> ----> ----> ---->
// NONDEBUG NONDEBUG DEBUG DEBUG DEBUG NONDEBUG ...
// <---- ^ +-- <---- <---- ^ +--
// | | | |
// | +------------------------+ |
// | |
// +-----------------------------------+
using prev_insn_or_last_debug_insn = pointer_mux<insn_info>;
using next_nondebug_or_debug_insn = pointer_mux<insn_info>;
insn_info (bb_info *bb, rtx_insn *rtl, int cost_or_uid);
static void print_uid (pretty_printer *, int);
void calculate_cost () const;
void set_properties (const rtx_properties &);
void set_accesses (access_info **, unsigned int, unsigned int);
void copy_accesses (access_array, access_array);
void set_cost (unsigned int cost) { m_cost_or_uid = cost; }
void set_bb (bb_info *bb) { m_bb = bb; }
void add_note (insn_note *note);
order_node *get_order_node () const;
order_node *get_known_order_node () const;
int slow_compare_with (const insn_info &) const;
insn_info *last_debug_insn () const;
unsigned int point () const { return m_point; }
void copy_prev_from (insn_info *);
void copy_next_from (insn_info *);
void set_prev_sametype_insn (insn_info *);
void set_last_debug_insn (insn_info *);
void set_next_any_insn (insn_info *);
void set_point (unsigned int point) { m_point = point; }
void clear_insn_links ();
bool has_insn_links ();
// The values returned by the accessors above.
prev_insn_or_last_debug_insn m_prev_insn_or_last_debug_insn;
next_nondebug_or_debug_insn m_next_nondebug_or_debug_insn;
bb_info *m_bb;
rtx_insn *m_rtl;
// The list of definitions followed by the list of uses.
access_info **m_accesses;
// The number of definitions and the number uses. FIRST_PSEUDO_REGISTER + 1
// is the maximum number of accesses to hard registers and memory, and
// MAX_RECOG_OPERANDS is the maximum number of pseudos that can be
// defined by an instruction, so the number of definitions in a real
// instruction should fit easily in 16 bits. However, there are no
// limits on the number of definitions in artifical instructions.
unsigned int m_num_uses;
unsigned int m_num_defs;
// Flags returned by the accessors above.
unsigned int m_is_debug_insn : 1;
unsigned int m_can_be_optimized : 1;
unsigned int m_is_asm : 1;
unsigned int m_has_pre_post_modify : 1;
unsigned int m_has_volatile_refs : 1;
// For future expansion.
unsigned int m_spare : 27;
// The program point at which the instruction occurs.
//
// Note that the values of the program points are influenced by -g
// and so should not used to make codegen decisions.
unsigned int m_point;
// Negative if the instruction is artificial, nonnegative if it is real.
//
// For real instructions: the cost of the instruction, or UNKNOWN_COST
// if we haven't measured it yet.
//
// For artificial instructions: the (negative) unique identifier of the
// instruction.
mutable int m_cost_or_uid;
// On LP64 systems, there's a gap here that could be used for future
// expansion.
// The list of notes that have been attached to the instruction.
insn_note *m_first_note;
};
// Iterators for unfiltered lists of instructions.
using any_insn_iterator = list_iterator<insn_info, &insn_info::next_any_insn>;
using reverse_any_insn_iterator
= list_iterator<insn_info, &insn_info::prev_any_insn>;
// Iterators for nondebug instructions only.
using nondebug_insn_iterator
= list_iterator<insn_info, &insn_info::next_nondebug_insn>;
using reverse_nondebug_insn_iterator
= list_iterator<insn_info, &insn_info::prev_nondebug_insn>;
// A class that describes an inclusive range of instructions.
class insn_range_info
{
public:
insn_range_info () = default;
// Create a range that contains a singleton instruction.
insn_range_info (insn_info *insn) : first (insn), last (insn) {}
// Create a range [FIRST, LAST], given that *FIRST <= *LAST.
insn_range_info (insn_info *first, insn_info *last);
// Return true if the range contains at least one instruction.
explicit operator bool () const { return *first <= *last; }
bool operator== (const insn_range_info &) const;
bool operator!= (const insn_range_info &) const;
// If the range contains a single instruction, return that instruction,
// otherwise return null.
insn_info *singleton () const;
// Return true if the range includes INSN.
bool includes (insn_info *insn) const;
// If INSN is inside the range, return INSN, otherwise return the
// nearest in-range instruction.
insn_info *clamp_insn_to_range (insn_info *insn) const;
// Return true if this range is a subrange of OTHER, i.e. if OTHER
// includes every instruction that this range does.
bool is_subrange_of (const insn_range_info &other) const;
// The lower and upper bounds of the range.
insn_info *first;
insn_info *last;
};
// A class that represents a closure of operator== for instructions.
// This is used by insn_is; see there for details.
class insn_is_closure
{
public:
insn_is_closure (const insn_info *insn) : m_insn (insn) {}
bool operator() (const insn_info *other) const { return m_insn == other; }
private:
const insn_info *m_insn;
};
void pp_insn (pretty_printer *, const insn_info *);
}
void dump (FILE *, const rtl_ssa::insn_info *);
void DEBUG_FUNCTION debug (const rtl_ssa::insn_info *);
|
