mirror of
https://github.com/autc04/Retro68.git
synced 2024-06-25 21:29:51 +00:00
612 lines
16 KiB
C++
612 lines
16 KiB
C++
/* "Supergraph" classes that combine CFGs and callgraph into one digraph.
|
|
Copyright (C) 2019-2022 Free Software Foundation, Inc.
|
|
Contributed by David Malcolm <dmalcolm@redhat.com>.
|
|
|
|
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/>. */
|
|
|
|
#ifndef GCC_ANALYZER_SUPERGRAPH_H
|
|
#define GCC_ANALYZER_SUPERGRAPH_H
|
|
|
|
using namespace ana;
|
|
|
|
namespace ana {
|
|
|
|
/* Forward decls, using indentation to show inheritance. */
|
|
|
|
class supergraph;
|
|
class supernode;
|
|
class superedge;
|
|
class callgraph_superedge;
|
|
class call_superedge;
|
|
class return_superedge;
|
|
class cfg_superedge;
|
|
class switch_cfg_superedge;
|
|
class supercluster;
|
|
class dot_annotator;
|
|
|
|
class logger;
|
|
|
|
/* An enum for discriminating between superedge subclasses. */
|
|
|
|
enum edge_kind
|
|
{
|
|
SUPEREDGE_CFG_EDGE,
|
|
SUPEREDGE_CALL,
|
|
SUPEREDGE_RETURN,
|
|
SUPEREDGE_INTRAPROCEDURAL_CALL
|
|
};
|
|
|
|
/* Flags for controlling the appearance of .dot dumps. */
|
|
|
|
enum supergraph_dot_flags
|
|
{
|
|
SUPERGRAPH_DOT_SHOW_BBS = (1 << 0)
|
|
};
|
|
|
|
/* A traits struct describing the family of node, edge and digraph
|
|
classes for supergraphs. */
|
|
|
|
struct supergraph_traits
|
|
{
|
|
typedef supernode node_t;
|
|
typedef superedge edge_t;
|
|
typedef supergraph graph_t;
|
|
struct dump_args_t
|
|
{
|
|
dump_args_t (enum supergraph_dot_flags flags,
|
|
const dot_annotator *node_annotator)
|
|
: m_flags (flags),
|
|
m_node_annotator (node_annotator)
|
|
{}
|
|
|
|
enum supergraph_dot_flags m_flags;
|
|
const dot_annotator *m_node_annotator;
|
|
};
|
|
typedef supercluster cluster_t;
|
|
};
|
|
|
|
/* A class to manage the setting and restoring of statement uids. */
|
|
|
|
class saved_uids
|
|
{
|
|
public:
|
|
void make_uid_unique (gimple *stmt);
|
|
void restore_uids () const;
|
|
|
|
private:
|
|
auto_vec<std::pair<gimple *, unsigned> > m_old_stmt_uids;
|
|
};
|
|
|
|
/* A "supergraph" is a directed graph formed by joining together all CFGs,
|
|
linking them via interprocedural call and return edges.
|
|
|
|
Basic blocks are split at callsites, so that a call statement occurs
|
|
twice: once at the end of a supernode, and a second instance at the
|
|
start of the next supernode (to handle the return). */
|
|
|
|
class supergraph : public digraph<supergraph_traits>
|
|
{
|
|
public:
|
|
supergraph (logger *logger);
|
|
~supergraph ();
|
|
|
|
supernode *get_node_for_function_entry (function *fun) const
|
|
{
|
|
return get_node_for_block (ENTRY_BLOCK_PTR_FOR_FN (fun));
|
|
}
|
|
|
|
supernode *get_node_for_function_exit (function *fun) const
|
|
{
|
|
return get_node_for_block (EXIT_BLOCK_PTR_FOR_FN (fun));
|
|
}
|
|
|
|
supernode *get_node_for_block (basic_block bb) const
|
|
{
|
|
return *const_cast <bb_to_node_t &> (m_bb_to_initial_node).get (bb);
|
|
}
|
|
|
|
/* Get the supernode containing the second half of the gcall *
|
|
at an interprocedural call, within the caller. */
|
|
supernode *get_caller_next_node (cgraph_edge *edge) const
|
|
{
|
|
return (*const_cast <cgraph_edge_to_node_t &>
|
|
(m_cgraph_edge_to_caller_next_node).get (edge));
|
|
}
|
|
|
|
call_superedge *get_edge_for_call (cgraph_edge *edge) const
|
|
{
|
|
return (*const_cast <cgraph_edge_to_call_superedge_t &>
|
|
(m_cgraph_edge_to_call_superedge).get (edge));
|
|
}
|
|
|
|
return_superedge *get_edge_for_return (cgraph_edge *edge) const
|
|
{
|
|
return (*const_cast <cgraph_edge_to_return_superedge_t &>
|
|
(m_cgraph_edge_to_return_superedge).get (edge));
|
|
}
|
|
|
|
superedge *get_intraprocedural_edge_for_call (cgraph_edge *edge) const
|
|
{
|
|
return (*const_cast <cgraph_edge_to_intraproc_superedge_t &>
|
|
(m_cgraph_edge_to_intraproc_superedge).get (edge));
|
|
}
|
|
|
|
cfg_superedge *get_edge_for_cfg_edge (edge e) const
|
|
{
|
|
return (*const_cast <cfg_edge_to_cfg_superedge_t &>
|
|
(m_cfg_edge_to_cfg_superedge).get (e));
|
|
}
|
|
|
|
supernode *get_supernode_for_stmt (const gimple *stmt) const
|
|
{
|
|
return (*const_cast <stmt_to_node_t &>(m_stmt_to_node_t).get
|
|
(const_cast <gimple *> (stmt)));
|
|
}
|
|
|
|
void dump_dot_to_pp (pretty_printer *pp, const dump_args_t &) const;
|
|
void dump_dot_to_file (FILE *fp, const dump_args_t &) const;
|
|
void dump_dot (const char *path, const dump_args_t &) const;
|
|
|
|
json::object *to_json () const;
|
|
|
|
int num_nodes () const { return m_nodes.length (); }
|
|
int num_edges () const { return m_edges.length (); }
|
|
|
|
supernode *get_node_by_index (int idx) const
|
|
{
|
|
return m_nodes[idx];
|
|
}
|
|
|
|
unsigned get_num_snodes (const function *fun) const
|
|
{
|
|
function_to_num_snodes_t &map
|
|
= const_cast <function_to_num_snodes_t &>(m_function_to_num_snodes);
|
|
return *map.get (fun);
|
|
}
|
|
|
|
private:
|
|
supernode *add_node (function *fun, basic_block bb, gcall *returning_call,
|
|
gimple_seq phi_nodes);
|
|
cfg_superedge *add_cfg_edge (supernode *src, supernode *dest, ::edge e);
|
|
call_superedge *add_call_superedge (supernode *src, supernode *dest,
|
|
cgraph_edge *cedge);
|
|
return_superedge *add_return_superedge (supernode *src, supernode *dest,
|
|
cgraph_edge *cedge);
|
|
|
|
/* Data. */
|
|
|
|
typedef ordered_hash_map<basic_block, supernode *> bb_to_node_t;
|
|
bb_to_node_t m_bb_to_initial_node;
|
|
bb_to_node_t m_bb_to_final_node;
|
|
|
|
typedef ordered_hash_map<cgraph_edge *, supernode *> cgraph_edge_to_node_t;
|
|
cgraph_edge_to_node_t m_cgraph_edge_to_caller_prev_node;
|
|
cgraph_edge_to_node_t m_cgraph_edge_to_caller_next_node;
|
|
|
|
typedef ordered_hash_map< ::edge, cfg_superedge *>
|
|
cfg_edge_to_cfg_superedge_t;
|
|
cfg_edge_to_cfg_superedge_t m_cfg_edge_to_cfg_superedge;
|
|
|
|
typedef ordered_hash_map<cgraph_edge *, call_superedge *>
|
|
cgraph_edge_to_call_superedge_t;
|
|
cgraph_edge_to_call_superedge_t m_cgraph_edge_to_call_superedge;
|
|
|
|
typedef ordered_hash_map<cgraph_edge *, return_superedge *>
|
|
cgraph_edge_to_return_superedge_t;
|
|
cgraph_edge_to_return_superedge_t m_cgraph_edge_to_return_superedge;
|
|
|
|
typedef ordered_hash_map<cgraph_edge *, superedge *>
|
|
cgraph_edge_to_intraproc_superedge_t;
|
|
cgraph_edge_to_intraproc_superedge_t m_cgraph_edge_to_intraproc_superedge;
|
|
|
|
typedef ordered_hash_map<gimple *, supernode *> stmt_to_node_t;
|
|
stmt_to_node_t m_stmt_to_node_t;
|
|
|
|
typedef hash_map<const function *, unsigned> function_to_num_snodes_t;
|
|
function_to_num_snodes_t m_function_to_num_snodes;
|
|
|
|
saved_uids m_stmt_uids;
|
|
};
|
|
|
|
/* A node within a supergraph. */
|
|
|
|
class supernode : public dnode<supergraph_traits>
|
|
{
|
|
public:
|
|
supernode (function *fun, basic_block bb, gcall *returning_call,
|
|
gimple_seq phi_nodes, int index)
|
|
: m_fun (fun), m_bb (bb), m_returning_call (returning_call),
|
|
m_phi_nodes (phi_nodes), m_index (index)
|
|
{}
|
|
|
|
function *get_function () const { return m_fun; }
|
|
|
|
bool entry_p () const
|
|
{
|
|
return m_bb == ENTRY_BLOCK_PTR_FOR_FN (m_fun);
|
|
}
|
|
|
|
bool return_p () const
|
|
{
|
|
return m_bb == EXIT_BLOCK_PTR_FOR_FN (m_fun);
|
|
}
|
|
|
|
void dump_dot (graphviz_out *gv, const dump_args_t &args) const OVERRIDE;
|
|
void dump_dot_id (pretty_printer *pp) const;
|
|
|
|
json::object *to_json () const;
|
|
|
|
location_t get_start_location () const;
|
|
location_t get_end_location () const;
|
|
|
|
/* Returns iterator at the start of the list of phi nodes, if any. */
|
|
gphi_iterator start_phis ()
|
|
{
|
|
gimple_seq *pseq = &m_phi_nodes;
|
|
|
|
/* Adapted from gsi_start_1. */
|
|
gphi_iterator i;
|
|
|
|
i.ptr = gimple_seq_first (*pseq);
|
|
i.seq = pseq;
|
|
i.bb = i.ptr ? gimple_bb (i.ptr) : NULL;
|
|
|
|
return i;
|
|
}
|
|
|
|
gcall *get_returning_call () const
|
|
{
|
|
return m_returning_call;
|
|
}
|
|
|
|
gimple *get_last_stmt () const
|
|
{
|
|
if (m_stmts.length () == 0)
|
|
return NULL;
|
|
return m_stmts[m_stmts.length () - 1];
|
|
}
|
|
|
|
gcall *get_final_call () const
|
|
{
|
|
gimple *stmt = get_last_stmt ();
|
|
if (stmt == NULL)
|
|
return NULL;
|
|
return dyn_cast<gcall *> (stmt);
|
|
}
|
|
|
|
unsigned int get_stmt_index (const gimple *stmt) const;
|
|
|
|
function * const m_fun; // alternatively could be stored as runs of indices within the supergraph
|
|
const basic_block m_bb;
|
|
gcall * const m_returning_call; // for handling the result of a returned call
|
|
gimple_seq m_phi_nodes; // ptr to that of the underlying BB, for the first supernode for the BB
|
|
auto_vec<gimple *> m_stmts;
|
|
const int m_index; /* unique within the supergraph as a whole. */
|
|
};
|
|
|
|
/* An abstract base class encapsulating an edge within a supergraph.
|
|
Edges can be CFG edges, or calls/returns for callgraph edges. */
|
|
|
|
class superedge : public dedge<supergraph_traits>
|
|
{
|
|
public:
|
|
virtual ~superedge () {}
|
|
|
|
void dump (pretty_printer *pp) const;
|
|
void dump () const;
|
|
void dump_dot (graphviz_out *gv, const dump_args_t &args) const;
|
|
|
|
virtual void dump_label_to_pp (pretty_printer *pp,
|
|
bool user_facing) const = 0;
|
|
|
|
json::object *to_json () const;
|
|
|
|
enum edge_kind get_kind () const { return m_kind; }
|
|
|
|
virtual cfg_superedge *dyn_cast_cfg_superedge () { return NULL; }
|
|
virtual const cfg_superedge *dyn_cast_cfg_superedge () const { return NULL; }
|
|
virtual const switch_cfg_superedge *dyn_cast_switch_cfg_superedge () const { return NULL; }
|
|
virtual callgraph_superedge *dyn_cast_callgraph_superedge () { return NULL; }
|
|
virtual const callgraph_superedge *dyn_cast_callgraph_superedge () const { return NULL; }
|
|
virtual call_superedge *dyn_cast_call_superedge () { return NULL; }
|
|
virtual const call_superedge *dyn_cast_call_superedge () const { return NULL; }
|
|
virtual return_superedge *dyn_cast_return_superedge () { return NULL; }
|
|
virtual const return_superedge *dyn_cast_return_superedge () const { return NULL; }
|
|
|
|
::edge get_any_cfg_edge () const;
|
|
cgraph_edge *get_any_callgraph_edge () const;
|
|
|
|
char *get_description (bool user_facing) const;
|
|
|
|
protected:
|
|
superedge (supernode *src, supernode *dest, enum edge_kind kind)
|
|
: dedge<supergraph_traits> (src, dest),
|
|
m_kind (kind)
|
|
{}
|
|
|
|
public:
|
|
const enum edge_kind m_kind;
|
|
};
|
|
|
|
/* An ID representing an expression at a callsite:
|
|
either a parameter index, or the return value (or unknown). */
|
|
|
|
class callsite_expr
|
|
{
|
|
public:
|
|
callsite_expr () : m_val (-1) {}
|
|
|
|
static callsite_expr from_zero_based_param (int idx)
|
|
{
|
|
return callsite_expr (idx + 1);
|
|
}
|
|
|
|
static callsite_expr from_return_value ()
|
|
{
|
|
return callsite_expr (0);
|
|
}
|
|
|
|
bool param_p () const
|
|
{
|
|
return m_val > 0;
|
|
}
|
|
|
|
bool return_value_p () const
|
|
{
|
|
return m_val == 0;
|
|
}
|
|
|
|
private:
|
|
callsite_expr (int val) : m_val (val) {}
|
|
|
|
int m_val; /* 1-based parm, 0 for return value, or -1 for "unknown". */
|
|
};
|
|
|
|
/* A subclass of superedge with an associated callgraph edge (either a
|
|
call or a return). */
|
|
|
|
class callgraph_superedge : public superedge
|
|
{
|
|
public:
|
|
callgraph_superedge (supernode *src, supernode *dst, enum edge_kind kind,
|
|
cgraph_edge *cedge)
|
|
: superedge (src, dst, kind),
|
|
m_cedge (cedge)
|
|
{}
|
|
|
|
void dump_label_to_pp (pretty_printer *pp, bool user_facing) const
|
|
FINAL OVERRIDE;
|
|
|
|
callgraph_superedge *dyn_cast_callgraph_superedge () FINAL OVERRIDE
|
|
{
|
|
return this;
|
|
}
|
|
const callgraph_superedge *dyn_cast_callgraph_superedge () const
|
|
FINAL OVERRIDE
|
|
{
|
|
return this;
|
|
}
|
|
|
|
function *get_callee_function () const;
|
|
function *get_caller_function () const;
|
|
tree get_callee_decl () const;
|
|
tree get_caller_decl () const;
|
|
gcall *get_call_stmt () const;
|
|
tree get_arg_for_parm (tree parm, callsite_expr *out) const;
|
|
tree get_parm_for_arg (tree arg, callsite_expr *out) const;
|
|
tree map_expr_from_caller_to_callee (tree caller_expr,
|
|
callsite_expr *out) const;
|
|
tree map_expr_from_callee_to_caller (tree callee_expr,
|
|
callsite_expr *out) const;
|
|
|
|
cgraph_edge *const m_cedge;
|
|
};
|
|
|
|
} // namespace ana
|
|
|
|
template <>
|
|
template <>
|
|
inline bool
|
|
is_a_helper <const callgraph_superedge *>::test (const superedge *sedge)
|
|
{
|
|
return (sedge->get_kind () == SUPEREDGE_INTRAPROCEDURAL_CALL
|
|
|| sedge->get_kind () == SUPEREDGE_CALL
|
|
|| sedge->get_kind () == SUPEREDGE_RETURN);
|
|
}
|
|
|
|
namespace ana {
|
|
|
|
/* A subclass of superedge representing an interprocedural call. */
|
|
|
|
class call_superedge : public callgraph_superedge
|
|
{
|
|
public:
|
|
call_superedge (supernode *src, supernode *dst, cgraph_edge *cedge)
|
|
: callgraph_superedge (src, dst, SUPEREDGE_CALL, cedge)
|
|
{}
|
|
|
|
call_superedge *dyn_cast_call_superedge () FINAL OVERRIDE
|
|
{
|
|
return this;
|
|
}
|
|
const call_superedge *dyn_cast_call_superedge () const FINAL OVERRIDE
|
|
{
|
|
return this;
|
|
}
|
|
|
|
return_superedge *get_edge_for_return (const supergraph &sg) const
|
|
{
|
|
return sg.get_edge_for_return (m_cedge);
|
|
}
|
|
};
|
|
|
|
} // namespace ana
|
|
|
|
template <>
|
|
template <>
|
|
inline bool
|
|
is_a_helper <const call_superedge *>::test (const superedge *sedge)
|
|
{
|
|
return sedge->get_kind () == SUPEREDGE_CALL;
|
|
}
|
|
|
|
namespace ana {
|
|
|
|
/* A subclass of superedge represesnting an interprocedural return. */
|
|
|
|
class return_superedge : public callgraph_superedge
|
|
{
|
|
public:
|
|
return_superedge (supernode *src, supernode *dst, cgraph_edge *cedge)
|
|
: callgraph_superedge (src, dst, SUPEREDGE_RETURN, cedge)
|
|
{}
|
|
|
|
return_superedge *dyn_cast_return_superedge () FINAL OVERRIDE { return this; }
|
|
const return_superedge *dyn_cast_return_superedge () const FINAL OVERRIDE
|
|
{
|
|
return this;
|
|
}
|
|
|
|
call_superedge *get_edge_for_call (const supergraph &sg) const
|
|
{
|
|
return sg.get_edge_for_call (m_cedge);
|
|
}
|
|
};
|
|
|
|
} // namespace ana
|
|
|
|
template <>
|
|
template <>
|
|
inline bool
|
|
is_a_helper <const return_superedge *>::test (const superedge *sedge)
|
|
{
|
|
return sedge->get_kind () == SUPEREDGE_RETURN;
|
|
}
|
|
|
|
namespace ana {
|
|
|
|
/* A subclass of superedge that corresponds to a CFG edge. */
|
|
|
|
class cfg_superedge : public superedge
|
|
{
|
|
public:
|
|
cfg_superedge (supernode *src, supernode *dst, ::edge e)
|
|
: superedge (src, dst, SUPEREDGE_CFG_EDGE),
|
|
m_cfg_edge (e)
|
|
{}
|
|
|
|
void dump_label_to_pp (pretty_printer *pp, bool user_facing) const OVERRIDE;
|
|
cfg_superedge *dyn_cast_cfg_superedge () FINAL OVERRIDE { return this; }
|
|
const cfg_superedge *dyn_cast_cfg_superedge () const FINAL OVERRIDE { return this; }
|
|
|
|
::edge get_cfg_edge () const { return m_cfg_edge; }
|
|
int get_flags () const { return m_cfg_edge->flags; }
|
|
int true_value_p () const { return get_flags () & EDGE_TRUE_VALUE; }
|
|
int false_value_p () const { return get_flags () & EDGE_FALSE_VALUE; }
|
|
int back_edge_p () const { return get_flags () & EDGE_DFS_BACK; }
|
|
|
|
size_t get_phi_arg_idx () const;
|
|
tree get_phi_arg (const gphi *phi) const;
|
|
|
|
private:
|
|
const ::edge m_cfg_edge;
|
|
};
|
|
|
|
} // namespace ana
|
|
|
|
template <>
|
|
template <>
|
|
inline bool
|
|
is_a_helper <const cfg_superedge *>::test (const superedge *sedge)
|
|
{
|
|
return sedge->get_kind () == SUPEREDGE_CFG_EDGE;
|
|
}
|
|
|
|
namespace ana {
|
|
|
|
/* A subclass for edges from switch statements, retaining enough
|
|
information to identify the pertinent cases, and for adding labels
|
|
when rendering via graphviz. */
|
|
|
|
class switch_cfg_superedge : public cfg_superedge {
|
|
public:
|
|
switch_cfg_superedge (supernode *src, supernode *dst, ::edge e);
|
|
|
|
const switch_cfg_superedge *dyn_cast_switch_cfg_superedge () const
|
|
FINAL OVERRIDE
|
|
{
|
|
return this;
|
|
}
|
|
|
|
void dump_label_to_pp (pretty_printer *pp, bool user_facing) const
|
|
FINAL OVERRIDE;
|
|
|
|
gswitch *get_switch_stmt () const
|
|
{
|
|
return as_a <gswitch *> (m_src->get_last_stmt ());
|
|
}
|
|
|
|
const vec<tree> &get_case_labels () const { return m_case_labels; }
|
|
|
|
private:
|
|
auto_vec<tree> m_case_labels;
|
|
};
|
|
|
|
} // namespace ana
|
|
|
|
template <>
|
|
template <>
|
|
inline bool
|
|
is_a_helper <const switch_cfg_superedge *>::test (const superedge *sedge)
|
|
{
|
|
return sedge->dyn_cast_switch_cfg_superedge () != NULL;
|
|
}
|
|
|
|
namespace ana {
|
|
|
|
/* Base class for adding additional content to the .dot output
|
|
for a supergraph. */
|
|
|
|
class dot_annotator
|
|
{
|
|
public:
|
|
virtual ~dot_annotator () {}
|
|
virtual bool add_node_annotations (graphviz_out *gv ATTRIBUTE_UNUSED,
|
|
const supernode &n ATTRIBUTE_UNUSED,
|
|
bool within_table ATTRIBUTE_UNUSED)
|
|
const
|
|
{
|
|
return false;
|
|
}
|
|
virtual void add_stmt_annotations (graphviz_out *gv ATTRIBUTE_UNUSED,
|
|
const gimple *stmt ATTRIBUTE_UNUSED,
|
|
bool within_row ATTRIBUTE_UNUSED)
|
|
const {}
|
|
virtual bool add_after_node_annotations (graphviz_out *gv ATTRIBUTE_UNUSED,
|
|
const supernode &n ATTRIBUTE_UNUSED)
|
|
const
|
|
{
|
|
return false;
|
|
}
|
|
};
|
|
|
|
extern cgraph_edge *supergraph_call_edge (function *fun, gimple *stmt);
|
|
|
|
} // namespace ana
|
|
|
|
#endif /* GCC_ANALYZER_SUPERGRAPH_H */
|