1#ifndef ROSE_BinaryAnalysis_Partitioner2_GraphViz_H
2#define ROSE_BinaryAnalysis_Partitioner2_GraphViz_H
3#include <featureTests.h>
4#ifdef ROSE_ENABLE_BINARY_ANALYSIS
5#include <Rose/BinaryAnalysis/Partitioner2/BasicTypes.h>
7#include <Rose/BinaryAnalysis/NoOperation.h>
8#include <Rose/BinaryAnalysis/Partitioner2/ControlFlowGraph.h>
9#include <Rose/BinaryAnalysis/Partitioner2/FunctionCallGraph.h>
10#include <Rose/BinaryAnalysis/SourceLocations.h>
11#include <Rose/Color.h>
13#include <boost/regex.hpp>
17namespace BinaryAnalysis {
18namespace Partitioner2 {
40ROSE_DLL_API std::string
escape(
const std::string&);
48ROSE_DLL_API std::string
concatenate(
const std::string &oldStuff,
const std::string &newStuff,
const std::string &separator=
"");
53ROSE_DLL_API
bool isId(
const std::string &s);
56ROSE_DLL_API
extern const size_t NO_ID;
70 std::string subgraph_;
79 void select(
bool b=
true) { isSelected_ = b; }
94 const std::string &
name()
const {
return name_; }
95 void name(
const std::string &s) { name_ = s; }
105 static std::string empty =
"\"\"";
106 return label_.empty() ? empty : label_;
108 void label(
const std::string &s) { label_ = s; }
127 const std::string&
subgraph()
const {
return subgraph_; }
128 void subgraph(
const std::string &s) { subgraph_ = s; }
156 typename G::ConstVertexIterator src, dst;
159 PseudoEdge(
const typename G::ConstVertexIterator &src,
const typename G::ConstVertexIterator &dst,
160 const std::string &label)
161 : src(src), dst(dst), label(label) {}
174 std::list<PseudoEdge> pseudoEdges_;
188 : subgraphColor_(0, 0, 0.95) {
195 vertexOrganization_.clear();
196 vertexOrganization_.resize(g.nVertices());
197 edgeOrganization_.clear();
198 edgeOrganization_.resize(g.nEdges());
199 subgraphOrganization_.
clear();
200 pseudoEdges_.
clear();
209 return defaultGraphAttributes_;
212 return defaultGraphAttributes_;
222 return defaultNodeAttributes_;
225 return defaultNodeAttributes_;
235 return defaultEdgeAttributes_;
238 return defaultEdgeAttributes_;
260 return vertexOrganization_;
263 return vertexOrganization_;
266 ASSERT_require(vertexId < vertexOrganization_.size());
267 return vertexOrganization_[vertexId];
270 ASSERT_require(vertexId < vertexOrganization_.size());
271 return vertexOrganization_[vertexId];
298 return edgeOrganization_;
301 return edgeOrganization_;
304 ASSERT_require(edgeId < edgeOrganization_.size());
305 return edgeOrganization_[edgeId];
308 ASSERT_require(edgeId < edgeOrganization_.size());
309 return edgeOrganization_[edgeId];
336 return subgraphOrganization_;
339 return subgraphOrganization_;
360 pseudoEdges_.clear();
392 virtual void emit(std::ostream&)
const;
438 bool useFunctionSubgraphs_;
439 bool showReturnEdges_;
440 bool showInstructions_;
441 bool showInstructionAddresses_;
442 bool showInstructionStackDeltas_;
443 bool showInNeighbors_;
444 bool showOutNeighbors_;
445 bool strikeNoopSequences_;
450 static unsigned long versionDate_;
702 return firstOwningFunction(*v);
730 virtual std::string
sourceLocation(
const ControlFlowGraph::ConstVertexIterator&)
const;
738 virtual std::string
vertexLabel(
const ControlFlowGraph::ConstVertexIterator&)
const;
765 virtual std::string
edgeLabel(
const ControlFlowGraph::ConstEdgeIterator&)
const;
766 std::string
edgeLabel(
const ControlFlowGraph::Edge&)
const;
802 boost::regex highlightNameMatcher_;
806 virtual std::string functionLabel(
const FunctionPtr&)
const;
808 virtual void emitCallGraph(std::ostream &out)
const;
811 virtual void highlight(
const boost::regex&);
830 boost::regex nameMatcher_;
831 typedef std::vector<FunctionPtr> InlinedFunctions;
837 virtual const FunctionCallGraph& callGraph()
const override {
return CgEmitter::callGraph(); }
839 virtual std::string functionLabel(
const FunctionPtr&)
const override;
840 virtual bool shouldInline(
const FunctionPtr&)
const;
896 std::string name = org.
name();
899 out <<name <<
" [ label=" <<org.
label() <<
" ";
908 const VMap &vmap)
const {
909 ASSERT_require2(vmap.
exists(edge->source()->id()),
"edge source vertex has not yet been emitted");
910 ASSERT_require2(vmap.
exists(edge->target()->id()),
"edge target vertex has not yet been emitted");
912 size_t sourceId = edge->source()->id();
913 std::string sourceName = vertexOrganization(sourceId).name();
914 if (sourceName.empty())
917 size_t targetId = edge->target()->id();
918 std::string targetName = vertexOrganization(targetId).name();
919 if (targetName.empty())
922 out <<sourceName <<
" -> " <<targetName <<
" [ label=" <<org.
label() <<
" " <<
toString(org.
attributes()) <<
" ];\n";
930 out <<
"digraph CFG {\n";
931 out <<
" graph [ " <<
toString(defaultGraphAttributes_) <<
" ];\n";
932 out <<
" node [ " <<
toString(defaultNodeAttributes_) <<
" ];\n";
933 out <<
" edge [ " <<
toString(defaultEdgeAttributes_) <<
" ];\n";
935 typedef std::map<std::string , std::string> Subgraphs;
939 for (
typename G::ConstVertexIterator vertex=graph_.vertices().begin(); vertex!=graph_.vertices().end(); ++vertex) {
942 std::ostringstream ss;
943 size_t gvid = emitVertex(ss, vertex, org, vmap);
944 vmap.
insert(vertex->id(), gvid);
945 subgraphs[org.
subgraph()] += ss.str();
950 for (
typename G::ConstEdgeIterator edge=graph_.edges().begin(); edge!=graph_.edges().end(); ++edge) {
953 vertexOrganization(edge->source()).isSelected() && vertexOrganization(edge->target()).isSelected()) {
954 std::ostringstream ss;
955 emitEdge(ss, edge, org, vmap);
956 subgraphs[org.
subgraph()] += ss.str();
961 for (
const Subgraphs::value_type &node: subgraphs) {
962 const std::string &subgraphName = node.first;
963 const std::string &subgraphContent = node.second;
964 if (!subgraphName.empty()) {
965 out <<
"\nsubgraph cluster_" <<subgraphName <<
" {"
966 <<
" label=" <<subgraphOrganization(subgraphName).label() <<
" "
967 <<
toString(subgraphOrganization(subgraphName).attributes()) <<
"\n"
974 Subgraphs::iterator unnamedSubgraph = subgraphs.find(
"");
975 if (unnamedSubgraph != subgraphs.end())
976 out <<unnamedSubgraph->second;
980 if (vertexOrganization(edge.src).isSelected() && vertexOrganization(edge.dst).isSelected()) {
981 std::string sourceName = vertexOrganization(edge.src).name();
982 std::string targetName = vertexOrganization(edge.dst).name();
986 <<
" [ label=" <<
escape(edge.label) <<
" ];\n";
996 for (
const typename G::Vertex &src: graph_.vertices()) {
997 if (vertexOrganization(src).isSelected()) {
998 std::set<size_t> targets;
999 for (
const typename G::Edge &edge: src.outEdges()) {
1000 if (edgeOrganization(edge).isSelected() && !targets.insert(edge.target()->id()).second)
1001 edgeOrganization(edge).select(
false);
Analysis that looks for no-op equivalents.
Function call information.
Base class for generating GraphViz output.
const Organization & vertexOrganization(size_t vertexId) const
Property: Controls which vertices are to appear in the output, and how.
Organization & vertexOrganization(size_t vertexId)
Property: Controls which vertices are to appear in the output, and how.
BaseEmitter(const Graph &g)
Constructor.
const Organization & subgraphOrganization(const std::string &name) const
Property: Controls which subgraphs appear in the output, and how.
const EdgeOrganization & edgeOrganization() const
Property: Controls which edges are to appear in the output, and how.
Attributes & defaultNodeAttributes()
Property: default graph node attributes.
Attributes & defaultGraphAttributes()
Property: default graph attributes.
EdgeOrganization & edgeOrganization()
Property: Controls which edges are to appear in the output, and how.
const SubgraphOrganization & subgraphOrganization() const
Property: Controls which subgraphs appear in the output, and how.
const Organization & edgeOrganization(const typename G::Edge &edge) const
Property: Controls which edges are to appear in the output, and how.
void subgraphColor(const Color::HSV &bg)
Property: color to use for function subgraph background.
SubgraphOrganization & subgraphOrganization()
Property: Controls which subgraphs appear in the output, and how.
const Attributes & defaultGraphAttributes() const
Property: default graph attributes.
void selectAll(bool b=true)
Causes all vertices and edges to be selected.
void selectAllEdges(bool b=true)
Causes all edges to be selected.
const Organization & edgeOrganization(size_t edgeId) const
Property: Controls which edges are to appear in the output, and how.
void selectAllVertices(bool b=true)
Causes all vertices to be selected.
Attributes & defaultEdgeAttributes()
Property: default graph edge attributes.
Organization & edgeOrganization(size_t edgeId)
Property: Controls which edges are to appear in the output, and how.
const Color::HSV & subgraphColor() const
Property: color to use for function subgraph background.
const Attributes & defaultNodeAttributes() const
Property: default graph node attributes.
VertexOrganization & vertexOrganization()
Property: Controls which vertices are to appear in the output, and how.
std::vector< Organization > EdgeOrganization
Organizational information for edges.
void graph(const Graph &g)
Reset the graph.
const Organization & vertexOrganization(const typename G::Vertex &vertex) const
Property: Controls which vertices are to appear in the output, and how.
void deselectParallelEdges()
Deselect all but one parallel edge.
const Organization & vertexOrganization(const typename G::ConstVertexIterator &vertex) const
Property: Controls which vertices are to appear in the output, and how.
std::vector< Organization > VertexOrganization
Organizational information for vertices.
const Attributes & defaultEdgeAttributes() const
Property: default graph edge attributes.
Organization & subgraphOrganization(const std::string &name)
Property: Controls which subgraphs appear in the output, and how.
const Organization & edgeOrganization(const typename G::ConstEdgeIterator &edge) const
Property: Controls which edges are to appear in the output, and how.
Organization & vertexOrganization(const typename G::Vertex &vertex)
Property: Controls which vertices are to appear in the output, and how.
size_t emitVertex(std::ostream &, const typename G::ConstVertexIterator &, const Organization &, const VMap &) const
Emit a single vertex if it hasn't been emitted already.
virtual void emit(std::ostream &) const
Dump selected vertices, edges, and subgraphs.
Organization & vertexOrganization(const typename G::ConstVertexIterator &vertex)
Property: Controls which vertices are to appear in the output, and how.
void emitEdge(std::ostream &, const typename G::ConstEdgeIterator &, const Organization &, const VMap &) const
Emit a single edge.
BaseEmitter()
Default constructor.
Organization & edgeOrganization(const typename G::ConstEdgeIterator &edge)
Property: Controls which edges are to appear in the output, and how.
Organization & edgeOrganization(const typename G::Edge &edge)
Property: Controls which edges are to appear in the output, and how.
void selectNone()
Deselects all vertices and edges.
const VertexOrganization & vertexOrganization() const
Property: Controls which vertices are to appear in the output, and how.
Sawyer::Container::Map< std::string, Organization > SubgraphOrganization
Organizational information for subgraphs.
Creates GraphViz files from Partitioner data.
static FunctionPtr firstOwningFunction(const ControlFlowGraph::ConstVertexIterator &v)
First function that owns a vertex.
virtual Attributes functionAttributes(const FunctionPtr &) const
Attributes for function vertex.
Attributes vertexAttributes(const ControlFlowGraph::Vertex &) const
Attributes for a CFG vertex.
const Color::HSV & warningColor() const
Property: color to use for background of special nodes and for warnings.
bool showInstructionAddresses() const
Property: show instruction addresses.
void warningColor(const Color::HSV &bg)
Property: color to use for background of special nodes and for warnings.
void showInstructions(bool b)
Property: show basic block instructions.
void useFunctionSubgraphs(bool b)
Property: use function subgraphs.
virtual std::string functionLabel(const FunctionPtr &) const
Label for function vertex.
const Color::HSV & funcReturnColor() const
Property: color to use for background of function return nodes.
std::string edgeLabel(const ControlFlowGraph::Edge &) const
Label for CFG edge.
static FunctionSet owningFunctions(const ControlFlowGraph::Vertex &)
Functions that own a vertex.
void srcMapper(const SourceLocations &mapper)
Property: Address-to-source mapping.
void selectFunctionCallees(const FunctionPtr &)
Select outgoing edges to neighboring vertices.
static FunctionSet owningFunctions(const ControlFlowGraph::ConstVertexIterator &)
Functions that own a vertex.
CfgEmitter & selectWholeGraph()
Selects graph elements for whole-graph output.
static bool isInterFunctionEdge(const ControlFlowGraph::Edge &)
Returns true if the edge spans two different functions.
CfgEmitter & selectFunctionGraph(const FunctionPtr &)
Selects the CFG for one function.
CfgEmitter(const PartitionerConstPtr &)
Constructor.
virtual std::string vertexLabel(const ControlFlowGraph::ConstVertexIterator &) const
Label for CFG vertex.
virtual std::string edgeLabel(const ControlFlowGraph::ConstEdgeIterator &) const
Label for CFG edge.
void selectFunctionCallers(const FunctionPtr &)
Select incoming edges from neighboring vertices.
void deselectReturnEdges()
Deselect all function return edges.
std::string vertexLabel(const ControlFlowGraph::Vertex &) const
Label for CFG vertex.
void emitFunctionGraph(std::ostream &, const FunctionPtr &)
Dump control flow graph for one function.
bool showOutNeighbors() const
Property: show outgoing edges to neighbor vertices.
void funcEnterColor(const Color::HSV &bg)
Property: color to use for background of function entrance nodes.
virtual Attributes vertexAttributes(const ControlFlowGraph::ConstVertexIterator &) const
Attributes for a CFG vertex.
bool showInstructions() const
Property: show basic block instructions.
void showOutNeighbors(bool b)
Property: show outgoing edges to neighbor vertices.
void selectInterval(const AddressInterval &)
Selects vertices in some interval.
void showInstructionStackDeltas(bool b)
Property: show instruction stack deltas.
std::string vertexLabelDetailed(const ControlFlowGraph::Vertex &) const
Detailed label for CFG vertex.
virtual Attributes edgeAttributes(const ControlFlowGraph::ConstEdgeIterator &) const
Attributes for a CFG edge.
void assignFunctionSubgraphs()
Assign vertices and edges to subgraphs.
Attributes edgeAttributes(const ControlFlowGraph::Edge &) const
Attributes for a CFG edge.
void funcReturnColor(const Color::HSV &bg)
Property: color to use for background of function return nodes.
bool strikeNoopSequences() const
Property: strike no-op sequences.
SourceLocations & srcMapper()
Property: Address-to-source mapping.
bool useFunctionSubgraphs() const
Property: use function subgraphs.
void selectNeighbors(bool selectInEdges=true, bool selectOutEdges=true)
Select neighboring vertices.
void strikeNoopSequences(bool b)
Property: strike no-op sequences.
static bool isInterFunctionEdge(const ControlFlowGraph::ConstEdgeIterator &)
Returns true if the edge spans two different functions.
virtual std::string vertexLabelDetailed(const ControlFlowGraph::ConstVertexIterator &) const
Detailed label for CFG vertex.
void showReturnEdges(bool b)
Property: show function return edges.
bool showInstructionStackDeltas() const
Property: show instruction stack deltas.
static FunctionPtr firstOwningFunction(const ControlFlowGraph::Vertex &)
First function that owns a vertex.
virtual std::string sourceLocation(const ControlFlowGraph::ConstVertexIterator &) const
Source location for vertex.
PartitionerConstPtr partitioner()
Property: partitioner.
void emitIntervalGraph(std::ostream &, const AddressInterval &)
Dump control flow graph for some address interval.
void selectIntraFunction(const FunctionPtr &)
Select vertices and intra-function edges for one function.
CfgEmitter(const PartitionerConstPtr &, const ControlFlowGraph &)
Constructor.
bool showInNeighbors() const
Property: show incoming edges from neighbor vertices.
void deselectUnusedVertex(ControlFlowGraph::ConstVertexIterator)
Deselect a vertex if it has no selected incident edges.
bool showReturnEdges() const
Property: show function return edges.
void deselectUnusedVertexType(VertexType)
Deselect vertices of specified type if they have no selected incident edges.
void showInstructionAddresses(bool b)
Property: show instruction addresses.
const Color::HSV & funcEnterColor() const
Property: color to use for background of function entrance nodes.
void showInNeighbors(bool b)
Property: show incoming edges from neighbor vertices.
void emitWholeGraph(std::ostream &)
Dump entire control flow graph.
CfgEmitter & selectIntervalGraph(const AddressInterval &interval)
Selects vertices that start within some interval.
const SourceLocations & srcMapper() const
Property: Address-to-source mapping.
Emits a function call graph.
Emits a modified function call graph.
Organizational information.
const std::string & name() const
Name for object.
void subgraph(const std::string &s)
Subgraph for object.
const std::string & label() const
Label for object.
const Attributes & attributes() const
Attributes for object.
Organization()
Default constructor.
void label(const std::string &s)
Label for object.
void name(const std::string &s)
Name for object.
bool isSelected() const
Determines whether an object is selected.
void attributes(const Attributes &a)
Attributes for object.
void select(bool b=true)
Select or deselect object.
const std::string & subgraph() const
Subgraph for object.
Attributes & attributes()
Attributes for object.
Bidirectional mapping between addresses and source locations.
Container associating values with keys.
bool exists(const Key &key) const
Determine if a key exists.
size_t size() const
Number of nodes, keys, or values in this container.
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
Value & insertMaybeDefault(const Key &key)
Conditionally insert a new key with default value.
Map & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
Map & clear()
Remove all nodes.
const Value & getOrDefault(const Key &key) const
Lookup and return a value or a default.
bool assignTo(U &out) const
Conditionally save a value.
ROSE_DLL_API std::string htmlEscape(const std::string &)
Escape characters that need to be escaped within GraphViz HTML literals.
ROSE_DLL_API bool isId(const std::string &s)
Determins if a string is a valid GraphViz ID.
ROSE_DLL_API std::string toString(const Attributes &)
Convert attributes to GraphViz language string.
PositionGraph readPositions(std::istream &)
Constructs graph positions from a file.
Sawyer::Container::Graph< VertexPosition, EdgePosition > PositionGraph
A graph with positioned vertices and edges.
ROSE_DLL_API std::string quotedEscape(const std::string &)
Escape characters that need to be escaped within GraphViz double quoted literals.
ROSE_DLL_API std::string escape(const std::string &)
Escape some value for GraphViz.
ROSE_DLL_API std::string concatenate(const std::string &oldStuff, const std::string &newStuff, const std::string &separator="")
Append a value to an existing string.
Sawyer::Container::Map< std::string, std::string > Attributes
GraphViz attributes.
ROSE_DLL_API const size_t NO_ID
An invalid identification number.
VertexType
Partitioner control flow vertex types.
ROSE_UTIL_API std::string numberToString(long long)
Convert an integer to a string.
Two dimensional display plane coordinate.
double y
Distance from up.
double x
Distance from left.
std::vector< Coordinate > spline
Control points for the edge B-spline.
std::string name
Name of vertex as known to GraphViz.
double width
Horizontal size of vertex.
Coordinate center
Center of vertex in display plane units.
double height
Vertical size of vertex.