1 //======================================================================= 2 // Copyright (C) 2005-2009 Jongsoo Park <jongsoo.park -at- gmail.com> 3 // 4 // Distributed under the Boost Software License, Version 1.0. 5 // (See accompanying file LICENSE_1_0.txt or copy at 6 // http://www.boost.org/LICENSE_1_0.txt) 7 //======================================================================= 8 9 #ifndef BOOST_GRAPH_DOMINATOR_HPP 10 #define BOOST_GRAPH_DOMINATOR_HPP 11 12 #include <boost/config.hpp> 13 #include <deque> 14 #include <set> 15 #include <boost/graph/depth_first_search.hpp> 16 #include <boost/concept/assert.hpp> 17 18 // Dominator tree computation 19 20 namespace boost { 21 namespace detail { 22 /** 23 * An extended time_stamper which also records vertices for each dfs number 24 */ 25 template<class TimeMap, class VertexVector, class TimeT, class Tag> 26 class time_stamper_with_vertex_vector 27 : public base_visitor< 28 time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, Tag> > 29 { 30 public : 31 typedef Tag event_filter; time_stamper_with_vertex_vector(TimeMap timeMap,VertexVector & v,TimeT & t)32 time_stamper_with_vertex_vector(TimeMap timeMap, VertexVector& v, 33 TimeT& t) 34 : timeStamper_(timeMap, t), v_(v) { } 35 36 template<class Graph> 37 void operator ()(const typename property_traits<TimeMap>::key_type & v,const Graph & g)38 operator()(const typename property_traits<TimeMap>::key_type& v, 39 const Graph& g) 40 { 41 timeStamper_(v, g); 42 v_[timeStamper_.m_time] = v; 43 } 44 45 private : 46 time_stamper<TimeMap, TimeT, Tag> timeStamper_; 47 VertexVector& v_; 48 }; 49 50 /** 51 * A convenient way to create a time_stamper_with_vertex_vector 52 */ 53 template<class TimeMap, class VertexVector, class TimeT, class Tag> 54 time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, Tag> stamp_times_with_vertex_vector(TimeMap timeMap,VertexVector & v,TimeT & t,Tag)55 stamp_times_with_vertex_vector(TimeMap timeMap, VertexVector& v, TimeT& t, 56 Tag) 57 { 58 return time_stamper_with_vertex_vector<TimeMap, VertexVector, TimeT, 59 Tag>(timeMap, v, t); 60 } 61 62 template<class Graph, class IndexMap, class TimeMap, class PredMap, 63 class DomTreePredMap> 64 class dominator_visitor 65 { 66 typedef typename graph_traits<Graph>::vertex_descriptor Vertex; 67 typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType; 68 69 public : 70 /** 71 * @param g [in] the target graph of the dominator tree 72 * @param entry [in] the entry node of g 73 * @param domTreePredMap [out] the immediate dominator map 74 * (parent map in dominator tree) 75 */ dominator_visitor(const Graph & g,const Vertex & entry,DomTreePredMap domTreePredMap)76 dominator_visitor(const Graph& g, const Vertex& entry, 77 DomTreePredMap domTreePredMap) 78 : semi_(num_vertices(g)), 79 ancestor_(num_vertices(g), graph_traits<Graph>::null_vertex()), 80 samedom_(ancestor_), 81 best_(semi_), 82 semiMap_(make_iterator_property_map(semi_.begin(), 83 get(vertex_index, g))), 84 ancestorMap_(make_iterator_property_map(ancestor_.begin(), 85 get(vertex_index, g))), 86 bestMap_(make_iterator_property_map(best_.begin(), 87 get(vertex_index, g))), 88 buckets_(num_vertices(g)), 89 bucketMap_(make_iterator_property_map(buckets_.begin(), 90 get(vertex_index, g))), 91 entry_(entry), 92 domTreePredMap_(domTreePredMap), 93 numOfVertices_(num_vertices(g)), 94 samedomMap(make_iterator_property_map(samedom_.begin(), 95 get(vertex_index, g))) 96 { 97 } 98 99 void operator ()(const Vertex & n,const TimeMap & dfnumMap,const PredMap & parentMap,const Graph & g)100 operator()(const Vertex& n, const TimeMap& dfnumMap, 101 const PredMap& parentMap, const Graph& g) 102 { 103 if (n == entry_) return; 104 105 const Vertex p(get(parentMap, n)); 106 Vertex s(p); 107 108 // 1. Calculate the semidominator of n, 109 // based on the semidominator thm. 110 // * Semidominator thm. : To find the semidominator of a node n, 111 // consider all predecessors v of n in the CFG (Control Flow Graph). 112 // - If v is a proper ancestor of n in the spanning tree 113 // (so dfnum(v) < dfnum(n)), then v is a candidate for semi(n) 114 // - If v is a non-ancestor of n (so dfnum(v) > dfnum(n)) 115 // then for each u that is an ancestor of v (or u = v), 116 // Let semi(u) be a candidate for semi(n) 117 // of all these candidates, the one with lowest dfnum is 118 // the semidominator of n. 119 120 // For each predecessor of n 121 typename graph_traits<Graph>::in_edge_iterator inItr, inEnd; 122 for (boost::tie(inItr, inEnd) = in_edges(n, g); inItr != inEnd; ++inItr) 123 { 124 const Vertex v = source(*inItr, g); 125 // To deal with unreachable nodes 126 if (get(dfnumMap, v) < 0 || get(dfnumMap, v) >= numOfVertices_) 127 continue; 128 129 Vertex s2; 130 if (get(dfnumMap, v) <= get(dfnumMap, n)) 131 s2 = v; 132 else 133 s2 = get(semiMap_, ancestor_with_lowest_semi_(v, dfnumMap)); 134 135 if (get(dfnumMap, s2) < get(dfnumMap, s)) 136 s = s2; 137 } 138 put(semiMap_, n, s); 139 140 // 2. Calculation of n's dominator is deferred until 141 // the path from s to n has been linked into the forest 142 get(bucketMap_, s).push_back(n); 143 get(ancestorMap_, n) = p; 144 get(bestMap_, n) = n; 145 146 // 3. Now that the path from p to v has been linked into 147 // the spanning forest, these lines calculate the dominator of v, 148 // based on the dominator thm., or else defer the calculation 149 // until y's dominator is known 150 // * Dominator thm. : On the spanning-tree path below semi(n) and 151 // above or including n, let y be the node 152 // with the smallest-numbered semidominator. Then, 153 // 154 // idom(n) = semi(n) if semi(y)=semi(n) or 155 // idom(y) if semi(y) != semi(n) 156 typename std::deque<Vertex>::iterator buckItr; 157 for (buckItr = get(bucketMap_, p).begin(); 158 buckItr != get(bucketMap_, p).end(); 159 ++buckItr) 160 { 161 const Vertex v(*buckItr); 162 const Vertex y(ancestor_with_lowest_semi_(v, dfnumMap)); 163 if (get(semiMap_, y) == get(semiMap_, v)) 164 put(domTreePredMap_, v, p); 165 else 166 put(samedomMap, v, y); 167 } 168 169 get(bucketMap_, p).clear(); 170 } 171 172 protected : 173 174 /** 175 * Evaluate function in Tarjan's path compression 176 */ 177 const Vertex ancestor_with_lowest_semi_(const Vertex & v,const TimeMap & dfnumMap)178 ancestor_with_lowest_semi_(const Vertex& v, const TimeMap& dfnumMap) 179 { 180 const Vertex a(get(ancestorMap_, v)); 181 182 if (get(ancestorMap_, a) != graph_traits<Graph>::null_vertex()) 183 { 184 const Vertex b(ancestor_with_lowest_semi_(a, dfnumMap)); 185 186 put(ancestorMap_, v, get(ancestorMap_, a)); 187 188 if (get(dfnumMap, get(semiMap_, b)) < 189 get(dfnumMap, get(semiMap_, get(bestMap_, v)))) 190 put(bestMap_, v, b); 191 } 192 193 return get(bestMap_, v); 194 } 195 196 std::vector<Vertex> semi_, ancestor_, samedom_, best_; 197 PredMap semiMap_, ancestorMap_, bestMap_; 198 std::vector< std::deque<Vertex> > buckets_; 199 200 iterator_property_map<typename std::vector<std::deque<Vertex> >::iterator, 201 IndexMap> bucketMap_; 202 203 const Vertex& entry_; 204 DomTreePredMap domTreePredMap_; 205 const VerticesSizeType numOfVertices_; 206 207 public : 208 209 PredMap samedomMap; 210 }; 211 212 } // namespace detail 213 214 /** 215 * @brief Build dominator tree using Lengauer-Tarjan algorithm. 216 * It takes O((V+E)log(V+E)) time. 217 * 218 * @pre dfnumMap, parentMap and verticesByDFNum have dfs results corresponding 219 * indexMap. 220 * If dfs has already run before, 221 * this function would be good for saving computations. 222 * @pre Unreachable nodes must be masked as 223 * graph_traits<Graph>::null_vertex in parentMap. 224 * @pre Unreachable nodes must be masked as 225 * (std::numeric_limits<VerticesSizeType>::max)() in dfnumMap. 226 * 227 * @param domTreePredMap [out] : immediate dominator map (parent map 228 * in dom. tree) 229 * 230 * @note reference Appel. p. 452~453. algorithm 19.9, 19.10. 231 * 232 * @todo : Optimization in Finding Dominators in Practice, Loukas Georgiadis 233 */ 234 template<class Graph, class IndexMap, class TimeMap, class PredMap, 235 class VertexVector, class DomTreePredMap> 236 void lengauer_tarjan_dominator_tree_without_dfs(const Graph & g,const typename graph_traits<Graph>::vertex_descriptor & entry,const IndexMap &,TimeMap dfnumMap,PredMap parentMap,VertexVector & verticesByDFNum,DomTreePredMap domTreePredMap)237 lengauer_tarjan_dominator_tree_without_dfs 238 (const Graph& g, 239 const typename graph_traits<Graph>::vertex_descriptor& entry, 240 const IndexMap& /*indexMap*/, 241 TimeMap dfnumMap, PredMap parentMap, VertexVector& verticesByDFNum, 242 DomTreePredMap domTreePredMap) 243 { 244 // Typedefs and concept check 245 typedef typename graph_traits<Graph>::vertex_descriptor Vertex; 246 typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType; 247 248 BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph> )); 249 250 const VerticesSizeType numOfVertices = num_vertices(g); 251 if (numOfVertices == 0) return; 252 253 // 1. Visit each vertex in reverse post order and calculate sdom. 254 detail::dominator_visitor<Graph, IndexMap, TimeMap, PredMap, DomTreePredMap> 255 visitor(g, entry, domTreePredMap); 256 257 VerticesSizeType i; 258 for (i = 0; i < numOfVertices; ++i) 259 { 260 const Vertex u(verticesByDFNum[numOfVertices - 1 - i]); 261 if (u != graph_traits<Graph>::null_vertex()) 262 visitor(u, dfnumMap, parentMap, g); 263 } 264 265 // 2. Now all the deferred dominator calculations, 266 // based on the second clause of the dominator thm., are performed 267 for (i = 0; i < numOfVertices; ++i) 268 { 269 const Vertex n(verticesByDFNum[i]); 270 271 if (n == entry || n == graph_traits<Graph>::null_vertex()) 272 continue; 273 274 Vertex u = get(visitor.samedomMap, n); 275 if (u != graph_traits<Graph>::null_vertex()) 276 { 277 put(domTreePredMap, n, get(domTreePredMap, u)); 278 } 279 } 280 } 281 282 /** 283 * Unlike lengauer_tarjan_dominator_tree_without_dfs, 284 * dfs is run in this function and 285 * the result is written to dfnumMap, parentMap, vertices. 286 * 287 * If the result of dfs required after this algorithm, 288 * this function can eliminate the need of rerunning dfs. 289 */ 290 template<class Graph, class IndexMap, class TimeMap, class PredMap, 291 class VertexVector, class DomTreePredMap> 292 void lengauer_tarjan_dominator_tree(const Graph & g,const typename graph_traits<Graph>::vertex_descriptor & entry,const IndexMap & indexMap,TimeMap dfnumMap,PredMap parentMap,VertexVector & verticesByDFNum,DomTreePredMap domTreePredMap)293 lengauer_tarjan_dominator_tree 294 (const Graph& g, 295 const typename graph_traits<Graph>::vertex_descriptor& entry, 296 const IndexMap& indexMap, 297 TimeMap dfnumMap, PredMap parentMap, VertexVector& verticesByDFNum, 298 DomTreePredMap domTreePredMap) 299 { 300 // Typedefs and concept check 301 typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType; 302 303 BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph> )); 304 305 // 1. Depth first visit 306 const VerticesSizeType numOfVertices = num_vertices(g); 307 if (numOfVertices == 0) return; 308 309 VerticesSizeType time = 310 (std::numeric_limits<VerticesSizeType>::max)(); 311 std::vector<default_color_type> 312 colors(numOfVertices, color_traits<default_color_type>::white()); 313 depth_first_visit 314 (g, entry, 315 make_dfs_visitor 316 (make_pair(record_predecessors(parentMap, on_tree_edge()), 317 detail::stamp_times_with_vertex_vector 318 (dfnumMap, verticesByDFNum, time, on_discover_vertex()))), 319 make_iterator_property_map(colors.begin(), indexMap)); 320 321 // 2. Run main algorithm. 322 lengauer_tarjan_dominator_tree_without_dfs(g, entry, indexMap, dfnumMap, 323 parentMap, verticesByDFNum, 324 domTreePredMap); 325 } 326 327 /** 328 * Use vertex_index as IndexMap and make dfnumMap, parentMap, verticesByDFNum 329 * internally. 330 * If we don't need the result of dfs (dfnumMap, parentMap, verticesByDFNum), 331 * this function would be more convenient one. 332 */ 333 template<class Graph, class DomTreePredMap> 334 void lengauer_tarjan_dominator_tree(const Graph & g,const typename graph_traits<Graph>::vertex_descriptor & entry,DomTreePredMap domTreePredMap)335 lengauer_tarjan_dominator_tree 336 (const Graph& g, 337 const typename graph_traits<Graph>::vertex_descriptor& entry, 338 DomTreePredMap domTreePredMap) 339 { 340 // typedefs 341 typedef typename graph_traits<Graph>::vertex_descriptor Vertex; 342 typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType; 343 typedef typename property_map<Graph, vertex_index_t>::const_type IndexMap; 344 typedef 345 iterator_property_map<typename std::vector<VerticesSizeType>::iterator, 346 IndexMap> TimeMap; 347 typedef 348 iterator_property_map<typename std::vector<Vertex>::iterator, IndexMap> 349 PredMap; 350 351 // Make property maps 352 const VerticesSizeType numOfVertices = num_vertices(g); 353 if (numOfVertices == 0) return; 354 355 const IndexMap indexMap = get(vertex_index, g); 356 357 std::vector<VerticesSizeType> dfnum(numOfVertices, 0); 358 TimeMap dfnumMap(make_iterator_property_map(dfnum.begin(), indexMap)); 359 360 std::vector<Vertex> parent(numOfVertices, 361 graph_traits<Graph>::null_vertex()); 362 PredMap parentMap(make_iterator_property_map(parent.begin(), indexMap)); 363 364 std::vector<Vertex> verticesByDFNum(parent); 365 366 // Run main algorithm 367 lengauer_tarjan_dominator_tree(g, entry, 368 indexMap, dfnumMap, parentMap, 369 verticesByDFNum, domTreePredMap); 370 } 371 372 /** 373 * Muchnick. p. 182, 184 374 * 375 * using iterative bit vector analysis 376 */ 377 template<class Graph, class IndexMap, class DomTreePredMap> 378 void iterative_bit_vector_dominator_tree(const Graph & g,const typename graph_traits<Graph>::vertex_descriptor & entry,const IndexMap & indexMap,DomTreePredMap domTreePredMap)379 iterative_bit_vector_dominator_tree 380 (const Graph& g, 381 const typename graph_traits<Graph>::vertex_descriptor& entry, 382 const IndexMap& indexMap, 383 DomTreePredMap domTreePredMap) 384 { 385 typedef typename graph_traits<Graph>::vertex_descriptor Vertex; 386 typedef typename graph_traits<Graph>::vertex_iterator vertexItr; 387 typedef typename graph_traits<Graph>::vertices_size_type VerticesSizeType; 388 typedef 389 iterator_property_map<typename std::vector< std::set<Vertex> >::iterator, 390 IndexMap> vertexSetMap; 391 392 BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph> )); 393 394 // 1. Finding dominator 395 // 1.1. Initialize 396 const VerticesSizeType numOfVertices = num_vertices(g); 397 if (numOfVertices == 0) return; 398 399 vertexItr vi, viend; 400 boost::tie(vi, viend) = vertices(g); 401 const std::set<Vertex> N(vi, viend); 402 403 bool change = true; 404 405 std::vector< std::set<Vertex> > dom(numOfVertices, N); 406 vertexSetMap domMap(make_iterator_property_map(dom.begin(), indexMap)); 407 get(domMap, entry).clear(); 408 get(domMap, entry).insert(entry); 409 410 while (change) 411 { 412 change = false; 413 for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi) 414 { 415 if (*vi == entry) continue; 416 417 std::set<Vertex> T(N); 418 419 typename graph_traits<Graph>::in_edge_iterator inItr, inEnd; 420 for (boost::tie(inItr, inEnd) = in_edges(*vi, g); inItr != inEnd; ++inItr) 421 { 422 const Vertex p = source(*inItr, g); 423 424 std::set<Vertex> tempSet; 425 std::set_intersection(T.begin(), T.end(), 426 get(domMap, p).begin(), 427 get(domMap, p).end(), 428 std::inserter(tempSet, tempSet.begin())); 429 T.swap(tempSet); 430 } 431 432 T.insert(*vi); 433 if (T != get(domMap, *vi)) 434 { 435 change = true; 436 get(domMap, *vi).swap(T); 437 } 438 } // end of for (boost::tie(vi, viend) = vertices(g) 439 } // end of while(change) 440 441 // 2. Build dominator tree 442 for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi) 443 get(domMap, *vi).erase(*vi); 444 445 Graph domTree(numOfVertices); 446 447 for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi) 448 { 449 if (*vi == entry) continue; 450 451 // We have to iterate through copied dominator set 452 const std::set<Vertex> tempSet(get(domMap, *vi)); 453 typename std::set<Vertex>::const_iterator s; 454 for (s = tempSet.begin(); s != tempSet.end(); ++s) 455 { 456 typename std::set<Vertex>::iterator t; 457 for (t = get(domMap, *vi).begin(); t != get(domMap, *vi).end(); ) 458 { 459 typename std::set<Vertex>::iterator old_t = t; 460 ++t; // Done early because t may become invalid 461 if (*old_t == *s) continue; 462 if (get(domMap, *s).find(*old_t) != get(domMap, *s).end()) 463 get(domMap, *vi).erase(old_t); 464 } 465 } 466 } 467 468 for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi) 469 { 470 if (*vi != entry && get(domMap, *vi).size() == 1) 471 { 472 Vertex temp = *get(domMap, *vi).begin(); 473 put(domTreePredMap, *vi, temp); 474 } 475 } 476 } 477 478 template<class Graph, class DomTreePredMap> 479 void iterative_bit_vector_dominator_tree(const Graph & g,const typename graph_traits<Graph>::vertex_descriptor & entry,DomTreePredMap domTreePredMap)480 iterative_bit_vector_dominator_tree 481 (const Graph& g, 482 const typename graph_traits<Graph>::vertex_descriptor& entry, 483 DomTreePredMap domTreePredMap) 484 { 485 typename property_map<Graph, vertex_index_t>::const_type 486 indexMap = get(vertex_index, g); 487 488 iterative_bit_vector_dominator_tree(g, entry, indexMap, domTreePredMap); 489 } 490 } // namespace boost 491 492 #endif // BOOST_GRAPH_DOMINATOR_HPP 493