1 #ifndef ROSE_BinaryAnalysis_ControlFlow_H
2 #define ROSE_BinaryAnalysis_ControlFlow_H
3 #include <featureTests.h>
4 #ifdef ROSE_ENABLE_BINARY_ANALYSIS
8 #include "SageBuilderAsm.h"
10 #include <boost/foreach.hpp>
11 #include <boost/graph/adjacency_list.hpp>
12 #include <boost/graph/reverse_graph.hpp>
13 #include <boost/graph/depth_first_search.hpp>
14 #include <Sawyer/GraphBoost.h>
20 namespace BinaryAnalysis {
135 : vertex_filter(NULL), edge_filter(NULL)
157 typedef boost::adjacency_list<boost::setS,
159 boost::bidirectionalS,
160 boost::property<boost::vertex_name_t, SgAsmBlock*> >
BlockGraph;
180 typedef boost::adjacency_list<boost::setS,
182 boost::bidirectionalS,
183 boost::property<boost::vertex_name_t, SgAsmInstruction*> >
InsnGraph;
251 return filter && !(*filter)(
this, src, dst);
259 VertexFilter *vertex_filter;
260 EdgeFilter *edge_filter;
289 template<
class ControlFlowGraph>
305 template<
class ControlFlowGraph>
338 template<
class ControlFlowGraph>
341 template<
class ControlFlowGraph>
344 template<
class ControlFlowGraph>
347 template<
class ControlFlowGraph>
353 template<
class BlockCFG,
class InsnCFG>
360 template<
class InsnCFG>
372 template<
class ControlFlowGraph>
375 template<
class ControlFlowGraph>
389 template<
class ControlFlowGraph>
390 ControlFlowGraph
copy(
const ControlFlowGraph &src);
392 template<
class ControlFlowGraph>
393 void copy(
const ControlFlowGraph &src, ControlFlowGraph &dst);
403 std::vector<typename boost::graph_traits<CFG>::vertex_descriptor> vertices;
404 std::vector<typename boost::graph_traits<CFG>::edge_descriptor> edges;
410 void operator()(std::ostream &o,
typename boost::graph_traits<CFG>::vertex_descriptor vertex)
const {}
416 void operator()(std::ostream&,
typename boost::graph_traits<CFG>::edge_descriptor )
const {}
421 template<
typename CFG,
class VertexPropertyWriter,
class EdgePropertyWriter>
422 void write_graphviz(std::ostream&,
const CFG&,
const VertexPropertyWriter&,
const EdgePropertyWriter&);
424 template<
typename CFG>
429 template<
typename CFG,
class VertexPropertyWriter>
430 void write_graphviz(std::ostream &out,
const CFG &cfg,
const VertexPropertyWriter &vpw) {
441 template<
class ControlFlowGraph>
442 struct FlowOrder:
public boost::default_dfs_visitor {
443 typedef typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor
Vertex;
444 typedef std::vector<Vertex> VertexList;
445 typedef std::vector<size_t> ReverseVertexList;
446 VertexList *forward_order;
447 FlowOrder(VertexList *forward_order): forward_order(forward_order) {}
448 void compute(
const ControlFlowGraph &g, Vertex v0, ReverseVertexList *reverse_order);
449 void finish_vertex(Vertex v, ControlFlowGraph g);
454 template<
class ControlFlowGraph>
457 ControlFlow *analyzer;
458 ControlFlowGraph &cfg;
459 typedef typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor
Vertex;
461 BlockVertexMap &bv_map;
462 VertexInserter(ControlFlow *analyzer, ControlFlowGraph &cfg, BlockVertexMap &bv_map)
463 : analyzer(analyzer), cfg(cfg), bv_map(bv_map)
466 void conditionally_add_vertex(
SgAsmBlock *block);
468 void visit(
SgNode *node) {
469 if (isSgAsmFunction(node)) {
473 conditionally_add_vertex(isSgAsmFunction(node)->get_entry_block());
475 conditionally_add_vertex(isSgAsmBlock(node));
513 template<
class ControlFlowGraph>
514 std::vector<typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor>
516 typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
517 std::vector<size_t> *reverse_order=NULL);
521 template<
class ControlFlowGraph>
522 struct ReturnBlocks:
public boost::default_dfs_visitor {
523 typedef typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor Vertex;
524 typedef std::vector<Vertex> Vector;
526 ReturnBlocks(Vector &blocks): blocks(blocks) {}
527 void finish_vertex(Vertex v, ControlFlowGraph g);
538 template<
class ControlFlowGraph>
539 std::vector<typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor>
541 typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start);
551 template<
class V,
class E>
555 typename CFG::ConstVertexValueIterator iter = cfg.
findVertex(vertexId);
562 template<
class V,
class E,
class AstNode>
566 typename CFG::VertexValueIterator iter = cfg.
findVertex(vertexId);
572 template<
class A,
class B,
class C,
class D,
class E,
class F,
class G>
573 typename boost::property_traits<typename boost::property_map<boost::adjacency_list<A, B, C, D, E, F, G>,
574 boost::vertex_name_t>::type>::value_type
575 get_ast_node(
const boost::adjacency_list<A, B, C, D, E, F, G> &cfg,
576 typename boost::graph_traits<boost::adjacency_list<A, B, C, D, E, F, G> >::vertex_descriptor vertex) {
577 return boost::get(boost::vertex_name, cfg, vertex);
581 template<
class A,
class B,
class C,
class D,
class E,
class F,
class G>
583 put_ast_node(boost::adjacency_list<A, B, C, D, E, F, G> &cfg,
584 typename boost::graph_traits<boost::adjacency_list<A, B, C, D, E, F, G> >::vertex_descriptor vertex,
585 typename boost::property_traits<
586 typename boost::property_map<boost::adjacency_list<A, B, C, D, E, F, G>, boost::vertex_name_t>::type
587 >::value_type ast_node) {
588 boost::put(boost::vertex_name, cfg, vertex, ast_node);
595 template<
class ControlFlowGraph>
599 typename boost::graph_traits<ControlFlowGraph>::vertex_iterator vi, vi_end;
600 for (boost::tie(vi, vi_end)=boost::vertices(cfg); vi!=vi_end; ++vi) {
606 const SgAsmIntegerValuePtrList &targets = block->
get_successors();
607 for (SgAsmIntegerValuePtrList::const_iterator ti=targets.begin(); ti!=targets.end(); ++ti)
613 typename boost::graph_traits<ControlFlowGraph>::out_edge_iterator ei, ei_end;
614 for (boost::tie(ei, ei_end)=boost::out_edges(*vi, cfg); ei!=ei_end; ++ei) {
626 template<
class ControlFlowGraph>
630 typename boost::graph_traits<ControlFlowGraph>::vertex_iterator vi, vi_end;
631 for (boost::tie(vi, vi_end)=boost::vertices(cfg); vi!=vi_end; ++vi) {
638 template<
class ControlFlowGraph>
640 ControlFlow::VertexInserter<ControlFlowGraph>::conditionally_add_vertex(
SgAsmBlock *block)
642 if (block && block->
has_instructions() && !analyzer->is_vertex_filtered(block) && !bv_map.exists(block)) {
643 Vertex vertex = boost::add_vertex(cfg);
644 bv_map[block] = vertex;
649 template<
class ControlFlowGraph>
653 typedef typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor Vertex;
654 Vertex NO_VERTEX = boost::graph_traits<ControlFlowGraph>::null_vertex();
656 BlockVertexMap bv_map;
660 VertexInserter<ControlFlowGraph>(
this, cfg, bv_map).traverse(root, preorder);
664 for (
typename BlockVertexMap::iterator bvi=bv_map.begin(); bvi!=bv_map.end(); ++bvi)
665 addrToVertex[bvi->first->get_address()] = bvi->second;
668 BOOST_FOREACH (Vertex sourceVertex, boost::vertices(cfg)) {
671 Vertex targetVertex = addrToVertex.
get_value_or(integerValue->get_absoluteValue(), NO_VERTEX);
672 if (targetVertex!=NO_VERTEX) {
674 assert(targetBlock!=NULL);
676 boost::add_edge(sourceVertex, targetVertex, cfg);
682 template<
class ControlFlowGraph>
689 bool preserve_call_fallthrough_edges =
false;
693 template<
class ControlFlowGraph>
701 SgAsmFunction *src_func = SageInterface::getEnclosingNode<SgAsmFunction>(src,
true);
702 SgAsmBlock *dst_block = SageInterface::getEnclosingNode<SgAsmBlock>(dst,
true);
703 SgAsmFunction *dst_func = SageInterface::getEnclosingNode<SgAsmFunction>(dst_block);
704 if (!src_func || !dst_func || dst_block!=dst_func->
get_entry_block()) {
706 }
else if (src_func!=dst_func) {
711 return parent ? (*parent)(analyzer, src, dst) :
true;
716 T1 edge_filter(parent);
727 template<
class ControlFlowGraph>
731 typedef typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor Vertex;
732 Vertex NO_VERTEX = boost::graph_traits<ControlFlowGraph>::null_vertex();
735 std::vector<Vertex> src_to_dst(boost::num_vertices(src), NO_VERTEX);
737 typename boost::graph_traits<const ControlFlowGraph>::vertex_iterator vi, vi_end;
738 for (boost::tie(vi, vi_end)=boost::vertices(src); vi!=vi_end; ++vi) {
741 src_to_dst[*vi] = boost::add_vertex(dst);
746 typename boost::graph_traits<const ControlFlowGraph>::edge_iterator ei, ei_end;
747 for (boost::tie(ei, ei_end)=boost::edges(src); ei!=ei_end; ++ei) {
748 if (NO_VERTEX!=src_to_dst[boost::source(*ei, src)] && NO_VERTEX!=src_to_dst[boost::target(*ei, src)]) {
752 boost::add_edge(src_to_dst[boost::source(*ei, src)], src_to_dst[boost::target(*ei, src)], dst);
757 template<
class ControlFlowGraph>
761 ControlFlowGraph dst;
766 template<
class BlockCFG,
class InsnCFG>
771 typedef typename boost::graph_traits<const BlockCFG>::vertex_descriptor BlockCFG_Vertex;
772 typedef typename boost::graph_traits<const BlockCFG>::vertex_iterator BlockCFG_VertexIterator;
773 typedef typename boost::graph_traits<const BlockCFG>::edge_iterator BlockCFG_EdgeIterator;
777 typedef typename boost::graph_traits<InsnCFG>::vertex_descriptor InsnCFG_Vertex;
778 typedef std::pair<InsnCFG_Vertex, InsnCFG_Vertex> InsnCFG_VertexPair;
784 BlockCFG_VertexIterator vi, vi_end;
785 for (boost::tie(vi, vi_end)=boost::vertices(cfgb); vi!=vi_end; ++vi) {
788 assert(!insns.empty());
789 InsnCFG_Vertex enter_vertex = boost::graph_traits<InsnCFG>::null_vertex();
790 InsnCFG_Vertex prev_vertex = boost::graph_traits<InsnCFG>::null_vertex();
791 for (SgAsmStatementPtrList::const_iterator ii=insns.begin(); ii!=insns.end(); ++ii) {
794 InsnCFG_Vertex vertex = boost::add_vertex(cfgi);
796 if (ii==insns.begin()) {
797 enter_vertex = vertex;
799 boost::add_edge(prev_vertex, vertex, cfgi);
801 prev_vertex = vertex;
803 assert(prev_vertex!=boost::graph_traits<InsnCFG>::null_vertex());
804 vertex_translation[*vi] = InsnCFG_VertexPair(enter_vertex, prev_vertex);
811 BlockCFG_EdgeIterator ei, ei_end;
812 for (boost::tie(ei, ei_end)=boost::edges(cfgb); ei!=ei_end; ++ei) {
813 InsnCFG_Vertex src_leave_vertex = vertex_translation.
get_one(boost::source(*ei, cfgb)).second;
814 InsnCFG_Vertex dst_enter_vertex = vertex_translation.
get_one(boost::target(*ei, cfgb)).first;
815 assert(src_leave_vertex!=boost::graph_traits<InsnCFG>::null_vertex());
816 assert(dst_enter_vertex!=boost::graph_traits<InsnCFG>::null_vertex());
817 boost::add_edge(src_leave_vertex, dst_enter_vertex, cfgi);
822 template<
class InsnCFG>
826 typedef typename boost::graph_traits<InsnCFG>::vertex_descriptor CFG_Vertex;
827 typedef typename boost::graph_traits<InsnCFG>::vertex_iterator CFG_VertexIterator;
828 typedef typename boost::graph_traits<InsnCFG>::in_edge_iterator CFG_InEdgeIterator;
829 typedef std::pair<CFG_Vertex, CFG_Vertex> CFG_VertexPair;
831 CFG_Vertex NO_VERTEX = boost::graph_traits<InsnCFG>::null_vertex();
837 InsnToVertex insn_to_vertex;
838 std::vector<bool> isret(boost::num_vertices(cfg),
false);
840 CFG_VertexIterator vi, vi_end;
841 for (boost::tie(vi, vi_end)=boost::vertices(cfg); vi!=vi_end; ++vi) {
844 insn_to_vertex[insn] = *vi;
846 if (0==boost::out_degree(*vi, cfg)) {
849 isret[*vi] = x86_ret==insn_x86->get_kind();
856 struct FunctionEntryVertex {
857 const InsnToVertex &insn_to_vertex;
859 FunctionEntryVertex(
const InsnToVertex &insn_to_vertex,
const InstructionMap &imap)
860 : insn_to_vertex(insn_to_vertex), imap(imap) {}
862 SgAsmFunction *func = SageInterface::getEnclosingNode<SgAsmFunction>(insn,
true);
864 CFG_Vertex entry_vertex = insn_to_vertex.get_one(entry_insn);
867 } function_entry_vertex(insn_to_vertex, insns);
870 std::vector<CFG_VertexPair> edges_to_insert, edges_to_erase;
872 CFG_VertexIterator vi, vi_end;
873 for (boost::tie(vi, vi_end)=boost::vertices(cfg); vi!=vi_end; ++vi) {
874 CFG_Vertex returner_vertex = *vi;
875 if (!isret[returner_vertex])
883 std::vector<bool> seen(boost::num_vertices(cfg),
false);
885 worklist.
push(function_entry_vertex(returner_insn));
886 while (!worklist.
empty()) {
887 CFG_Vertex callee_vertex = worklist.
shift();
888 CFG_InEdgeIterator ei, ei_end;
889 for (boost::tie(ei, ei_end)=boost::in_edges(callee_vertex, cfg); ei!=ei_end; ++ei) {
890 CFG_Vertex caller_vertex = boost::source(*ei, cfg);
891 if (!seen[caller_vertex]) {
892 seen[caller_vertex] =
true;
894 SgAsmBlock *caller_block = SageInterface::getEnclosingNode<SgAsmBlock>(caller_insn);
895 assert(caller_block!=NULL);
896 rose_addr_t target_va, returnee_va;
901 CFG_Vertex returnee_vertex = insn_to_vertex.get_value_or(returnee_insn, NO_VERTEX);
902 if (returnee_vertex!=NO_VERTEX) {
903 edges_to_insert.push_back(CFG_VertexPair(returner_vertex, returnee_vertex));
904 edges_to_erase.push_back(CFG_VertexPair(caller_vertex, returnee_vertex));
910 worklist.
push(function_entry_vertex(caller_insn));
919 if (!preserve_call_fallthrough_edges) {
920 for (
size_t i=0; i<edges_to_erase.size(); ++i)
921 boost::remove_edge(edges_to_erase[i].first, edges_to_erase[i].second, cfg);
923 for (
size_t i=0; i<edges_to_insert.size(); ++i)
924 boost::add_edge(edges_to_insert[i].first, edges_to_insert[i].second, cfg);
927 template<
class ControlFlowGraph>
929 ControlFlow::FlowOrder<ControlFlowGraph>::compute(
const ControlFlowGraph &g, Vertex v0,
930 ReverseVertexList *reverse_order) {
931 forward_order->clear();
932 std::vector<boost::default_color_type> colors(boost::num_vertices(g), boost::white_color);
933 boost::depth_first_visit(g, v0, *
this, &(colors[0]));
934 assert(!forward_order->empty());
935 std::reverse(forward_order->begin(), forward_order->end());
937 reverse_order->clear();
938 reverse_order->resize(boost::num_vertices(g),
INVALID_INDEX);
939 for (
size_t i=0; i<forward_order->size(); i++)
940 (*reverse_order)[(*forward_order)[i]] = i;
944 template<
class ControlFlowGraph>
946 ControlFlow::FlowOrder<ControlFlowGraph>::finish_vertex(Vertex v, ControlFlowGraph g) {
947 forward_order->push_back(v);
950 template<
class ControlFlowGraph>
951 std::vector<typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor>
953 typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
954 std::vector<size_t> *reverse_order)
956 std::vector<typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor> forward_order;
957 FlowOrder<ControlFlowGraph>(&forward_order).compute(cfg, start, reverse_order);
958 return forward_order;
961 template<
class ControlFlowGraph>
963 ControlFlow::ReturnBlocks<ControlFlowGraph>::finish_vertex(Vertex v, ControlFlowGraph g)
965 typename boost::graph_traits<ControlFlowGraph>::out_edge_iterator ei, ei_end;
966 boost::tie(ei, ei_end) = boost::out_edges(v, g);
971 template<
class ControlFlowGraph>
972 std::vector<typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor>
974 typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start)
976 typename ReturnBlocks<ControlFlowGraph>::Vector result;
977 ReturnBlocks<ControlFlowGraph> visitor(result);
978 std::vector<boost::default_color_type> colors(boost::num_vertices(cfg), boost::white_color);
979 boost::depth_first_visit(cfg, start, visitor, &(colors[0]));
983 template<
class ControlFlowGraph>
987 ControlFlowGraph cfg;
992 template<
class ControlFlowGraph>
996 ControlFlowGraph cfg;
1001 template<
class ControlFlowGraph>
1005 ControlFlowGraph cfg;
1011 template<
typename CFG,
class VertexPropertyWriter,
class EdgePropertyWriter>
1014 const VertexPropertyWriter &vpw,
const EdgePropertyWriter &epw)
1017 typedef typename boost::graph_traits<CFG>::edge_descriptor CFG_Edge;
1018 typedef typename boost::graph_traits<CFG>::vertex_iterator CFG_VertexIterator;
1019 typedef typename boost::graph_traits<CFG>::out_edge_iterator CFG_OutEdgeIterator;
1024 std::vector<CFG_Edge> interfunc_edges;
1025 CFG_VertexIterator vi, vi_end;
1026 for (boost::tie(vi, vi_end)=boost::vertices(cfg); vi!=vi_end; ++vi) {
1029 f.vertices.push_back(*vi);
1030 CFG_OutEdgeIterator ei, ei_end;
1031 for (boost::tie(ei, ei_end)=boost::out_edges(*vi, cfg); ei!=ei_end; ++ei) {
1033 SgAsmFunction *tgt_func = SageInterface::getEnclosingNode<SgAsmFunction>(tgt_node,
true);
1034 if (tgt_func==func) {
1035 f.edges.push_back(*ei);
1037 interfunc_edges.push_back(*ei);
1043 out <<
"digraph G {\n";
1044 for (
typename Functions::iterator fi=funcs.begin(); fi!=funcs.end(); ++fi) {
1046 if (!f.vertices.empty() || !f.edges.empty()) {
1048 SgAsmFunction *func = SageInterface::getEnclosingNode<SgAsmFunction>(node,
true);
1049 const size_t maxNameSize = 63;
1050 char cluster_name[maxNameSize+1];
1051 snprintf(cluster_name, maxNameSize,
"cluster_F%" PRIx64, func->get_entry_va());
1052 out <<
" subgraph " <<cluster_name <<
" {\n"
1053 <<
" style=filled;\n"
1054 <<
" color=lightgrey;\n"
1056 <<(func->get_name().empty()?std::string(
""):(
" <"+func->get_name()+
">")) <<
"\";\n";
1057 for (
size_t i=0; i<f.vertices.size(); ++i) {
1058 out <<
" " <<f.vertices[i];
1059 vpw(out, f.vertices[i]);
1062 for (
size_t i=0; i<f.edges.size(); ++i) {
1063 out <<
" " <<boost::source(f.edges[i], cfg) <<
"->" <<boost::target(f.edges[i], cfg);
1064 epw(out, f.edges[i]);
1072 for (
size_t i=0; i<interfunc_edges.size(); ++i) {
1073 out <<
" " <<boost::source(interfunc_edges[i], cfg) <<
"->" <<boost::target(interfunc_edges[i], cfg);
1074 epw(out, interfunc_edges[i]);
void set_successors_complete(bool const &)
Property: Whether the successors list is complete.
BlockGraph Graph
Default control flow graph.
Default vertex property writer is a no-op.
void put_ast_node(Sawyer::Container::Graph< V, E > &cfg, size_t vertexId, AstNode *astNode)
Set the AST node associated with a vertex.
void write_graphviz(std::ostream &out, const CFG &cfg)
Write a CFG to a graphviz file, creating a cluster subgraph for each function.
Graph containing user-defined vertices and edges.
ROSE_UTIL_API std::string numberToString(long long)
Convert an integer to a string.
bool is_function_call(rose_addr_t &target_va, rose_addr_t &return_va)
Returns true if basic block appears to be a function call.
Base class for all binary analysis IR nodes.
Class for traversing the AST.
void apply_to_ast(const ControlFlowGraph &)
Applies graph to AST.
Base class for machine instructions.
bool is_vertex_filtered(SgAsmNode *bb_or_insn, VertexFilter *filter)
Determines if a vertex is filtered out.
SgAsmBlock * get_entry_block() const
Function entry basic block.
boost::adjacency_list< boost::setS, boost::vecS, boost::bidirectionalS, boost::property< boost::vertex_name_t, SgAsmInstruction * > > InsnGraph
Default instruction-based control flow graph.
void explode_blocks(const BlockCFG &cfgb, InsnCFG &cfgi)
Create an instruction control flow graph from a basic block control flow graph.
const T & get_value_or(const Key &key, const T &dflt) const
Convenience for getting a value from an Option.
void set_parent(SgNode *parent)
All nodes in the AST contain a reference to a parent node.
List of things to work on.
ControlFlowGraph build_insn_cfg_from_ast(SgNode *root)
Builds a control flow graph for part of an AST.
rose_addr_t const & get_address() const
Property: Starting virtual address.
Represents a synthesized function.
Sawyer::Container::Graph< V, E >::VertexValue get_ast_node(const Sawyer::Container::Graph< V, E > &cfg, size_t vertexId)
Return the AST node associated with a vertex.
ControlFlowGraph build_block_cfg_from_ast(SgNode *root)
Builds a control flow graph for part of an AST.
std::vector< typename boost::graph_traits< ControlFlowGraph >::vertex_descriptor > flow_order(const ControlFlowGraph &, typename boost::graph_traits< ControlFlowGraph >::vertex_descriptor start, std::vector< size_t > *reverse_order=NULL)
Orders nodes by depth first search reverse post order.
void write_graphviz(std::ostream &out, const CFG &cfg, const VertexPropertyWriter &vpw)
Write a CFG to a graphviz file, creating a cluster subgraph for each function.
ControlFlowGraph copy(const ControlFlowGraph &src)
Copies a graph while filtering.
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
Main namespace for the ROSE library.
void fixup_fcall_fret(InsnCFG &cfg, bool preserve_call_fallthrough_edges)
Fix up a CFG by changing function call and return edges.
void clear_ast(SgNode *ast)
Clears successor information from the AST.
T shift()
Remove and return the item from the front of the work list.
rose_addr_t const & get_entry_va() const
Property: Primary entry address.
void set_edge_filter(EdgeFilter *filter)
Manipulate the edge filter.
bool push(const T &, boost::tribool check_uniqueness=boost::logic::indeterminate)
Add an item to the back of the work list.
Base class for integer values.
This class represents the base class for all IR nodes within Sage III.
ROSE_UTIL_API std::string addrToString(uint64_t value, size_t nbits=0)
Convert a virtual address to a string.
bool is_edge_filtered(SgAsmNode *src, SgAsmNode *dst)
Determines if an edge is filtered out.
ControlFlowGraph build_cg_from_ast(SgNode *root)
Builds a control flow graph with only function call edges.
void set_cached_vertex(size_t const &)
Property: Cached vertex for control flow graphs.
void makeRelativeTo(SgNode *baseNode)
Makes the value of this integer relative to some other addressable node.
bool has_instructions() const
Determins if a block contains instructions.
boost::adjacency_list< boost::setS, boost::vecS, boost::bidirectionalS, boost::property< boost::vertex_name_t, SgAsmBlock * > > BlockGraph
Default basic block control flow graph type.
VertexIterator findVertex(size_t id)
Finds the vertex with specified ID number.
VertexFilter * get_vertex_filter() const
Manipulate the vertex filter.
Represents one Intel x86 machine instruction.
Extends std::map with methods that return optional values.
SgAsmStatementPtrList const & get_statementList() const
Property: Statements of which this block is composed.
bool empty() const
Returns true if this work list is empty.
std::vector< typename boost::graph_traits< ControlFlowGraph >::vertex_descriptor > return_blocks(const ControlFlowGraph &cfg, typename boost::graph_traits< ControlFlowGraph >::vertex_descriptor start)
Returns list of function return blocks.
bool is_edge_filtered(SgAsmNode *src, SgAsmNode *dst, EdgeFilter *filter)
Determines if an edge is filtered out.
SgAsmIntegerValuePtrList const & get_successors() const
Property: Control flow successors.
Binary control flow analysis.
void write_graphviz(std::ostream &, const CFG &, const VertexPropertyWriter &, const EdgePropertyWriter &)
Write a CFG to a graphviz file, creating a cluster subgraph for each function.
Default edge property writer is a no-op.
V VertexValue
User-level data associated with vertices.
const T & get_one(const Key &key) const
Look up one value or throw an exception.
bool is_vertex_filtered(SgAsmNode *bb_or_insn)
Determines if a vertex is filtered out.
void cache_vertex_descriptors(const ControlFlowGraph &)
Cache basic block vertex descriptors in AST.
const size_t INVALID_INDEX(static_cast< size_t >(-1))
Invalid array index.
List of vertices and intra-function edges for one function.
EdgeFilter * get_edge_filter() const
Manipulate the edge filter.
void set_vertex_filter(VertexFilter *filter)
Manipulate the vertex filter.