1 | /* |
2 | * Copyright (c) 2015-2017, Intel Corporation |
3 | * |
4 | * Redistribution and use in source and binary forms, with or without |
5 | * modification, are permitted provided that the following conditions are met: |
6 | * |
7 | * * Redistributions of source code must retain the above copyright notice, |
8 | * this list of conditions and the following disclaimer. |
9 | * * Redistributions in binary form must reproduce the above copyright |
10 | * notice, this list of conditions and the following disclaimer in the |
11 | * documentation and/or other materials provided with the distribution. |
12 | * * Neither the name of Intel Corporation nor the names of its contributors |
13 | * may be used to endorse or promote products derived from this software |
14 | * without specific prior written permission. |
15 | * |
16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE |
20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
26 | * POSSIBILITY OF SUCH DAMAGE. |
27 | */ |
28 | |
29 | /** \file |
30 | * \brief Region analysis. |
31 | * |
32 | * Definition: a \a region is a subset of vertices in a graph such that: |
33 | * - the edges entering the region are a cutset of the graph |
34 | * - for every in-edge (u, v) to the region there exist edges (u, w) for all |
35 | * w in {w : w in region and w has an in-edge} |
36 | * - the regions in a graph partition the graph |
37 | * |
38 | * Note: |
39 | * - we partition a graph into the maximal number of regions |
40 | * - similar properties for exit edges should hold as a consequence |
41 | * - graph == sequence of regions |
42 | * - a region is considered to have an epsilon vertex to allow jumps |
43 | * - vertices which only lead to back edges need to be floated up in the topo |
44 | * order |
45 | * |
46 | * Algorithm overview: |
47 | * -# topo-order over the DAG skeleton; |
48 | * -# incrementally add vertices to the current region until the boundary edges |
49 | * form a valid cut-set; |
50 | * -# for each back-edge, if the source and target are in different regions, |
51 | * merge the regions (and all intervening regions) into a common region. |
52 | */ |
53 | #include "ng_region.h" |
54 | |
55 | #include "ng_holder.h" |
56 | #include "ng_util.h" |
57 | #include "ue2common.h" |
58 | #include "util/container.h" |
59 | #include "util/flat_containers.h" |
60 | #include "util/graph_range.h" |
61 | #include "util/graph_small_color_map.h" |
62 | |
63 | #include <set> |
64 | #include <utility> |
65 | #include <vector> |
66 | |
67 | #include <boost/graph/filtered_graph.hpp> |
68 | #include <boost/graph/topological_sort.hpp> |
69 | |
70 | using namespace std; |
71 | |
72 | namespace ue2 { |
73 | |
74 | using BackEdgeSet = unordered_set<NFAEdge>; |
75 | using AcyclicGraph = |
76 | boost::filtered_graph<NGHolder, bad_edge_filter<BackEdgeSet>>; |
77 | |
78 | namespace { |
79 | struct exit_info { |
80 | explicit exit_info(NFAVertex v) : exit(v) {} |
81 | |
82 | NFAVertex exit; |
83 | flat_set<NFAVertex> open; |
84 | }; |
85 | } |
86 | |
87 | static |
88 | void checkAndAddExitCandidate(const AcyclicGraph &g, |
89 | const unordered_set<NFAVertex> &r, NFAVertex v, |
90 | vector<exit_info> &exits) { |
91 | exit_info v_exit(v); |
92 | auto &open = v_exit.open; |
93 | |
94 | /* find the set of vertices reachable from v which are not in r */ |
95 | for (auto w : adjacent_vertices_range(v, g)) { |
96 | if (!contains(r, w)) { |
97 | open.insert(w); |
98 | } |
99 | } |
100 | |
101 | if (!open.empty()) { |
102 | DEBUG_PRINTF("exit %zu\n" , g[v].index); |
103 | exits.push_back(move(v_exit)); |
104 | } |
105 | } |
106 | |
107 | static |
108 | void findExits(const AcyclicGraph &g, const unordered_set<NFAVertex> &r, |
109 | vector<exit_info> &exits) { |
110 | exits.clear(); |
111 | for (auto v : r) { |
112 | checkAndAddExitCandidate(g, r, v, exits); |
113 | } |
114 | } |
115 | |
116 | static |
117 | void refineExits(const AcyclicGraph &g, const unordered_set<NFAVertex> &r, |
118 | NFAVertex new_v, vector<exit_info> &exits) { |
119 | /* new_v is no long an open edge */ |
120 | for (auto &exit : exits) { |
121 | exit.open.erase(new_v); |
122 | } |
123 | |
124 | /* no open edges: no longer an exit */ |
125 | exits.erase(remove_if(exits.begin(), exits.end(), |
126 | [&](const exit_info &exit) { return exit.open.empty(); }), |
127 | exits.end()); |
128 | |
129 | checkAndAddExitCandidate(g, r, new_v, exits); |
130 | } |
131 | |
132 | /** the set of exits from a candidate region are valid if: FIXME: document |
133 | */ |
134 | static |
135 | bool exitValid(UNUSED const AcyclicGraph &g, const vector<exit_info> &exits, |
136 | const flat_set<NFAVertex> &open_jumps) { |
137 | if (exits.empty() || (exits.size() < 2 && open_jumps.empty())) { |
138 | return true; |
139 | } |
140 | if (exits.size() == 1 && open_jumps.size() == 1) { |
141 | DEBUG_PRINTF("oj %zu, e %zu\n" , g[*open_jumps.begin()].index, |
142 | g[exits[0].exit].index); |
143 | if (*open_jumps.begin() == exits[0].exit) { |
144 | return true; |
145 | } |
146 | } |
147 | |
148 | assert(!exits.empty()); |
149 | const auto &enters = exits.front().open; |
150 | |
151 | if (!open_jumps.empty() && enters != open_jumps) { |
152 | return false; |
153 | } |
154 | |
155 | for (auto it = begin(exits) + 1; it != end(exits); ++it) { |
156 | if (it->open != enters) { |
157 | return false; |
158 | } |
159 | } |
160 | |
161 | return true; |
162 | } |
163 | |
164 | static |
165 | void setRegion(const unordered_set<NFAVertex> &r, u32 rid, |
166 | unordered_map<NFAVertex, u32> ®ions) { |
167 | for (auto v : r) { |
168 | regions[v] = rid; |
169 | } |
170 | } |
171 | |
172 | static |
173 | void buildInitialCandidate(const AcyclicGraph &g, |
174 | vector<NFAVertex>::const_reverse_iterator &it, |
175 | const vector<NFAVertex>::const_reverse_iterator &ite, |
176 | unordered_set<NFAVertex> &candidate, |
177 | /* in exits of prev region; |
178 | * out exits from candidate */ |
179 | vector<exit_info> &exits, |
180 | flat_set<NFAVertex> &open_jumps) { |
181 | if (it == ite) { |
182 | candidate.clear(); |
183 | exits.clear(); |
184 | return; |
185 | } |
186 | |
187 | if (exits.empty()) { |
188 | DEBUG_PRINTF("odd\n" ); |
189 | candidate.clear(); |
190 | DEBUG_PRINTF("adding %zu to initial\n" , g[*it].index); |
191 | candidate.insert(*it); |
192 | open_jumps.erase(*it); |
193 | checkAndAddExitCandidate(g, candidate, *it, exits); |
194 | ++it; |
195 | return; |
196 | } |
197 | |
198 | // Note: findExits() will clear exits, so it's safe to mutate/move its |
199 | // elements here. |
200 | auto &enters = exits.front().open; |
201 | candidate.clear(); |
202 | |
203 | for (; it != ite; ++it) { |
204 | DEBUG_PRINTF("adding %zu to initial\n" , g[*it].index); |
205 | candidate.insert(*it); |
206 | if (contains(enters, *it)) { |
207 | break; |
208 | } |
209 | } |
210 | |
211 | if (it != ite) { |
212 | enters.erase(*it); |
213 | open_jumps = move(enters); |
214 | DEBUG_PRINTF("oj size = %zu\n" , open_jumps.size()); |
215 | ++it; |
216 | } else { |
217 | open_jumps.clear(); |
218 | } |
219 | |
220 | findExits(g, candidate, exits); |
221 | } |
222 | |
223 | static |
224 | void findDagLeaders(const NGHolder &h, const AcyclicGraph &g, |
225 | const vector<NFAVertex> &topo, |
226 | unordered_map<NFAVertex, u32> ®ions) { |
227 | assert(!topo.empty()); |
228 | u32 curr_id = 0; |
229 | auto t_it = topo.rbegin(); |
230 | unordered_set<NFAVertex> candidate; |
231 | flat_set<NFAVertex> open_jumps; |
232 | DEBUG_PRINTF("adding %zu to current\n" , g[*t_it].index); |
233 | assert(t_it != topo.rend()); |
234 | candidate.insert(*t_it++); |
235 | DEBUG_PRINTF("adding %zu to current\n" , g[*t_it].index); |
236 | assert(t_it != topo.rend()); |
237 | candidate.insert(*t_it++); |
238 | |
239 | vector<exit_info> exits; |
240 | findExits(g, candidate, exits); |
241 | |
242 | while (t_it != topo.rend()) { |
243 | assert(!candidate.empty()); |
244 | |
245 | if (exitValid(g, exits, open_jumps)) { |
246 | if (contains(candidate, h.accept) && !open_jumps.empty()) { |
247 | /* we have tried to make an optional region containing accept as |
248 | * we have an open jump to eod. This candidate region needs to |
249 | * be put in with the previous region. */ |
250 | curr_id--; |
251 | DEBUG_PRINTF("merging in with region %u\n" , curr_id); |
252 | } else { |
253 | DEBUG_PRINTF("setting region %u\n" , curr_id); |
254 | } |
255 | setRegion(candidate, curr_id++, regions); |
256 | buildInitialCandidate(g, t_it, topo.rend(), candidate, exits, |
257 | open_jumps); |
258 | } else { |
259 | NFAVertex curr = *t_it; |
260 | DEBUG_PRINTF("adding %zu to current\n" , g[curr].index); |
261 | candidate.insert(curr); |
262 | open_jumps.erase(curr); |
263 | refineExits(g, candidate, *t_it, exits); |
264 | DEBUG_PRINTF(" open jumps %zu exits %zu\n" , open_jumps.size(), |
265 | exits.size()); |
266 | ++t_it; |
267 | } |
268 | } |
269 | /* assert exits valid */ |
270 | setRegion(candidate, curr_id, regions); |
271 | } |
272 | |
273 | static |
274 | void mergeUnderBackEdges(const NGHolder &g, const vector<NFAVertex> &topo, |
275 | const BackEdgeSet &backEdges, |
276 | unordered_map<NFAVertex, u32> ®ions) { |
277 | for (const auto &e : backEdges) { |
278 | NFAVertex u = source(e, g); |
279 | NFAVertex v = target(e, g); |
280 | |
281 | u32 ru = regions[u]; |
282 | u32 rv = regions[v]; |
283 | if (ru == rv) { |
284 | continue; |
285 | } |
286 | |
287 | DEBUG_PRINTF("merging v = %zu(%u), u = %zu(%u)\n" , g[v].index, rv, |
288 | g[u].index, ru); |
289 | assert(rv < ru); |
290 | |
291 | for (auto t : topo) { |
292 | u32 r = regions[t]; |
293 | if (r <= ru && r > rv) { |
294 | regions[t] = rv; |
295 | } else if (r > ru) { |
296 | regions[t] = rv + r - ru; |
297 | } |
298 | } |
299 | } |
300 | } |
301 | |
302 | static |
303 | void reorderSpecials(const NGHolder &w, const AcyclicGraph &acyclic_g, |
304 | vector<NFAVertex> &topoOrder) { |
305 | // Start is last element of reverse topo ordering. |
306 | auto it = find(topoOrder.begin(), topoOrder.end(), w.start); |
307 | if (it != topoOrder.end() - 1) { |
308 | DEBUG_PRINTF("repositioning start\n" ); |
309 | assert(it != topoOrder.end()); |
310 | topoOrder.erase(it); |
311 | topoOrder.insert(topoOrder.end(), w.start); |
312 | } |
313 | |
314 | // StartDs is second-to-last element of reverse topo ordering. |
315 | it = find(topoOrder.begin(), topoOrder.end(), w.startDs); |
316 | if (it != topoOrder.end() - 2) { |
317 | DEBUG_PRINTF("repositioning start ds\n" ); |
318 | assert(it != topoOrder.end()); |
319 | topoOrder.erase(it); |
320 | topoOrder.insert(topoOrder.end() - 1, w.startDs); |
321 | } |
322 | |
323 | // AcceptEOD is first element of reverse topo ordering. |
324 | it = find(topoOrder.begin(), topoOrder.end(), w.acceptEod); |
325 | if (it != topoOrder.begin()) { |
326 | DEBUG_PRINTF("repositioning accept\n" ); |
327 | assert(it != topoOrder.end()); |
328 | topoOrder.erase(it); |
329 | topoOrder.insert(topoOrder.begin(), w.acceptEod); |
330 | } |
331 | |
332 | // Accept is second element of reverse topo ordering, if it's connected. |
333 | it = find(topoOrder.begin(), topoOrder.end(), w.accept); |
334 | if (it != topoOrder.begin() + 1) { |
335 | DEBUG_PRINTF("repositioning accept\n" ); |
336 | assert(it != topoOrder.end()); |
337 | topoOrder.erase(it); |
338 | if (in_degree(w.accept, acyclic_g) != 0) { |
339 | topoOrder.insert(topoOrder.begin() + 1, w.accept); |
340 | } |
341 | } |
342 | } |
343 | |
344 | static |
345 | void liftSinks(const AcyclicGraph &acyclic_g, vector<NFAVertex> &topoOrder) { |
346 | unordered_set<NFAVertex> sinks; |
347 | for (auto v : vertices_range(acyclic_g)) { |
348 | if (is_special(v, acyclic_g)) { |
349 | continue; |
350 | } |
351 | |
352 | if (isLeafNode(v, acyclic_g)) { |
353 | DEBUG_PRINTF("sink found %zu\n" , acyclic_g[v].index); |
354 | sinks.insert(NFAVertex(v)); |
355 | } |
356 | } |
357 | |
358 | if (sinks.empty()) { |
359 | DEBUG_PRINTF("no sinks found\n" ); |
360 | return; |
361 | } |
362 | |
363 | bool changed; |
364 | do { |
365 | DEBUG_PRINTF("look\n" ); |
366 | changed = false; |
367 | for (auto v : vertices_range(acyclic_g)) { |
368 | if (is_special(v, acyclic_g) || contains(sinks, NFAVertex(v))) { |
369 | continue; |
370 | } |
371 | |
372 | for (auto w : adjacent_vertices_range(v, acyclic_g)) { |
373 | if (!contains(sinks, NFAVertex(w))) { |
374 | goto next; |
375 | } |
376 | } |
377 | |
378 | DEBUG_PRINTF("sink found %zu\n" , acyclic_g[v].index); |
379 | sinks.insert(NFAVertex(v)); |
380 | changed = true; |
381 | next:; |
382 | } |
383 | } while (changed); |
384 | |
385 | for (auto ri = topoOrder.rbegin() + 1; ri != topoOrder.rend(); ++ri) { |
386 | if (!contains(sinks, *ri)) { |
387 | continue; |
388 | } |
389 | NFAVertex s = *ri; |
390 | DEBUG_PRINTF("handling sink %zu\n" , acyclic_g[s].index); |
391 | unordered_set<NFAVertex> parents; |
392 | for (const auto &e : in_edges_range(s, acyclic_g)) { |
393 | parents.insert(NFAVertex(source(e, acyclic_g))); |
394 | } |
395 | |
396 | /* vertex has no children not reachable on a back edge, bubble the |
397 | * vertex up the topo order to be near its parents */ |
398 | vector<NFAVertex>::reverse_iterator rj = ri; |
399 | --rj; |
400 | while (rj != topoOrder.rbegin() && !contains(parents, *rj)) { |
401 | /* sink is in rj + 1 */ |
402 | assert(*(rj + 1) == s); |
403 | DEBUG_PRINTF("lifting\n" ); |
404 | using std::swap; |
405 | swap(*rj, *(rj + 1)); |
406 | --rj; |
407 | } |
408 | } |
409 | } |
410 | |
411 | using ColorMap = decltype(make_small_color_map(NGHolder())); |
412 | |
413 | /** Build a reverse topo ordering (with only the specials that are in use). We |
414 | * also want to ensure vertices which only lead to back edges are placed near |
415 | * their parents. */ |
416 | static |
417 | vector<NFAVertex> buildTopoOrder(const NGHolder &w, |
418 | const AcyclicGraph &acyclic_g, |
419 | ColorMap &colours) { |
420 | vector<NFAVertex> topoOrder; |
421 | topoOrder.reserve(num_vertices(w)); |
422 | |
423 | topological_sort(acyclic_g, back_inserter(topoOrder), |
424 | color_map(colours)); |
425 | |
426 | reorderSpecials(w, acyclic_g, topoOrder); |
427 | |
428 | if (topoOrder.empty()) { |
429 | return topoOrder; |
430 | } |
431 | |
432 | liftSinks(acyclic_g, topoOrder); |
433 | |
434 | DEBUG_PRINTF("TOPO ORDER\n" ); |
435 | for (auto ri = topoOrder.rbegin(); ri != topoOrder.rend(); ++ri) { |
436 | DEBUG_PRINTF("[%zu]\n" , acyclic_g[*ri].index); |
437 | } |
438 | DEBUG_PRINTF("----------\n" ); |
439 | |
440 | return topoOrder; |
441 | } |
442 | |
443 | unordered_map<NFAVertex, u32> assignRegions(const NGHolder &g) { |
444 | assert(hasCorrectlyNumberedVertices(g)); |
445 | const u32 numVertices = num_vertices(g); |
446 | DEBUG_PRINTF("assigning regions for %u vertices in holder\n" , numVertices); |
447 | |
448 | auto colours = make_small_color_map(g); |
449 | |
450 | // Build an acyclic graph for this NGHolder. |
451 | BackEdgeSet deadEdges; |
452 | depth_first_search(g, |
453 | visitor(BackEdges<BackEdgeSet>(deadEdges)) |
454 | .root_vertex(g.start) |
455 | .color_map(colours)); |
456 | |
457 | auto af = make_bad_edge_filter(&deadEdges); |
458 | AcyclicGraph acyclic_g(g, af); |
459 | |
460 | // Build a (reverse) topological ordering. |
461 | vector<NFAVertex> topoOrder = buildTopoOrder(g, acyclic_g, colours); |
462 | |
463 | // Everybody starts in region 0. |
464 | unordered_map<NFAVertex, u32> regions; |
465 | regions.reserve(numVertices); |
466 | for (auto v : vertices_range(g)) { |
467 | regions.emplace(v, 0); |
468 | } |
469 | |
470 | findDagLeaders(g, acyclic_g, topoOrder, regions); |
471 | mergeUnderBackEdges(g, topoOrder, deadEdges, regions); |
472 | |
473 | return regions; |
474 | } |
475 | |
476 | } // namespace ue2 |
477 | |