OLD | NEW |
(Empty) | |
| 1 /* Callgraph implementation. |
| 2 Copyright (C) 2011 Free Software Foundation, Inc. |
| 3 Contributed by Sriraman Tallam (tmsriram@google.com). |
| 4 |
| 5 This program is free software; you can redistribute it and/or modify |
| 6 it under the terms of the GNU General Public License as published by |
| 7 the Free Software Foundation; either version 3, or (at your option) |
| 8 any later version. |
| 9 |
| 10 This program is distributed in the hope that it will be useful, but |
| 11 WITHOUT ANY WARRANTY; without even the implied warranty of |
| 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 13 General Public License for more details. |
| 14 |
| 15 You should have received a copy of the GNU General Public License |
| 16 along with this program; see the file COPYING3. If not see |
| 17 <http://www.gnu.org/licenses/>. */ |
| 18 |
| 19 #ifndef CALLGRAPH_H |
| 20 #define CALLGRAPH_H |
| 21 |
| 22 #include <vector> |
| 23 #include <string> |
| 24 #include <map> |
| 25 #include <list> |
| 26 #include <iostream> |
| 27 #include <stdio.h> |
| 28 #include <assert.h> |
| 29 |
| 30 class Node; |
| 31 class Edge; |
| 32 |
| 33 /* Represents a node on the call graph. */ |
| 34 class Node |
| 35 { |
| 36 public: |
| 37 Node (unsigned int id, std::string name) |
| 38 : id_ (id), name_ (name), merge_next_ (NULL), edge_list_ (), |
| 39 last_merge_node_ (this), is_merged_ (false), is_real_node_ (false) |
| 40 { } |
| 41 |
| 42 /* Returns the unique id for this node. */ |
| 43 unsigned int id () const |
| 44 { return this->id_; } |
| 45 |
| 46 /* Name of the function corresponding to this node. */ |
| 47 const std::string& |
| 48 name () const |
| 49 { return this->name_; } |
| 50 |
| 51 /* Add a new edge to the list of edges with this node. */ |
| 52 void add_edge (Edge *edge) |
| 53 { edge_list_.push_back (edge); } |
| 54 |
| 55 /* Returns the list of edges that contain this node. */ |
| 56 std::list<Edge*>& edge_list () |
| 57 { return edge_list_; } |
| 58 |
| 59 /* Returns true if this node has been merged onto an other node. */ |
| 60 bool is_merged () const |
| 61 { return this->is_merged_; } |
| 62 |
| 63 /* Chain the nodes that are merged. Maintain a pointer to the last |
| 64 node in the chain. After merging at the end, the last node in the |
| 65 current chain is the last node in the chain of the merged node. */ |
| 66 void merge_node (Node *mergee) |
| 67 { |
| 68 last_merge_node_->merge_next_ = mergee; |
| 69 last_merge_node_ = mergee->last_merge_node_; |
| 70 mergee->is_merged_ = true; |
| 71 } |
| 72 |
| 73 /* Get the next node in the chain of merged nodes. */ |
| 74 Node *get_merge_next () const |
| 75 { return this->merge_next_; } |
| 76 |
| 77 /* True if the function corresponding to this node can be re-ordered. */ |
| 78 bool is_real_node () const |
| 79 { return this->is_real_node_; } |
| 80 |
| 81 void set_as_real_node () |
| 82 { this->is_real_node_ = true; } |
| 83 |
| 84 private: |
| 85 unsigned int id_; |
| 86 std::string name_; |
| 87 /* Pointer to the next node in the chain of merged nodes. */ |
| 88 Node *merge_next_; |
| 89 /* List of edges with this node. */ |
| 90 std::list<Edge*> edge_list_; |
| 91 /* Pointer to the last node in the chain of merged nodes. */ |
| 92 Node *last_merge_node_; |
| 93 bool is_merged_; |
| 94 bool is_real_node_; |
| 95 }; |
| 96 |
| 97 /* WEAK if one of the nodes is not real. STRONG if both |
| 98 nodes are real. */ |
| 99 typedef enum edge_type_ |
| 100 { |
| 101 WEAK_EDGE, |
| 102 STRONG_EDGE |
| 103 } Edge_type; |
| 104 |
| 105 /* Represents an edge in the call graph. */ |
| 106 class Edge |
| 107 { |
| 108 public: |
| 109 Edge (Node *function_1, |
| 110 Node *function_2, |
| 111 unsigned int weight) |
| 112 : weight_ (weight), next_ (NULL), prev_ (NULL), is_merged_ (false) |
| 113 { |
| 114 this->set_functions (function_1, function_2); |
| 115 function_1->add_edge (this); |
| 116 function_2->add_edge (this); |
| 117 } |
| 118 |
| 119 /* Assigns the two nodes that make up this edge. */ |
| 120 void set_functions (Node *function_1, Node *function_2) |
| 121 { |
| 122 /* No self edges. */ |
| 123 assert (function_1->id () != function_2->id ()); |
| 124 if (function_1->id () < function_2->id ()) |
| 125 { |
| 126 first_function_ = function_1; |
| 127 second_function_ = function_2; |
| 128 } |
| 129 else |
| 130 { |
| 131 first_function_ = function_2; |
| 132 second_function_ = function_1; |
| 133 } |
| 134 } |
| 135 |
| 136 /* The first node that makes up this edge. */ |
| 137 Node *first_function () const |
| 138 { return this->first_function_; } |
| 139 |
| 140 /* The second node that makes up this edge. */ |
| 141 Node *second_function () const |
| 142 { return this->second_function_; } |
| 143 |
| 144 /* Returns the weight of this edge. */ |
| 145 unsigned int weight () const |
| 146 { return this->weight_; } |
| 147 |
| 148 /* Increments the weight of this edge by WEIGHT. */ |
| 149 void add_weight (unsigned int weight) |
| 150 { this->weight_ += weight; } |
| 151 |
| 152 /* Compares the weight of two edges. If the types of the edges are |
| 153 different, then the STRONG_EDGE is always bigger. */ |
| 154 bool operator< (const Edge& edge) |
| 155 { |
| 156 if (this->edge_type () == edge.edge_type ()) |
| 157 return this->weight_ < edge.weight_; |
| 158 |
| 159 if (this->edge_type () == STRONG_EDGE) |
| 160 return false; |
| 161 |
| 162 return true; |
| 163 } |
| 164 |
| 165 /* Gets the next edge in a chain of edges. */ |
| 166 Edge *get_next () const |
| 167 { return this->next_; } |
| 168 |
| 169 /* Sets the next edge in a chain of edges. */ |
| 170 void set_next (Edge *edge) |
| 171 { this->next_ = edge; } |
| 172 |
| 173 /* Gets the previous edge in a chain of edges. */ |
| 174 Edge *get_prev () const |
| 175 { return this->prev_; } |
| 176 |
| 177 /* Sets the previous edge in a chain of edges. */ |
| 178 void set_prev (Edge *edge) |
| 179 { this->prev_ = edge; } |
| 180 |
| 181 /* True is the nodes corresponding to this edge have been merged. */ |
| 182 bool is_merged () const |
| 183 { return this->is_merged_; } |
| 184 |
| 185 /* Set that the nodes corresponding to this edge have been merged. */ |
| 186 void set_merged () |
| 187 { this->is_merged_ = true; } |
| 188 |
| 189 Edge_type edge_type () const |
| 190 { return edge_type_; } |
| 191 |
| 192 /* A WEAK_EDGE has one of its nodes corresponding to a function |
| 193 that cannot be re-ordered. Functions that can be re-ordered |
| 194 are marked as real nodes. */ |
| 195 void |
| 196 set_edge_type () |
| 197 { |
| 198 if (this->first_function_->is_real_node () |
| 199 && this->second_function_->is_real_node ()) |
| 200 this->edge_type_ = STRONG_EDGE; |
| 201 else |
| 202 this->edge_type_ = WEAK_EDGE; |
| 203 } |
| 204 |
| 205 private: |
| 206 |
| 207 Node *first_function_; |
| 208 Node *second_function_; |
| 209 unsigned int weight_; |
| 210 Edge *next_; |
| 211 Edge *prev_; |
| 212 /* True if the nodes corresponding to this edge have been merged. */ |
| 213 bool is_merged_; |
| 214 Edge_type edge_type_; |
| 215 }; |
| 216 |
| 217 |
| 218 /* List of Functions or Nodes. */ |
| 219 typedef std::vector<Node*> Function_list; |
| 220 |
| 221 /* Maps a function name to the id in the Function_list. */ |
| 222 typedef std::map<std::string, unsigned int> Function_map; |
| 223 |
| 224 typedef Edge *Edge_ptr; |
| 225 typedef std::list<Edge*> Edge_list; |
| 226 typedef std::pair<unsigned int, unsigned int> Raw_edge; |
| 227 typedef std::map<Raw_edge, Edge*> Edge_map; |
| 228 |
| 229 typedef std::pair<void*, int> Section_id; |
| 230 typedef std::map<std::string, std::pair<void*, int> > Section_map; |
| 231 |
| 232 void |
| 233 parse_callgraph_section_contents (unsigned char *contents, unsigned int length); |
| 234 |
| 235 /* Maps the section name to its corresponding object handle |
| 236 and the section index. */ |
| 237 void |
| 238 map_section_name_to_index (char *name, void *handle, int shndx); |
| 239 |
| 240 void |
| 241 dump_functions (); |
| 242 |
| 243 void |
| 244 dump_edges (); |
| 245 |
| 246 void |
| 247 find_pettis_hansen_function_layout (); |
| 248 |
| 249 unsigned int |
| 250 get_layout (const char *out_filename, void ***handles, unsigned int **shndx); |
| 251 |
| 252 #endif |
OLD | NEW |