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