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 | #include "rose_build_role_aliasing.h" |
30 | |
31 | #include "ue2common.h" |
32 | #include "rose_build_impl.h" |
33 | #include "rose_build_merge.h" |
34 | #include "rose_build_util.h" |
35 | #include "grey.h" |
36 | #include "nfa/castlecompile.h" |
37 | #include "nfa/goughcompile.h" |
38 | #include "nfa/mcclellancompile_util.h" |
39 | #include "nfagraph/ng_holder.h" |
40 | #include "nfagraph/ng_is_equal.h" |
41 | #include "nfagraph/ng_limex.h" |
42 | #include "nfagraph/ng_prune.h" |
43 | #include "nfagraph/ng_uncalc_components.h" |
44 | #include "nfagraph/ng_util.h" |
45 | #include "util/bitutils.h" |
46 | #include "util/compile_context.h" |
47 | #include "util/container.h" |
48 | #include "util/flat_containers.h" |
49 | #include "util/graph.h" |
50 | #include "util/graph_range.h" |
51 | #include "util/hash.h" |
52 | #include "util/order_check.h" |
53 | |
54 | #include <algorithm> |
55 | #include <numeric> |
56 | #include <vector> |
57 | #include <boost/graph/adjacency_iterator.hpp> |
58 | #include <boost/range/adaptor/map.hpp> |
59 | |
60 | using namespace std; |
61 | using boost::adaptors::map_values; |
62 | |
63 | namespace ue2 { |
64 | |
65 | static constexpr size_t MERGE_GROUP_SIZE_MAX = 200; |
66 | |
67 | namespace { |
68 | // Used for checking edge sets (both in- and out-) against each other. |
69 | struct EdgeAndVertex { |
70 | EdgeAndVertex(const RoseEdge &e, const RoseVertex v_, |
71 | const RoseGraph &g) : v(v_), eprops(g[e]) {} |
72 | virtual ~EdgeAndVertex() {} |
73 | |
74 | virtual bool operator<(const EdgeAndVertex &a) const { |
75 | if (v != a.v) { |
76 | return v < a.v; |
77 | } |
78 | if (eprops.minBound != a.eprops.minBound) { |
79 | return eprops.minBound < a.eprops.minBound; |
80 | } |
81 | if (eprops.maxBound != a.eprops.maxBound) { |
82 | return eprops.maxBound < a.eprops.maxBound; |
83 | } |
84 | if (eprops.rose_top != a.eprops.rose_top) { |
85 | return eprops.rose_top < a.eprops.rose_top; |
86 | |
87 | } |
88 | return eprops.history < a.eprops.history; |
89 | } |
90 | |
91 | virtual bool operator==(const EdgeAndVertex &a) const { |
92 | return v == a.v && |
93 | eprops.minBound == a.eprops.minBound && |
94 | eprops.maxBound == a.eprops.maxBound && |
95 | eprops.rose_top == a.eprops.rose_top && |
96 | eprops.history == a.eprops.history; |
97 | } |
98 | |
99 | private: |
100 | RoseVertex v; |
101 | const RoseEdgeProps &eprops; |
102 | }; |
103 | |
104 | struct AliasOutEdge : EdgeAndVertex { |
105 | AliasOutEdge(const RoseEdge &e, const RoseGraph &g) : |
106 | EdgeAndVertex(e, target(e, g), g) {} |
107 | }; |
108 | |
109 | struct AliasInEdge : EdgeAndVertex { |
110 | AliasInEdge(const RoseEdge &e, const RoseGraph &g) : |
111 | EdgeAndVertex(e, source(e, g), g) {} |
112 | }; |
113 | |
114 | class CandidateSet { |
115 | public: |
116 | using key_type = RoseVertex; |
117 | using iterator = set<RoseVertex>::iterator; |
118 | using const_iterator = set<RoseVertex>::const_iterator; |
119 | |
120 | iterator begin() { return main_cont.begin(); } |
121 | iterator end() { return main_cont.end(); } |
122 | const_iterator begin() const { return main_cont.begin(); } |
123 | const_iterator end() const { return main_cont.end(); } |
124 | |
125 | bool contains(RoseVertex a) const { |
126 | return hash_cont.find(a) != hash_cont.end(); |
127 | } |
128 | |
129 | void insert(RoseVertex a) { |
130 | main_cont.insert(a); |
131 | hash_cont.insert(a); |
132 | } |
133 | |
134 | void erase(iterator aa) { |
135 | RoseVertex a = *aa; |
136 | main_cont.erase(aa); |
137 | hash_cont.erase(a); |
138 | } |
139 | |
140 | void erase(RoseVertex a) { |
141 | main_cont.erase(a); |
142 | hash_cont.erase(a); |
143 | } |
144 | |
145 | size_t size() const { |
146 | assert(hash_cont.size() == main_cont.size()); |
147 | return main_cont.size(); |
148 | } |
149 | |
150 | bool empty() const { |
151 | assert(hash_cont.size() == main_cont.size()); |
152 | return main_cont.empty(); |
153 | } |
154 | |
155 | private: |
156 | /* if a vertex is worth storing, it is worth storing twice */ |
157 | set<RoseVertex> main_cont; /* deterministic iterator */ |
158 | unordered_set<RoseVertex> hash_cont; /* member checks */ |
159 | }; |
160 | |
161 | struct RoseAliasingInfo { |
162 | RoseAliasingInfo(const RoseBuildImpl &build) { |
163 | const auto &g = build.g; |
164 | |
165 | // Populate reverse leftfix map. |
166 | for (auto v : vertices_range(g)) { |
167 | if (g[v].left) { |
168 | rev_leftfix[g[v].left].insert(v); |
169 | } |
170 | } |
171 | |
172 | // Populate reverse ghost vertex map. |
173 | for (const auto &m : build.ghost) { |
174 | rev_ghost[m.second].insert(m.first); |
175 | } |
176 | } |
177 | |
178 | /** \brief Mapping from leftfix to vertices. */ |
179 | unordered_map<left_id, set<RoseVertex>> rev_leftfix; |
180 | |
181 | /** \brief Mapping from undelayed ghost to delayed vertices. */ |
182 | unordered_map<RoseVertex, set<RoseVertex>> rev_ghost; |
183 | }; |
184 | |
185 | } // namespace |
186 | |
187 | // Check successor set: must lead to the same vertices via edges with the |
188 | // same properties. |
189 | static |
190 | bool sameSuccessors(RoseVertex a, RoseVertex b, const RoseGraph &g) { |
191 | if (out_degree(a, g) != out_degree(b, g)) { |
192 | return false; |
193 | } |
194 | |
195 | set<AliasOutEdge> succs_a, succs_b; |
196 | |
197 | for (const auto &e : out_edges_range(a, g)) { |
198 | succs_a.insert(AliasOutEdge(e, g)); |
199 | } |
200 | |
201 | for (const auto &e : out_edges_range(b, g)) { |
202 | succs_b.insert(AliasOutEdge(e, g)); |
203 | } |
204 | |
205 | return (succs_a == succs_b); |
206 | } |
207 | |
208 | /* unlike LeftEngInfo::==, this does a deep check to see if the leftfixes are |
209 | * equivalent rather than checking for pointer equality. */ |
210 | static |
211 | bool hasEqualLeftfixes(RoseVertex a, RoseVertex b, const RoseGraph &g) { |
212 | assert(g[a].left || g[b].left); |
213 | if (!g[a].left || !g[b].left) { |
214 | return false; |
215 | } |
216 | const LeftEngInfo &a_left = g[a].left; |
217 | const LeftEngInfo &b_left = g[b].left; |
218 | |
219 | if (a_left.castle && b_left.castle) { |
220 | return is_equal(*a_left.castle, a_left.leftfix_report, |
221 | *b_left.castle, b_left.leftfix_report); |
222 | } |
223 | |
224 | if (a_left.graph && b_left.graph) { |
225 | /* non-castle engines have graphs */ |
226 | return is_equal(*a_left.graph, a_left.leftfix_report, *b_left.graph, |
227 | b_left.leftfix_report); |
228 | } |
229 | |
230 | /* graph <-> castle cases are not equal */ |
231 | return false; |
232 | } |
233 | |
234 | // Check predecessor set: must come from the same vertices via edges with |
235 | // the same properties. |
236 | static |
237 | bool samePredecessors(RoseVertex a, RoseVertex b, const RoseGraph &g) { |
238 | if (in_degree(a, g) != in_degree(b, g)) { |
239 | return false; |
240 | } |
241 | |
242 | set<AliasInEdge> preds_a, preds_b; |
243 | |
244 | for (const auto &e : in_edges_range(a, g)) { |
245 | preds_a.insert(AliasInEdge(e, g)); |
246 | } |
247 | |
248 | for (const auto &e : in_edges_range(b, g)) { |
249 | preds_b.insert(AliasInEdge(e, g)); |
250 | } |
251 | |
252 | if (preds_a != preds_b) { |
253 | return false; |
254 | } |
255 | |
256 | if (g[a].left || g[b].left) { |
257 | if (!hasEqualLeftfixes(a, b, g)) { |
258 | return false; |
259 | } |
260 | |
261 | for (const auto &e_a : in_edges_range(a, g)) { |
262 | RoseEdge e = edge(source(e_a, g), b, g); |
263 | if (!e || g[e].rose_top != g[e_a].rose_top) { |
264 | DEBUG_PRINTF("bad tops\n" ); |
265 | return false; |
266 | } |
267 | } |
268 | } |
269 | |
270 | return true; |
271 | } |
272 | |
273 | static |
274 | bool hasCommonSuccWithBadBounds(RoseVertex a, RoseVertex b, |
275 | const RoseGraph &g) { |
276 | for (const auto &e_a : out_edges_range(a, g)) { |
277 | if (RoseEdge e = edge(b, target(e_a, g), g)) { |
278 | if (g[e_a].maxBound < g[e].minBound |
279 | || g[e].maxBound < g[e_a].minBound) { |
280 | return true; |
281 | } |
282 | if (g[e_a].rose_top != g[e].rose_top) { |
283 | // Can't trigger two tops on the same leftfix, we can't merge |
284 | // this. |
285 | return true; |
286 | } |
287 | } |
288 | } |
289 | return false; |
290 | } |
291 | |
292 | static |
293 | bool hasCommonPredWithBadBounds(RoseVertex a, RoseVertex b, |
294 | const RoseGraph &g) { |
295 | for (const auto &e_a : in_edges_range(a, g)) { |
296 | if (RoseEdge e = edge(source(e_a, g), b, g)) { |
297 | if (g[e_a].maxBound < g[e].minBound |
298 | || g[e].maxBound < g[e_a].minBound) { |
299 | return true; |
300 | } |
301 | |
302 | // XXX: if we're merging two vertices with different roses, we |
303 | // cannot allow them to share a pred, as we would be unable to |
304 | // merge the (necessarily different) tops on the in-edges. This |
305 | // could be relaxed if we made the tops mergeable (by making |
306 | // edge_top a bitfield, for example). |
307 | if (g[a].left != g[b].left) { |
308 | return true; |
309 | } |
310 | |
311 | } |
312 | } |
313 | return false; |
314 | } |
315 | |
316 | static |
317 | bool canMergeLiterals(RoseVertex a, RoseVertex b, const RoseBuildImpl &build) { |
318 | const auto &lits_a = build.g[a].literals; |
319 | const auto &lits_b = build.g[b].literals; |
320 | assert(!lits_a.empty() && !lits_b.empty()); |
321 | |
322 | // If both vertices have only pseudo-dotstar in-edges, we can merge |
323 | // literals of different lengths and can avoid the check below. |
324 | if (build.hasOnlyPseudoStarInEdges(a) && |
325 | build.hasOnlyPseudoStarInEdges(b)) { |
326 | DEBUG_PRINTF("both have pseudo-dotstar in-edges\n" ); |
327 | return true; |
328 | } |
329 | |
330 | // Otherwise, all the literals involved must have the same length. |
331 | for (u32 a_id : lits_a) { |
332 | const rose_literal_id &la = build.literals.at(a_id); |
333 | for (u32 b_id : lits_b) { |
334 | const rose_literal_id &lb = build.literals.at(b_id); |
335 | |
336 | if (la.elength() != lb.elength()) { |
337 | DEBUG_PRINTF("bad merge %zu!=%zu '%s', '%s'\n" , la.elength(), |
338 | lb.elength(), la.s.c_str(), lb.s.c_str()); |
339 | return false; |
340 | } |
341 | } |
342 | } |
343 | |
344 | return true; |
345 | } |
346 | |
347 | static |
348 | bool isAliasingCandidate(RoseVertex v, const RoseBuildImpl &build) { |
349 | const RoseVertexProps &props = build.g[v]; |
350 | |
351 | // Must have literals. |
352 | if (props.literals.empty()) { |
353 | return false; |
354 | } |
355 | |
356 | assert(*props.literals.begin() != MO_INVALID_IDX); |
357 | return true; |
358 | } |
359 | |
360 | static |
361 | bool sameGhostProperties(const RoseBuildImpl &build, |
362 | const RoseAliasingInfo &rai, RoseVertex a, |
363 | RoseVertex b) { |
364 | // If these are ghost mapping keys, then they must map to the same vertex. |
365 | if (contains(build.ghost, a) || contains(build.ghost, b)) { |
366 | DEBUG_PRINTF("checking ghost key compat\n" ); |
367 | if (!contains(build.ghost, a) || !contains(build.ghost, b)) { |
368 | DEBUG_PRINTF("missing ghost mapping\n" ); |
369 | return false; |
370 | } |
371 | if (build.ghost.at(a) != build.ghost.at(b)) { |
372 | DEBUG_PRINTF("diff ghost mapping\n" ); |
373 | return false; |
374 | } |
375 | DEBUG_PRINTF("ghost mappings ok\n" ); |
376 | return true; |
377 | } |
378 | |
379 | // If they are ghost vertices, then they must have the same literals. |
380 | if (contains(rai.rev_ghost, a) || contains(rai.rev_ghost, b)) { |
381 | if (!contains(rai.rev_ghost, a) || !contains(rai.rev_ghost, b)) { |
382 | DEBUG_PRINTF("missing ghost reverse mapping\n" ); |
383 | return false; |
384 | } |
385 | return build.g[a].literals == build.g[b].literals; |
386 | } |
387 | |
388 | return true; |
389 | } |
390 | |
391 | static |
392 | bool sameRoleProperties(const RoseBuildImpl &build, const RoseAliasingInfo &rai, |
393 | RoseVertex a, RoseVertex b) { |
394 | const RoseGraph &g = build.g; |
395 | const RoseVertexProps &aprops = g[a], &bprops = g[b]; |
396 | |
397 | if (aprops.eod_accept != bprops.eod_accept) { |
398 | return false; |
399 | } |
400 | |
401 | // We don't want to merge a role with LAST_BYTE history with one without, |
402 | // as a role that can only be triggered at EOD cannot safely precede |
403 | // "ordinary" roles. |
404 | if (hasLastByteHistorySucc(g, a) != hasLastByteHistorySucc(g, b)) { |
405 | return false; |
406 | } |
407 | |
408 | // We certainly don't want to merge root roles with non-root roles. |
409 | /* TODO: explain */ |
410 | if (build.isRootSuccessor(a) != build.isRootSuccessor(b)) { |
411 | return false; |
412 | } |
413 | |
414 | if (aprops.som_adjust != bprops.som_adjust) { |
415 | return false; |
416 | } |
417 | |
418 | if (!sameGhostProperties(build, rai, a, b)) { |
419 | return false; |
420 | } |
421 | |
422 | /* "roses are mergeable" check are handled elsewhere */ |
423 | |
424 | return true; |
425 | } |
426 | |
427 | /* Checks compatibility of role properties if we require that two roles are |
428 | * right equiv. */ |
429 | static |
430 | bool sameRightRoleProperties(const RoseBuildImpl &build, RoseVertex a, |
431 | RoseVertex b) { |
432 | const RoseGraph &g = build.g; |
433 | const RoseVertexProps &aprops = g[a], &bprops = g[b]; |
434 | |
435 | if (aprops.reports != bprops.reports) { |
436 | return false; |
437 | } |
438 | |
439 | if (hasAnchHistorySucc(g, a) != hasAnchHistorySucc(g, b)) { |
440 | return false; |
441 | } |
442 | |
443 | // If the history type is ANCH, then we need to be careful that we only |
444 | // merge literals that occur at the same offsets. |
445 | if (hasAnchHistorySucc(g, a) || hasAnchHistorySucc(g, b)) { |
446 | if (aprops.min_offset != bprops.min_offset |
447 | || aprops.max_offset != bprops.max_offset) { |
448 | return false; |
449 | } |
450 | } |
451 | |
452 | if (aprops.suffix != bprops.suffix) { |
453 | return false; |
454 | } |
455 | |
456 | return true; |
457 | } |
458 | |
459 | static |
460 | void mergeEdgeAdd(RoseVertex u, RoseVertex v, const RoseEdge &from_edge, |
461 | const RoseEdge *to_edge, RoseGraph &g) { |
462 | const RoseEdgeProps &from_props = g[from_edge]; |
463 | |
464 | if (!to_edge) { |
465 | DEBUG_PRINTF("adding edge [%zu,%zu]\n" , g[u].index, g[v].index); |
466 | add_edge(u, v, from_props, g); |
467 | } else { |
468 | // union of the two edges. |
469 | DEBUG_PRINTF("updating edge [%zu,%zu]\n" , g[u].index, g[v].index); |
470 | RoseEdgeProps &to_props = g[*to_edge]; |
471 | to_props.minBound = min(to_props.minBound, from_props.minBound); |
472 | to_props.maxBound = max(to_props.maxBound, from_props.maxBound); |
473 | assert(to_props.rose_top == from_props.rose_top); |
474 | } |
475 | } |
476 | |
477 | /* clone a's edges onto b */ |
478 | static |
479 | void mergeEdges(RoseVertex a, RoseVertex b, RoseGraph &g) { |
480 | // All the edges to or from b for quick lookup. |
481 | typedef map<RoseVertex, RoseEdge> EdgeCache; |
482 | EdgeCache b_edges; |
483 | |
484 | // Cache b's in-edges so we can look them up by source quickly. |
485 | for (const auto &e : in_edges_range(b, g)) { |
486 | RoseVertex u = source(e, g); |
487 | b_edges.emplace(u, e); |
488 | } |
489 | |
490 | // Add a's in-edges to b, merging them in where b already has the new edge. |
491 | // Once handled, the in-edges to a are removed. |
492 | RoseGraph::in_edge_iterator ei, ee; |
493 | tie(ei, ee) = in_edges(a, g); |
494 | while (ei != ee) { |
495 | RoseVertex u = source(*ei, g); |
496 | EdgeCache::const_iterator it = b_edges.find(u); |
497 | const RoseEdge *to_edge = (it == b_edges.end() ? nullptr : &it->second); |
498 | mergeEdgeAdd(u, b, *ei, to_edge, g); |
499 | remove_edge(*ei++, g); |
500 | } |
501 | |
502 | // Cache b's out-edges so we can look them up by target quickly. |
503 | b_edges.clear(); |
504 | for (const auto &e : out_edges_range(b, g)) { |
505 | RoseVertex v = target(e, g); |
506 | b_edges.emplace(v, e); |
507 | } |
508 | |
509 | // Add a's out-edges to b, merging them in where b already has the new edge. |
510 | // Once handled, the out-edges to a are removed. |
511 | RoseGraph::out_edge_iterator oi, oe; |
512 | tie(oi, oe) = out_edges(a, g); |
513 | while (oi != oe) { |
514 | RoseVertex v = target(*oi, g); |
515 | EdgeCache::const_iterator it = b_edges.find(v); |
516 | const RoseEdge *to_edge = (it == b_edges.end() ? nullptr : &it->second); |
517 | mergeEdgeAdd(b, v, *oi, to_edge, g); |
518 | remove_edge(*oi++, g); |
519 | } |
520 | |
521 | // Vertex a should no longer have any in- or out-edges. |
522 | assert(degree(a, g) == 0); |
523 | } |
524 | |
525 | static |
526 | void mergeLiteralSets(RoseVertex a, RoseVertex b, RoseBuildImpl &build) { |
527 | RoseGraph &g = build.g; |
528 | const auto &a_literals = g[a].literals; |
529 | for (u32 lit_id : a_literals) { |
530 | auto &lit_vertices = build.literal_info[lit_id].vertices; |
531 | lit_vertices.erase(a); |
532 | lit_vertices.insert(b); |
533 | } |
534 | |
535 | insert(&g[b].literals, a_literals); |
536 | } |
537 | |
538 | static |
539 | void updateAliasingInfo(RoseBuildImpl &build, RoseAliasingInfo &rai, |
540 | RoseVertex a, RoseVertex b) { |
541 | if (build.g[a].left) { |
542 | const left_id left(build.g[a].left); |
543 | assert(contains(rai.rev_leftfix[left], a)); |
544 | rai.rev_leftfix[left].erase(a); |
545 | } |
546 | if (contains(build.ghost, a)) { |
547 | auto ghost = build.ghost.at(a); |
548 | assert(contains(build.ghost, b) && ghost == build.ghost.at(b)); |
549 | build.ghost.erase(a); |
550 | rai.rev_ghost[ghost].erase(a); |
551 | } |
552 | |
553 | if (contains(rai.rev_ghost, a)) { |
554 | for (const auto &v : rai.rev_ghost[a]) { |
555 | build.ghost[v] = b; |
556 | rai.rev_ghost[b].insert(v); |
557 | } |
558 | rai.rev_ghost.erase(a); |
559 | } |
560 | } |
561 | |
562 | /** \brief Common role merge code used by variants below. */ |
563 | static |
564 | void mergeCommon(RoseBuildImpl &build, RoseAliasingInfo &rai, RoseVertex a, |
565 | RoseVertex b) { |
566 | RoseGraph &g = build.g; |
567 | |
568 | assert(g[a].eod_accept == g[b].eod_accept); |
569 | assert(g[a].left == g[b].left); |
570 | assert(!g[a].suffix || g[a].suffix == g[b].suffix); |
571 | |
572 | // In some situations (ghost roles etc), we can have different groups. |
573 | assert(!g[a].groups && !g[b].groups); /* current structure means groups |
574 | * haven't been assigned yet */ |
575 | g[b].groups |= g[a].groups; |
576 | |
577 | mergeLiteralSets(a, b, build); |
578 | updateAliasingInfo(build, rai, a, b); |
579 | |
580 | // Our min and max_offsets should be sane. |
581 | assert(g[b].min_offset <= g[b].max_offset); |
582 | |
583 | // Safety check: we should not have created through a merge a vertex that |
584 | // has an out-edge with ANCH history but is not fixed-offset. |
585 | assert(!hasAnchHistorySucc(g, b) || g[b].fixedOffset()); |
586 | } |
587 | |
588 | /** \brief Merge role 'a' into 'b', left merge path. */ |
589 | static |
590 | void mergeVerticesLeft(RoseVertex a, RoseVertex b, RoseBuildImpl &build, |
591 | RoseAliasingInfo &rai) { |
592 | RoseGraph &g = build.g; |
593 | DEBUG_PRINTF("merging vertex %zu into %zu\n" , g[a].index, g[b].index); |
594 | |
595 | insert(&g[b].reports, g[a].reports); |
596 | |
597 | // Since it is a left merge (identical LHS) we should pick the tighter |
598 | // bound. |
599 | g[b].min_offset = max(g[a].min_offset, g[b].min_offset); |
600 | g[b].max_offset = min(g[a].max_offset, g[b].max_offset); |
601 | |
602 | if (!g[b].suffix) { |
603 | g[b].suffix = g[a].suffix; |
604 | } |
605 | |
606 | mergeEdges(a, b, g); |
607 | mergeCommon(build, rai, a, b); |
608 | } |
609 | |
610 | /** \brief Merge role 'a' into 'b', right merge path. */ |
611 | static |
612 | void mergeVerticesRight(RoseVertex a, RoseVertex b, RoseBuildImpl &build, |
613 | RoseAliasingInfo &rai) { |
614 | RoseGraph &g = build.g; |
615 | DEBUG_PRINTF("merging vertex %zu into %zu\n" , g[a].index, g[b].index); |
616 | |
617 | insert(&g[b].reports, g[a].reports); |
618 | g[b].min_offset = min(g[a].min_offset, g[b].min_offset); |
619 | g[b].max_offset = max(g[a].max_offset, g[b].max_offset); |
620 | |
621 | mergeEdges(a, b, g); |
622 | mergeCommon(build, rai, a, b); |
623 | } |
624 | |
625 | /** |
626 | * Faster version of \ref mergeVertices for diamond merges, for which we know |
627 | * that the in- and out-edge sets, reports and suffixes are identical. |
628 | */ |
629 | static |
630 | void mergeVerticesDiamond(RoseVertex a, RoseVertex b, RoseBuildImpl &build, |
631 | RoseAliasingInfo &rai) { |
632 | RoseGraph &g = build.g; |
633 | DEBUG_PRINTF("merging vertex %zu into %zu\n" , g[a].index, g[b].index); |
634 | |
635 | // For a diamond merge, most properties are already the same (with the |
636 | // notable exception of the literal set). |
637 | assert(g[a].reports == g[b].reports); |
638 | assert(g[a].suffix == g[b].suffix); |
639 | |
640 | g[b].min_offset = min(g[a].min_offset, g[b].min_offset); |
641 | g[b].max_offset = max(g[a].max_offset, g[b].max_offset); |
642 | |
643 | mergeCommon(build, rai, a, b); |
644 | } |
645 | |
646 | static never_inline |
647 | void findCandidates(const RoseBuildImpl &build, CandidateSet *candidates) { |
648 | for (auto v : vertices_range(build.g)) { |
649 | if (isAliasingCandidate(v, build)) { |
650 | DEBUG_PRINTF("candidate %zu\n" , build.g[v].index); |
651 | DEBUG_PRINTF("lits: %u\n" , *build.g[v].literals.begin()); |
652 | candidates->insert(v); |
653 | } |
654 | } |
655 | |
656 | assert(candidates->size() <= num_vertices(build.g)); |
657 | DEBUG_PRINTF("found %zu/%zu candidates\n" , candidates->size(), |
658 | num_vertices(build.g)); |
659 | } |
660 | |
661 | static |
662 | RoseVertex pickPred(const RoseVertex v, const RoseGraph &g, |
663 | const RoseBuildImpl &build) { |
664 | RoseGraph::in_edge_iterator ei, ee; |
665 | tie(ei, ee) = in_edges(v, g); |
666 | if (ei == ee) { |
667 | assert(0); // every candidate should have in-degree! |
668 | return RoseGraph::null_vertex(); |
669 | } |
670 | |
671 | // Avoid roots if we have other options, since it doesn't matter to the |
672 | // merge pass which predecessor we pick. |
673 | RoseVertex u = source(*ei, g); |
674 | while (build.isAnyStart(u) && ++ei != ee) { |
675 | u = source(*ei, g); |
676 | } |
677 | return u; |
678 | } |
679 | |
680 | template<> |
681 | bool contains<>(const CandidateSet &container, const RoseVertex &key) { |
682 | return container.contains(key); |
683 | } |
684 | |
685 | // Simplified version of hasCommonPredWithBadBounds for diamond merges. |
686 | static |
687 | bool hasCommonPredWithDiffRoses(RoseVertex a, RoseVertex b, |
688 | const RoseGraph &g) { |
689 | if (!g[a].left || !g[b].left) { |
690 | DEBUG_PRINTF("one of (a, b) doesn't have a prefix\n" ); |
691 | return true; |
692 | } |
693 | |
694 | // XXX: if we're merging two vertices with different leftfixes, we |
695 | // cannot allow them to share a pred, as we would be unable to |
696 | // merge the (necessarily different) tops on the in-edges. This |
697 | // could be relaxed if we made the tops mergeable (by making |
698 | // edge_top a bitfield, for example). |
699 | |
700 | const bool equal_roses = hasEqualLeftfixes(a, b, g); |
701 | |
702 | for (const auto &e_a : in_edges_range(a, g)) { |
703 | if (RoseEdge e = edge(source(e_a, g), b, g)) { |
704 | DEBUG_PRINTF("common pred, e_r=%d r_t %u,%u\n" , |
705 | (int)equal_roses, g[e].rose_top, g[e_a].rose_top); |
706 | if (!equal_roses) { |
707 | DEBUG_PRINTF("different roses\n" ); |
708 | return true; |
709 | } |
710 | if (g[e].rose_top != g[e_a].rose_top) { |
711 | DEBUG_PRINTF("bad tops\n" ); |
712 | return true; |
713 | } |
714 | } |
715 | } |
716 | DEBUG_PRINTF("ok\n" ); |
717 | return false; |
718 | } |
719 | |
720 | static |
721 | void pruneReportIfUnused(const RoseBuildImpl &build, shared_ptr<NGHolder> h, |
722 | const set<RoseVertex> &verts, ReportID report) { |
723 | DEBUG_PRINTF("trying to prune %u from %p (v %zu)\n" , report, h.get(), |
724 | verts.size()); |
725 | for (RoseVertex v : verts) { |
726 | if (build.g[v].left.graph == h && |
727 | build.g[v].left.leftfix_report == report) { |
728 | DEBUG_PRINTF("report %u still in use\n" , report); |
729 | return; |
730 | } |
731 | } |
732 | |
733 | if (!verts.empty()) { |
734 | // Report no longer in use, but graph h is still alive: we should prune |
735 | // the report if we can do so without rendering the graph |
736 | // unimplementable. |
737 | |
738 | DEBUG_PRINTF("report %u has been merged away, pruning\n" , report); |
739 | assert(h->kind == (build.isRootSuccessor(*verts.begin()) ? NFA_PREFIX |
740 | : NFA_INFIX)); |
741 | unique_ptr<NGHolder> h_new = cloneHolder(*h); |
742 | pruneReport(*h_new, report); |
743 | |
744 | if (isImplementableNFA(*h_new, nullptr, build.cc)) { |
745 | clear_graph(*h); |
746 | cloneHolder(*h, *h_new); |
747 | } else { |
748 | DEBUG_PRINTF("prune produced unimplementable graph, " |
749 | "leaving as-is\n" ); |
750 | } |
751 | } |
752 | } |
753 | |
754 | /** \brief Remove any tops that don't lead to the given report from this |
755 | * Castle. */ |
756 | static |
757 | void pruneCastle(CastleProto &castle, ReportID report) { |
758 | unordered_set<u32> dead; // tops to remove. |
759 | for (const auto &m : castle.repeats) { |
760 | if (!contains(m.second.reports, report)) { |
761 | dead.insert(m.first); |
762 | } |
763 | } |
764 | |
765 | for (const auto &top : dead) { |
766 | castle.erase(top); |
767 | } |
768 | |
769 | assert(!castle.repeats.empty()); |
770 | } |
771 | |
772 | /** \brief Set all reports to the given one. */ |
773 | static |
774 | void setReports(CastleProto &castle, ReportID report) { |
775 | castle.report_map.clear(); |
776 | for (auto &e : castle.repeats) { |
777 | u32 top = e.first; |
778 | auto &repeat = e.second; |
779 | repeat.reports.clear(); |
780 | repeat.reports.insert(report); |
781 | castle.report_map[report].insert(top); |
782 | } |
783 | } |
784 | |
785 | static |
786 | void updateEdgeTops(RoseGraph &g, RoseVertex v, const map<u32, u32> &top_map) { |
787 | for (const auto &e : in_edges_range(v, g)) { |
788 | g[e].rose_top = top_map.at(g[e].rose_top); |
789 | } |
790 | } |
791 | |
792 | static |
793 | void pruneUnusedTops(CastleProto &castle, const RoseGraph &g, |
794 | const set<RoseVertex> &verts) { |
795 | unordered_set<u32> used_tops; |
796 | for (auto v : verts) { |
797 | assert(g[v].left.castle.get() == &castle); |
798 | |
799 | for (const auto &e : in_edges_range(v, g)) { |
800 | u32 top = g[e].rose_top; |
801 | assert(contains(castle.repeats, top)); |
802 | used_tops.insert(top); |
803 | } |
804 | } |
805 | |
806 | DEBUG_PRINTF("castle has %zu tops, graph has %zu tops\n" , |
807 | castle.repeats.size(), used_tops.size()); |
808 | |
809 | for (u32 top : assoc_keys(castle.repeats)) { |
810 | if (!contains(used_tops, top)) { |
811 | DEBUG_PRINTF("removing unused top %u\n" , top); |
812 | castle.erase(top); |
813 | } |
814 | } |
815 | } |
816 | |
817 | static |
818 | void pruneUnusedTops(NGHolder &h, const RoseGraph &g, |
819 | const set<RoseVertex> &verts) { |
820 | if (!is_triggered(h)) { |
821 | DEBUG_PRINTF("not triggered, no tops\n" ); |
822 | return; |
823 | } |
824 | assert(isCorrectlyTopped(h)); |
825 | DEBUG_PRINTF("pruning unused tops\n" ); |
826 | flat_set<u32> used_tops; |
827 | for (auto v : verts) { |
828 | assert(g[v].left.graph.get() == &h); |
829 | |
830 | for (const auto &e : in_edges_range(v, g)) { |
831 | u32 top = g[e].rose_top; |
832 | used_tops.insert(top); |
833 | } |
834 | } |
835 | |
836 | vector<NFAEdge> dead; |
837 | for (const auto &e : out_edges_range(h.start, h)) { |
838 | NFAVertex v = target(e, h); |
839 | if (v == h.startDs) { |
840 | continue; // stylised edge, leave it alone. |
841 | } |
842 | flat_set<u32> pruned_tops; |
843 | auto pt_inserter = inserter(pruned_tops, pruned_tops.end()); |
844 | set_intersection(h[e].tops.begin(), h[e].tops.end(), |
845 | used_tops.begin(), used_tops.end(), pt_inserter); |
846 | h[e].tops = std::move(pruned_tops); |
847 | if (h[e].tops.empty()) { |
848 | DEBUG_PRINTF("edge (start,%zu) has only unused tops\n" , h[v].index); |
849 | dead.push_back(e); |
850 | } |
851 | } |
852 | |
853 | if (dead.empty()) { |
854 | return; |
855 | } |
856 | |
857 | remove_edges(dead, h); |
858 | pruneUseless(h); |
859 | clearReports(h); // As we may have removed vacuous edges. |
860 | } |
861 | |
862 | static |
863 | bool mergeSameCastle(RoseBuildImpl &build, RoseVertex a, RoseVertex b, |
864 | RoseAliasingInfo &rai) { |
865 | RoseGraph &g = build.g; |
866 | LeftEngInfo &a_left = g[a].left; |
867 | LeftEngInfo &b_left = g[b].left; |
868 | CastleProto &castle = *a_left.castle; |
869 | |
870 | DEBUG_PRINTF("a report=%u, b report=%u\n" , a_left.leftfix_report, |
871 | b_left.leftfix_report); |
872 | |
873 | u32 merge_count = 0; |
874 | for (const auto &c : castle.repeats) { |
875 | DEBUG_PRINTF("top %u -> %s report %u\n" , c.first, |
876 | c.second.bounds.str().c_str(), *c.second.reports.begin()); |
877 | if (contains(c.second.reports, a_left.leftfix_report) || |
878 | contains(c.second.reports, b_left.leftfix_report)) { |
879 | merge_count++; |
880 | } |
881 | } |
882 | |
883 | if (castle.repeats.size() + merge_count > castle.max_occupancy) { |
884 | DEBUG_PRINTF("too big to merge\n" ); |
885 | return false; |
886 | } |
887 | |
888 | const ReportID new_report = build.getNewNfaReport(); |
889 | map<u32, u32> a_top_map, b_top_map; |
890 | |
891 | for (const auto &c : castle.repeats) { |
892 | u32 old_top = c.first; |
893 | if (contains(c.second.reports, a_left.leftfix_report)) { |
894 | PureRepeat pr = c.second; |
895 | pr.reports.clear(); |
896 | pr.reports.insert(new_report); |
897 | u32 new_top = castle.merge(pr); |
898 | assert(new_top < castle.max_occupancy); |
899 | a_top_map[old_top] = new_top; |
900 | } else if (contains(c.second.reports, b_left.leftfix_report)) { |
901 | PureRepeat pr = c.second; |
902 | pr.reports.clear(); |
903 | pr.reports.insert(new_report); |
904 | u32 new_top = castle.merge(pr); |
905 | assert(new_top < castle.max_occupancy); |
906 | b_top_map[old_top] = new_top; |
907 | } |
908 | } |
909 | |
910 | assert(contains(rai.rev_leftfix[b_left], b)); |
911 | rai.rev_leftfix[b_left].erase(b); |
912 | rai.rev_leftfix[a_left].insert(b); |
913 | |
914 | a_left.leftfix_report = new_report; |
915 | b_left.leftfix_report = new_report; |
916 | assert(a_left == b_left); |
917 | |
918 | updateEdgeTops(g, a, a_top_map); |
919 | updateEdgeTops(g, b, b_top_map); |
920 | |
921 | pruneUnusedTops(castle, g, rai.rev_leftfix[a_left]); |
922 | return true; |
923 | } |
924 | |
925 | static |
926 | bool attemptRoseCastleMerge(RoseBuildImpl &build, bool preds_same, RoseVertex a, |
927 | RoseVertex b, bool trivialCasesOnly, |
928 | RoseAliasingInfo &rai) { |
929 | RoseGraph &g = build.g; |
930 | LeftEngInfo &a_left = g[a].left; |
931 | LeftEngInfo &b_left = g[b].left; |
932 | left_id a_left_id(a_left); |
933 | left_id b_left_id(b_left); |
934 | CastleProto &a_castle = *a_left_id.castle(); |
935 | CastleProto &b_castle = *b_left_id.castle(); |
936 | |
937 | if (a_castle.reach() != b_castle.reach()) { |
938 | DEBUG_PRINTF("different reach\n" ); |
939 | return false; |
940 | } |
941 | |
942 | DEBUG_PRINTF("a castle=%p, report=%u\n" , &a_castle, a_left.leftfix_report); |
943 | DEBUG_PRINTF("b castle=%p, report=%u\n" , &b_castle, b_left.leftfix_report); |
944 | |
945 | if (&a_castle == &b_castle) { |
946 | DEBUG_PRINTF("castles are the same\n" ); |
947 | return mergeSameCastle(build, a, b, rai); |
948 | } |
949 | |
950 | if (is_equal(a_castle, a_left.leftfix_report, b_castle, |
951 | b_left.leftfix_report)) { |
952 | DEBUG_PRINTF("castles are equiv with respect to reports\n" ); |
953 | if (rai.rev_leftfix[a_left_id].size() == 1) { |
954 | /* nobody else is using a_castle */ |
955 | rai.rev_leftfix[b_left_id].erase(b); |
956 | rai.rev_leftfix[a_left_id].insert(b); |
957 | pruneUnusedTops(b_castle, g, rai.rev_leftfix[b_left_id]); |
958 | b_left.castle = a_left.castle; |
959 | b_left.leftfix_report = a_left.leftfix_report; |
960 | DEBUG_PRINTF("OK -> only user of a_castle\n" ); |
961 | return true; |
962 | } |
963 | |
964 | if (rai.rev_leftfix[b_left_id].size() == 1) { |
965 | /* nobody else is using b_castle */ |
966 | rai.rev_leftfix[a_left_id].erase(a); |
967 | rai.rev_leftfix[b_left_id].insert(a); |
968 | pruneUnusedTops(a_castle, g, rai.rev_leftfix[a_left_id]); |
969 | a_left.castle = b_left.castle; |
970 | a_left.leftfix_report = b_left.leftfix_report; |
971 | DEBUG_PRINTF("OK -> only user of b_castle\n" ); |
972 | return true; |
973 | } |
974 | |
975 | if (preds_same) { |
976 | /* preds are the same anyway in diamond/left merges just need to |
977 | * check that all the literals in rev_leftfix[b_h] can handle a_h */ |
978 | for (auto v : rai.rev_leftfix[b_left_id]) { |
979 | if (!mergeableRoseVertices(build, a, v)) { |
980 | goto literal_mismatch_1; |
981 | } |
982 | } |
983 | |
984 | rai.rev_leftfix[a_left_id].erase(a); |
985 | rai.rev_leftfix[b_left_id].insert(a); |
986 | pruneUnusedTops(a_castle, g, rai.rev_leftfix[a_left_id]); |
987 | a_left.castle = b_left.castle; |
988 | a_left.leftfix_report = b_left.leftfix_report; |
989 | DEBUG_PRINTF("OK -> same preds ???\n" ); |
990 | return true; |
991 | literal_mismatch_1: |
992 | /* preds are the same anyway in diamond/left merges just need to |
993 | * check that all the literals in rev_leftfix[a_h] can handle b_h */ |
994 | for (auto v : rai.rev_leftfix[a_left_id]) { |
995 | if (!mergeableRoseVertices(build, v, b)) { |
996 | goto literal_mismatch_2; |
997 | } |
998 | } |
999 | |
1000 | rai.rev_leftfix[b_left_id].erase(b); |
1001 | rai.rev_leftfix[a_left_id].insert(b); |
1002 | pruneUnusedTops(b_castle, g, rai.rev_leftfix[b_left_id]); |
1003 | b_left.castle = a_left.castle; |
1004 | b_left.leftfix_report = a_left.leftfix_report; |
1005 | DEBUG_PRINTF("OK -> same preds ???\n" ); |
1006 | return true; |
1007 | literal_mismatch_2:; |
1008 | } |
1009 | DEBUG_PRINTF("OK -> create new\n" ); |
1010 | /* we need to create a new graph as there may be other people |
1011 | * using b_left and it would be bad if a's preds started triggering it |
1012 | */ |
1013 | ReportID new_report = build.getNewNfaReport(); |
1014 | shared_ptr<CastleProto> new_castle = make_shared<CastleProto>(a_castle); |
1015 | pruneCastle(*new_castle, a_left.leftfix_report); |
1016 | setReports(*new_castle, new_report); |
1017 | |
1018 | rai.rev_leftfix[a_left_id].erase(a); |
1019 | rai.rev_leftfix[b_left_id].erase(b); |
1020 | pruneUnusedTops(*a_left.castle, g, rai.rev_leftfix[a_left_id]); |
1021 | pruneUnusedTops(*b_left.castle, g, rai.rev_leftfix[b_left_id]); |
1022 | |
1023 | a_left.leftfix_report = new_report; |
1024 | b_left.leftfix_report = new_report; |
1025 | a_left.castle = new_castle; |
1026 | b_left.castle = new_castle; |
1027 | |
1028 | assert(a_left == b_left); |
1029 | rai.rev_leftfix[a_left].insert(a); |
1030 | rai.rev_leftfix[a_left].insert(b); |
1031 | pruneUnusedTops(*new_castle, g, rai.rev_leftfix[a_left]); |
1032 | return true; |
1033 | } |
1034 | |
1035 | // Everything after this point requires more work, so we guard it with the |
1036 | // trivial cases argument.. |
1037 | if (trivialCasesOnly) { |
1038 | return false; |
1039 | } |
1040 | |
1041 | // Only infixes. Prefixes require special care when doing non-trivial |
1042 | // merges. |
1043 | if (!build.isNonRootSuccessor(a) || !build.isNonRootSuccessor(b)) { |
1044 | return false; |
1045 | } |
1046 | |
1047 | set<RoseVertex> &b_verts = rai.rev_leftfix[b_left_id]; |
1048 | set<RoseVertex> aa; |
1049 | aa.insert(a); |
1050 | |
1051 | if (!mergeableRoseVertices(build, aa, b_verts)) { |
1052 | DEBUG_PRINTF("vertices not mergeable\n" ); |
1053 | return false; |
1054 | } |
1055 | |
1056 | if (!build.cc.grey.roseMultiTopRoses || !build.cc.grey.allowCastle) { |
1057 | return false; |
1058 | } |
1059 | |
1060 | DEBUG_PRINTF("merging into new castle\n" ); |
1061 | |
1062 | // Clone new castle with a's repeats in it, set to a new report. |
1063 | ReportID new_report = build.getNewNfaReport(); |
1064 | shared_ptr<CastleProto> m_castle = make_shared<CastleProto>(a_castle); |
1065 | pruneCastle(*m_castle, a_left.leftfix_report); |
1066 | setReports(*m_castle, new_report); |
1067 | |
1068 | // Merge in the relevant repeats from b with the new report. Note that |
1069 | // we'll have to remap tops appropriately. |
1070 | map<u32, u32> b_top_map; |
1071 | for (const auto &e : in_edges_range(b, g)) { |
1072 | u32 top = g[e].rose_top; |
1073 | assert(contains(b_castle.repeats, top)); |
1074 | |
1075 | PureRepeat pr = b_castle.repeats[top]; // mutable copy |
1076 | pr.reports.clear(); |
1077 | pr.reports.insert(new_report); |
1078 | |
1079 | // We should be protected from merging common preds with tops leading |
1080 | // to completely different repeats by earlier checks, but just in |
1081 | // case... |
1082 | if (RoseEdge a_edge = edge(source(e, g), a, g)) { |
1083 | u32 a_top = g[a_edge].rose_top; |
1084 | const PureRepeat &a_pr = m_castle->repeats[a_top]; // new report |
1085 | if (pr != a_pr) { |
1086 | DEBUG_PRINTF("merge failed, common pred with diff repeat\n" ); |
1087 | return false; |
1088 | } |
1089 | } |
1090 | |
1091 | u32 new_top = m_castle->merge(pr); |
1092 | if (new_top == CastleProto::max_occupancy) { |
1093 | DEBUG_PRINTF("merge failed\n" ); |
1094 | return false; |
1095 | } |
1096 | b_top_map[top] = new_top; |
1097 | } |
1098 | |
1099 | updateEdgeTops(g, b, b_top_map); |
1100 | |
1101 | DEBUG_PRINTF("merged into castle containing %zu repeats\n" , |
1102 | m_castle->repeats.size()); |
1103 | |
1104 | rai.rev_leftfix[a_left_id].erase(a); |
1105 | rai.rev_leftfix[b_left_id].erase(b); |
1106 | pruneUnusedTops(*a_left.castle, g, rai.rev_leftfix[a_left_id]); |
1107 | pruneUnusedTops(*b_left.castle, g, rai.rev_leftfix[b_left_id]); |
1108 | |
1109 | a_left.castle = m_castle; |
1110 | a_left.leftfix_report = new_report; |
1111 | b_left.castle = m_castle; |
1112 | b_left.leftfix_report = new_report; |
1113 | |
1114 | assert(a_left == b_left); |
1115 | rai.rev_leftfix[a_left].insert(a); |
1116 | rai.rev_leftfix[a_left].insert(b); |
1117 | pruneUnusedTops(*m_castle, g, rai.rev_leftfix[a_left]); |
1118 | return true; |
1119 | } |
1120 | |
1121 | static |
1122 | bool attemptRoseGraphMerge(RoseBuildImpl &build, bool preds_same, RoseVertex a, |
1123 | RoseVertex b, bool trivialCasesOnly, |
1124 | RoseAliasingInfo &rai) { |
1125 | RoseGraph &g = build.g; |
1126 | LeftEngInfo &a_left = g[a].left; |
1127 | LeftEngInfo &b_left = g[b].left; |
1128 | left_id a_left_id(a_left); |
1129 | left_id b_left_id(b_left); |
1130 | shared_ptr<NGHolder> a_h = a_left.graph; |
1131 | shared_ptr<NGHolder> b_h = b_left.graph; |
1132 | assert(a_h && b_h); |
1133 | assert(isImplementableNFA(*a_h, nullptr, build.cc)); |
1134 | assert(isImplementableNFA(*b_h, nullptr, build.cc)); |
1135 | |
1136 | // If we only differ in reports, this is a very easy merge. Just use b's |
1137 | // report for both. |
1138 | /* Actually not so easy, there may be other poor suckers using a and/or b's |
1139 | * reports who will be surprised by this change */ |
1140 | if (a_h == b_h) { |
1141 | DEBUG_PRINTF("OK -> same actual holder\n" ); |
1142 | ReportID a_oldreport = a_left.leftfix_report; |
1143 | ReportID b_oldreport = b_left.leftfix_report; |
1144 | ReportID new_report = build.getNewNfaReport(); |
1145 | duplicateReport(*a_h, a_left.leftfix_report, new_report); |
1146 | duplicateReport(*b_h, b_left.leftfix_report, new_report); |
1147 | a_left.leftfix_report = new_report; |
1148 | b_left.leftfix_report = new_report; |
1149 | pruneReportIfUnused(build, b_h, rai.rev_leftfix[b_left_id], |
1150 | a_oldreport); |
1151 | pruneReportIfUnused(build, b_h, rai.rev_leftfix[b_left_id], |
1152 | b_oldreport); |
1153 | pruneUnusedTops(*b_h, g, rai.rev_leftfix[b_left_id]); |
1154 | assert(a_left == b_left); |
1155 | return true; |
1156 | } |
1157 | |
1158 | /* if it is the same graph, it is also fairly easy */ |
1159 | if (is_equal(*a_h, a_left.leftfix_report, *b_h, b_left.leftfix_report)) { |
1160 | if (rai.rev_leftfix[a_left_id].size() == 1) { |
1161 | /* nobody else is using a_h */ |
1162 | rai.rev_leftfix[b_left_id].erase(b); |
1163 | rai.rev_leftfix[a_left_id].insert(b); |
1164 | b_left.graph = a_h; |
1165 | b_left.leftfix_report = a_left.leftfix_report; |
1166 | pruneUnusedTops(*b_h, g, rai.rev_leftfix[b_left_id]); |
1167 | DEBUG_PRINTF("OK -> only user of a_h\n" ); |
1168 | return true; |
1169 | } |
1170 | |
1171 | if (rai.rev_leftfix[b_left_id].size() == 1) { |
1172 | /* nobody else is using b_h */ |
1173 | rai.rev_leftfix[a_left_id].erase(a); |
1174 | rai.rev_leftfix[b_left_id].insert(a); |
1175 | a_left.graph = b_h; |
1176 | a_left.leftfix_report = b_left.leftfix_report; |
1177 | pruneUnusedTops(*a_h, g, rai.rev_leftfix[a_left_id]); |
1178 | DEBUG_PRINTF("OK -> only user of b_h\n" ); |
1179 | return true; |
1180 | } |
1181 | |
1182 | if (preds_same) { |
1183 | /* preds are the same anyway in diamond/left merges just need to |
1184 | * check that all the literals in rev_leftfix[b_h] can handle a_h */ |
1185 | for (auto v : rai.rev_leftfix[b_left_id]) { |
1186 | if (!mergeableRoseVertices(build, a, v)) { |
1187 | goto literal_mismatch_1; |
1188 | } |
1189 | } |
1190 | |
1191 | rai.rev_leftfix[a_left_id].erase(a); |
1192 | rai.rev_leftfix[b_left_id].insert(a); |
1193 | a_left.graph = b_h; |
1194 | a_left.leftfix_report = b_left.leftfix_report; |
1195 | pruneUnusedTops(*a_h, g, rai.rev_leftfix[a_left_id]); |
1196 | DEBUG_PRINTF("OK -> same preds ???\n" ); |
1197 | return true; |
1198 | literal_mismatch_1: |
1199 | /* preds are the same anyway in diamond/left merges just need to |
1200 | * check that all the literals in rev_leftfix[a_h] can handle b_h */ |
1201 | for (auto v : rai.rev_leftfix[a_left_id]) { |
1202 | if (!mergeableRoseVertices(build, v, b)) { |
1203 | goto literal_mismatch_2; |
1204 | } |
1205 | } |
1206 | |
1207 | rai.rev_leftfix[b_left_id].erase(b); |
1208 | rai.rev_leftfix[a_left_id].insert(b); |
1209 | b_left.graph = a_h; |
1210 | b_left.leftfix_report = a_left.leftfix_report; |
1211 | pruneUnusedTops(*b_h, g, rai.rev_leftfix[b_left_id]); |
1212 | DEBUG_PRINTF("OK -> same preds ???\n" ); |
1213 | return true; |
1214 | literal_mismatch_2:; |
1215 | } |
1216 | DEBUG_PRINTF("OK -> create new\n" ); |
1217 | /* we need to create a new graph as there may be other people |
1218 | * using b_left and it would be bad if a's preds started triggering it |
1219 | */ |
1220 | ReportID new_report = build.getNewNfaReport(); |
1221 | shared_ptr<NGHolder> new_graph = cloneHolder(*b_h); |
1222 | duplicateReport(*new_graph, b_left.leftfix_report, new_report); |
1223 | pruneAllOtherReports(*new_graph, new_report); |
1224 | |
1225 | if (!isImplementableNFA(*new_graph, nullptr, build.cc)) { |
1226 | DEBUG_PRINTF("new graph not implementable\n" ); |
1227 | return false; |
1228 | } |
1229 | |
1230 | rai.rev_leftfix[a_left_id].erase(a); |
1231 | rai.rev_leftfix[b_left_id].erase(b); |
1232 | pruneUnusedTops(*a_h, g, rai.rev_leftfix[a_left_id]); |
1233 | pruneUnusedTops(*b_h, g, rai.rev_leftfix[b_left_id]); |
1234 | |
1235 | a_left.leftfix_report = new_report; |
1236 | b_left.leftfix_report = new_report; |
1237 | a_left.graph = new_graph; |
1238 | b_left.graph = new_graph; |
1239 | |
1240 | rai.rev_leftfix[a_left].insert(a); |
1241 | rai.rev_leftfix[a_left].insert(b); |
1242 | pruneUnusedTops(*new_graph, g, rai.rev_leftfix[a_left]); |
1243 | return true; |
1244 | } |
1245 | |
1246 | // Everything after this point requires merging via the uncalc code, so we |
1247 | // guard it with the trivial cases arg. |
1248 | if (trivialCasesOnly) { |
1249 | return false; |
1250 | } |
1251 | |
1252 | // Only infixes. Prefixes require special care when doing non-trivial |
1253 | // merges. |
1254 | if (!build.isNonRootSuccessor(a) || !build.isNonRootSuccessor(b)) { |
1255 | return false; |
1256 | } |
1257 | |
1258 | DEBUG_PRINTF("attempting merge of roses on vertices %zu and %zu\n" , |
1259 | g[a].index, g[b].index); |
1260 | |
1261 | set<RoseVertex> &b_verts = rai.rev_leftfix[b_left]; |
1262 | set<RoseVertex> aa; |
1263 | aa.insert(a); |
1264 | |
1265 | if (!mergeableRoseVertices(build, aa, b_verts)) { |
1266 | DEBUG_PRINTF("vertices not mergeable\n" ); |
1267 | return false; |
1268 | } |
1269 | |
1270 | if (!build.cc.grey.roseMultiTopRoses) { |
1271 | return false; |
1272 | } |
1273 | |
1274 | // Clone a copy of a's NFA to operate on, and store a copy of its in-edge |
1275 | // properties. |
1276 | |
1277 | /* We need to allocate a new report id because */ |
1278 | ReportID a_oldreport = a_left.leftfix_report; |
1279 | ReportID b_oldreport = b_left.leftfix_report; |
1280 | ReportID new_report = build.getNewNfaReport(); |
1281 | duplicateReport(*b_h, b_left.leftfix_report, new_report); |
1282 | b_left.leftfix_report = new_report; |
1283 | pruneReportIfUnused(build, b_h, rai.rev_leftfix[b_left_id], b_oldreport); |
1284 | |
1285 | NGHolder victim; |
1286 | cloneHolder(victim, *a_h); |
1287 | duplicateReport(victim, a_left.leftfix_report, new_report); |
1288 | pruneAllOtherReports(victim, new_report); |
1289 | |
1290 | map<RoseVertex, RoseEdgeProps> a_props; |
1291 | for (const auto &e : in_edges_range(a, g)) { |
1292 | a_props[source(e, g)] = g[e]; |
1293 | } |
1294 | |
1295 | DEBUG_PRINTF("victim %zu states\n" , num_vertices(*a_h)); |
1296 | DEBUG_PRINTF("winner %zu states\n" , num_vertices(*b_h)); |
1297 | |
1298 | if (!setDistinctRoseTops(g, victim, *b_h, deque<RoseVertex>(1, a))) { |
1299 | assert(roseHasTops(build, a)); |
1300 | assert(roseHasTops(build, b)); |
1301 | return false; |
1302 | } |
1303 | |
1304 | assert(victim.kind == b_h->kind); |
1305 | assert(!generates_callbacks(*b_h)); |
1306 | |
1307 | if (!mergeNfaPair(victim, *b_h, nullptr, build.cc)) { |
1308 | DEBUG_PRINTF("merge failed\n" ); |
1309 | // Restore in-edge properties. |
1310 | for (const auto &e : in_edges_range(a, g)) { |
1311 | g[e] = a_props[source(e, g)]; |
1312 | } |
1313 | assert(roseHasTops(build, a)); |
1314 | assert(roseHasTops(build, b)); |
1315 | return false; |
1316 | } |
1317 | |
1318 | DEBUG_PRINTF("merge succeeded -> %zu vertices\n" , num_vertices(*b_h)); |
1319 | |
1320 | // update A's rose data to point to the merged graph. |
1321 | a_left.graph = b_h; |
1322 | a_left.leftfix_report = new_report; |
1323 | |
1324 | assert(contains(rai.rev_leftfix[a_left_id], a)); |
1325 | assert(contains(rai.rev_leftfix[b_left_id], b)); |
1326 | rai.rev_leftfix[a_left_id].erase(a); |
1327 | rai.rev_leftfix[b_left_id].insert(a); |
1328 | |
1329 | pruneUnusedTops(*a_h, g, rai.rev_leftfix[a_left_id]); |
1330 | pruneUnusedTops(*b_h, g, rai.rev_leftfix[b_left_id]); |
1331 | |
1332 | // Prune A's report from its old prefix if it was only used by A. |
1333 | pruneReportIfUnused(build, a_h, rai.rev_leftfix[a_left_id], a_oldreport); |
1334 | |
1335 | reduceImplementableGraph(*b_h, SOM_NONE, nullptr, build.cc); |
1336 | |
1337 | assert(roseHasTops(build, a)); |
1338 | assert(roseHasTops(build, b)); |
1339 | assert(isImplementableNFA(*b_h, nullptr, build.cc)); |
1340 | return true; |
1341 | } |
1342 | |
1343 | // Called by the role aliasing pass: Attempt to merge rose a into b, updating |
1344 | // the two LeftEngInfo structures to be the same. Returns false if the merge |
1345 | // is not possible. |
1346 | static |
1347 | bool attemptRoseMerge(RoseBuildImpl &build, bool preds_same, RoseVertex a, |
1348 | RoseVertex b, bool trivialCasesOnly, |
1349 | RoseAliasingInfo &rai) { |
1350 | DEBUG_PRINTF("attempting rose merge, vertices a=%zu, b=%zu\n" , |
1351 | build.g[a].index, build.g[b].index); |
1352 | assert(a != b); |
1353 | |
1354 | RoseGraph &g = build.g; |
1355 | LeftEngInfo &a_left = g[a].left; |
1356 | LeftEngInfo &b_left = g[b].left; |
1357 | |
1358 | // Trivial case. |
1359 | if (a_left == b_left) { |
1360 | DEBUG_PRINTF("roses are identical, no leftfix or already merged\n" ); |
1361 | return true; |
1362 | } |
1363 | |
1364 | const left_id a_left_id(a_left); |
1365 | const left_id b_left_id(b_left); |
1366 | |
1367 | /* Haig merges not supported at the moment */ |
1368 | if (a_left.haig || b_left.haig) { |
1369 | return false; |
1370 | } |
1371 | |
1372 | /* dfa merges not supported at the moment (no multitop) */ |
1373 | if (a_left.dfa || b_left.dfa) { |
1374 | return false; |
1375 | } |
1376 | |
1377 | // Only non-transients for the moment. |
1378 | if (contains(build.transient, a_left_id) || |
1379 | contains(build.transient, b_left_id)) { |
1380 | return false; |
1381 | } |
1382 | |
1383 | /* It is not possible to merge roles with different lags as we can only |
1384 | * test the leftfix at one location relative to the literal match */ |
1385 | if (a_left.lag != b_left.lag) { |
1386 | return false; |
1387 | } |
1388 | |
1389 | assert(roseHasTops(build, a)); |
1390 | assert(roseHasTops(build, b)); |
1391 | |
1392 | if (a_left_id.graph() && b_left_id.graph()) { |
1393 | return attemptRoseGraphMerge(build, preds_same, a, b, trivialCasesOnly, |
1394 | rai); |
1395 | } |
1396 | |
1397 | if (a_left_id.castle() && b_left_id.castle()) { |
1398 | return attemptRoseCastleMerge(build, preds_same, a, b, trivialCasesOnly, |
1399 | rai); |
1400 | } |
1401 | |
1402 | return false; |
1403 | } |
1404 | |
1405 | /** |
1406 | * \brief Buckets that only contain one vertex are never going to lead to a |
1407 | * merge. |
1408 | */ |
1409 | static |
1410 | void removeSingletonBuckets(vector<vector<RoseVertex>> &buckets) { |
1411 | auto it = remove_if( |
1412 | begin(buckets), end(buckets), |
1413 | [](const vector<RoseVertex> &bucket) { return bucket.size() < 2; }); |
1414 | if (it != end(buckets)) { |
1415 | DEBUG_PRINTF("deleting %zu singleton buckets\n" , |
1416 | distance(it, end(buckets))); |
1417 | buckets.erase(it, end(buckets)); |
1418 | } |
1419 | } |
1420 | |
1421 | static |
1422 | void buildInvBucketMap(const vector<vector<RoseVertex>> &buckets, |
1423 | unordered_map<RoseVertex, size_t> &inv) { |
1424 | inv.clear(); |
1425 | for (size_t i = 0; i < buckets.size(); i++) { |
1426 | for (auto v : buckets[i]) { |
1427 | assert(!contains(inv, v)); |
1428 | inv.emplace(v, i); |
1429 | } |
1430 | } |
1431 | } |
1432 | |
1433 | /** |
1434 | * \brief Generic splitter that will use the given split function to partition |
1435 | * the vector of buckets, then remove buckets with <= 1 entry. |
1436 | */ |
1437 | template <class SplitFunction> |
1438 | void splitAndFilterBuckets(vector<vector<RoseVertex>> &buckets, |
1439 | const SplitFunction &make_split_key) { |
1440 | if (buckets.empty()) { |
1441 | return; |
1442 | } |
1443 | |
1444 | vector<vector<RoseVertex>> out; |
1445 | |
1446 | // Mapping from split key value to new bucket index. |
1447 | using key_type = decltype(make_split_key(RoseGraph::null_vertex())); |
1448 | unordered_map<key_type, size_t> dest_map; |
1449 | dest_map.reserve(buckets.front().size()); |
1450 | |
1451 | for (const auto &bucket : buckets) { |
1452 | assert(!bucket.empty()); |
1453 | dest_map.clear(); |
1454 | for (RoseVertex v : bucket) { |
1455 | auto p = dest_map.emplace(make_split_key(v), out.size()); |
1456 | if (p.second) { // New key, add a bucket. |
1457 | out.emplace_back(); |
1458 | } |
1459 | auto out_bucket = p.first->second; |
1460 | out[out_bucket].push_back(v); |
1461 | } |
1462 | } |
1463 | |
1464 | if (out.size() == buckets.size()) { |
1465 | return; // No new buckets created. |
1466 | } |
1467 | |
1468 | buckets = std::move(out); |
1469 | removeSingletonBuckets(buckets); |
1470 | } |
1471 | |
1472 | static |
1473 | void splitByReportSuffixBehaviour(const RoseGraph &g, |
1474 | vector<vector<RoseVertex>> &buckets) { |
1475 | // Split by report set and suffix info. |
1476 | auto make_split_key = [&g](RoseVertex v) { |
1477 | return hash_all(g[v].reports, g[v].suffix); |
1478 | }; |
1479 | splitAndFilterBuckets(buckets, make_split_key); |
1480 | } |
1481 | |
1482 | static |
1483 | void splitByLiteralTable(const RoseBuildImpl &build, |
1484 | vector<vector<RoseVertex>> &buckets) { |
1485 | const RoseGraph &g = build.g; |
1486 | |
1487 | // Split by literal table. |
1488 | auto make_split_key = [&](RoseVertex v) { |
1489 | const auto &lits = g[v].literals; |
1490 | assert(!lits.empty()); |
1491 | auto table = build.literals.at(*lits.begin()).table; |
1492 | return std::underlying_type<decltype(table)>::type(table); |
1493 | }; |
1494 | splitAndFilterBuckets(buckets, make_split_key); |
1495 | } |
1496 | |
1497 | static |
1498 | void splitByNeighbour(const RoseGraph &g, vector<vector<RoseVertex>> &buckets, |
1499 | unordered_map<RoseVertex, size_t> &inv, bool succ) { |
1500 | vector<vector<RoseVertex>> ; |
1501 | map<size_t, vector<RoseVertex>> neighbours_by_bucket; |
1502 | set<RoseVertex> picked; |
1503 | vector<RoseVertex> leftovers; |
1504 | |
1505 | for (RoseVertex u : vertices_range(g)) { |
1506 | /* once split by v, stays split. also keeps iterator in buckets valid */ |
1507 | extras.clear(); |
1508 | neighbours_by_bucket.clear(); |
1509 | if (succ) { |
1510 | /* forward pass */ |
1511 | for (RoseVertex v : adjacent_vertices_range(u, g)) { |
1512 | auto it = inv.find(v); |
1513 | if (it != end(inv)) { |
1514 | neighbours_by_bucket[it->second].push_back(v); |
1515 | } |
1516 | } |
1517 | } else { |
1518 | /* backward pass */ |
1519 | for (RoseVertex v : inv_adjacent_vertices_range(u, g)) { |
1520 | auto it = inv.find(v); |
1521 | if (it != end(inv)) { |
1522 | neighbours_by_bucket[it->second].push_back(v); |
1523 | } |
1524 | } |
1525 | } |
1526 | for (const auto &e : neighbours_by_bucket) { |
1527 | size_t old_key = e.first; |
1528 | if (buckets[old_key].size() == e.second.size()) { |
1529 | /* did not split */ |
1530 | continue; |
1531 | } |
1532 | assert(!e.second.empty()); |
1533 | |
1534 | picked.clear(); |
1535 | picked.insert(begin(e.second), end(e.second)); |
1536 | |
1537 | size_t new_key = buckets.size() + extras.size(); |
1538 | leftovers.clear(); |
1539 | for (RoseVertex v : buckets[old_key]) { |
1540 | if (contains(picked, v)) { |
1541 | inv[v] = new_key; |
1542 | } else { |
1543 | leftovers.push_back(v); |
1544 | } |
1545 | } |
1546 | |
1547 | assert(!leftovers.empty()); |
1548 | assert(e.second.size() + leftovers.size() |
1549 | == buckets[old_key].size()); |
1550 | extras.push_back(e.second); |
1551 | buckets[old_key].swap(leftovers); |
1552 | } |
1553 | insert(&buckets, buckets.end(), extras); |
1554 | } |
1555 | |
1556 | removeSingletonBuckets(buckets); |
1557 | buildInvBucketMap(buckets, inv); |
1558 | } |
1559 | |
1560 | static |
1561 | vector<vector<RoseVertex>> |
1562 | splitDiamondMergeBuckets(CandidateSet &candidates, const RoseBuildImpl &build) { |
1563 | const RoseGraph &g = build.g; |
1564 | |
1565 | vector<vector<RoseVertex>> buckets(1); |
1566 | buckets[0].reserve(candidates.size()); |
1567 | insert(&buckets[0], buckets[0].end(), candidates); |
1568 | |
1569 | DEBUG_PRINTF("at start, %zu candidates in 1 bucket\n" , candidates.size()); |
1570 | |
1571 | splitByReportSuffixBehaviour(g, buckets); |
1572 | DEBUG_PRINTF("split by report/suffix, %zu buckets\n" , buckets.size()); |
1573 | if (buckets.empty()) { |
1574 | return buckets; |
1575 | } |
1576 | |
1577 | splitByLiteralTable(build, buckets); |
1578 | DEBUG_PRINTF("split by lit table, %zu buckets\n" , buckets.size()); |
1579 | if (buckets.empty()) { |
1580 | return buckets; |
1581 | } |
1582 | |
1583 | // Neighbour splits require inverse map. |
1584 | unordered_map<RoseVertex, size_t> inv; |
1585 | buildInvBucketMap(buckets, inv); |
1586 | |
1587 | splitByNeighbour(g, buckets, inv, true); |
1588 | DEBUG_PRINTF("split by successor, %zu buckets\n" , buckets.size()); |
1589 | if (buckets.empty()) { |
1590 | return buckets; |
1591 | } |
1592 | |
1593 | splitByNeighbour(g, buckets, inv, false); |
1594 | DEBUG_PRINTF("split by predecessor, %zu buckets\n" , buckets.size()); |
1595 | |
1596 | return buckets; |
1597 | } |
1598 | |
1599 | static never_inline |
1600 | void diamondMergePass(CandidateSet &candidates, RoseBuildImpl &build, |
1601 | vector<RoseVertex> *dead, bool mergeRoses, |
1602 | RoseAliasingInfo &rai) { |
1603 | DEBUG_PRINTF("begin\n" ); |
1604 | RoseGraph &g = build.g; |
1605 | |
1606 | if (candidates.empty()) { |
1607 | return; |
1608 | } |
1609 | |
1610 | /* Vertices may only be diamond merged with others in the same bucket */ |
1611 | auto cand_buckets = splitDiamondMergeBuckets(candidates, build); |
1612 | |
1613 | for (const vector<RoseVertex> &siblings : cand_buckets) { |
1614 | for (auto it = siblings.begin(); it != siblings.end();) { |
1615 | RoseVertex a = *it; |
1616 | ++it; |
1617 | |
1618 | assert(contains(candidates, a)); |
1619 | |
1620 | DEBUG_PRINTF("trying to merge %zu into somebody\n" , g[a].index); |
1621 | for (auto jt = it; jt != siblings.end(); ++jt) { |
1622 | RoseVertex b = *jt; |
1623 | assert(contains(candidates, b)); |
1624 | |
1625 | if (!sameRoleProperties(build, rai, a, b)) { |
1626 | DEBUG_PRINTF("diff role prop\n" ); |
1627 | continue; |
1628 | } |
1629 | |
1630 | // Check "diamond" requirements: must have same right side |
1631 | // (successors, reports) and left side (predecessors). |
1632 | /* Note: bucketing does not check edge properties (bounds, tops) |
1633 | * so we still have to checks successors and predecessors. */ |
1634 | |
1635 | if (!sameSuccessors(a, b, g) |
1636 | || !sameRightRoleProperties(build, a, b) |
1637 | || !samePredecessors(a, b, g)) { |
1638 | DEBUG_PRINTF("not diamond\n" ); |
1639 | continue; |
1640 | } |
1641 | |
1642 | if (!canMergeLiterals(a, b, build)) { |
1643 | DEBUG_PRINTF("incompatible lits\n" ); |
1644 | continue; |
1645 | } |
1646 | |
1647 | if (!attemptRoseMerge(build, true, a, b, !mergeRoses, rai)) { |
1648 | DEBUG_PRINTF("rose fail\n" ); |
1649 | continue; |
1650 | } |
1651 | |
1652 | mergeVerticesDiamond(a, b, build, rai); |
1653 | dead->push_back(a); |
1654 | candidates.erase(a); |
1655 | break; // next a |
1656 | } |
1657 | } |
1658 | } |
1659 | |
1660 | DEBUG_PRINTF("%zu candidates remaining\n" , candidates.size()); |
1661 | } |
1662 | |
1663 | static |
1664 | vector<RoseVertex>::iterator findLeftMergeSibling( |
1665 | vector<RoseVertex>::iterator it, |
1666 | const vector<RoseVertex>::iterator &end, |
1667 | const RoseVertex a, const RoseBuildImpl &build, |
1668 | const RoseAliasingInfo &rai, |
1669 | const CandidateSet &candidates) { |
1670 | const RoseGraph &g = build.g; |
1671 | |
1672 | for (; it != end; ++it) { |
1673 | RoseVertex b = *it; |
1674 | if (a == b) { |
1675 | continue; |
1676 | } |
1677 | |
1678 | if (!contains(candidates, b)) { |
1679 | continue; |
1680 | } |
1681 | |
1682 | if (!sameRoleProperties(build, rai, a, b)) { |
1683 | continue; |
1684 | } |
1685 | |
1686 | // Check left-equivalence: must have same predecessors and same |
1687 | // literals. |
1688 | |
1689 | if (g[a].literals != g[b].literals) { |
1690 | continue; |
1691 | } |
1692 | |
1693 | if (!samePredecessors(a, b, g)) { |
1694 | continue; |
1695 | } |
1696 | |
1697 | if (hasCommonSuccWithBadBounds(a, b, g)) { |
1698 | continue; |
1699 | } |
1700 | |
1701 | if (g[a].suffix && g[b].suffix && g[a].suffix != g[b].suffix) { |
1702 | continue; /* we can only trigger one suffix */ |
1703 | } |
1704 | |
1705 | return it; |
1706 | } |
1707 | |
1708 | return end; |
1709 | } |
1710 | |
1711 | static |
1712 | void getLeftMergeSiblings(const RoseBuildImpl &build, RoseVertex a, |
1713 | vector<RoseVertex> &siblings) { |
1714 | // We have to find a sibling to merge `a' with, and we select between |
1715 | // two approaches to minimize the number of vertices we have to |
1716 | // examine; which we use depends on the shape of the graph. |
1717 | |
1718 | const RoseGraph &g = build.g; |
1719 | assert(!g[a].literals.empty()); |
1720 | u32 lit_id = *g[a].literals.begin(); |
1721 | const auto &verts = build.literal_info.at(lit_id).vertices; |
1722 | RoseVertex pred = pickPred(a, g, build); |
1723 | |
1724 | siblings.clear(); |
1725 | |
1726 | if (pred == RoseGraph::null_vertex() || build.isAnyStart(pred) || |
1727 | out_degree(pred, g) > verts.size()) { |
1728 | // Select sibling from amongst the vertices that share a literal. |
1729 | insert(&siblings, siblings.end(), verts); |
1730 | } else { |
1731 | // Select sibling from amongst the vertices that share a |
1732 | // predecessor. |
1733 | insert(&siblings, siblings.end(), adjacent_vertices(pred, g)); |
1734 | } |
1735 | } |
1736 | |
1737 | static never_inline |
1738 | void leftMergePass(CandidateSet &candidates, RoseBuildImpl &build, |
1739 | vector<RoseVertex> *dead, RoseAliasingInfo &rai) { |
1740 | DEBUG_PRINTF("begin (%zu)\n" , candidates.size()); |
1741 | vector<RoseVertex> siblings; |
1742 | |
1743 | auto it = candidates.begin(); |
1744 | while (it != candidates.end()) { |
1745 | RoseVertex a = *it; |
1746 | CandidateSet::iterator ait = it; |
1747 | ++it; |
1748 | |
1749 | getLeftMergeSiblings(build, a, siblings); |
1750 | |
1751 | auto jt = siblings.begin(); |
1752 | while (jt != siblings.end()) { |
1753 | jt = findLeftMergeSibling(jt, siblings.end(), a, build, rai, |
1754 | candidates); |
1755 | if (jt == siblings.end()) { |
1756 | break; |
1757 | } |
1758 | RoseVertex b = *jt; |
1759 | if (attemptRoseMerge(build, true, a, b, false, rai)) { |
1760 | mergeVerticesLeft(a, b, build, rai); |
1761 | dead->push_back(a); |
1762 | candidates.erase(ait); |
1763 | break; // consider next a |
1764 | } |
1765 | ++jt; |
1766 | } |
1767 | } |
1768 | |
1769 | DEBUG_PRINTF("%zu candidates remaining\n" , candidates.size()); |
1770 | assert(!hasOrphanedTops(build)); |
1771 | } |
1772 | |
1773 | // Can't merge vertices with different root predecessors. |
1774 | static |
1775 | bool safeRootPreds(RoseVertex a, RoseVertex b, const RoseGraph &g) { |
1776 | set<RoseVertex> a_roots, b_roots; |
1777 | |
1778 | for (auto u : inv_adjacent_vertices_range(a, g)) { |
1779 | if (!in_degree(u, g)) { |
1780 | a_roots.insert(u); |
1781 | } |
1782 | } |
1783 | for (auto u : inv_adjacent_vertices_range(b, g)) { |
1784 | if (!in_degree(u, g)) { |
1785 | b_roots.insert(u); |
1786 | } |
1787 | } |
1788 | |
1789 | assert(a_roots.size() <= 1); |
1790 | assert(b_roots.size() <= 1); |
1791 | |
1792 | return a_roots == b_roots; |
1793 | } |
1794 | |
1795 | static never_inline |
1796 | vector<RoseVertex>::const_iterator findRightMergeSibling( |
1797 | vector<RoseVertex>::const_iterator it, |
1798 | const vector<RoseVertex>::const_iterator &end, |
1799 | const RoseVertex a, const RoseBuildImpl &build, |
1800 | const RoseAliasingInfo &rai, |
1801 | const CandidateSet &candidates) { |
1802 | const RoseGraph &g = build.g; |
1803 | |
1804 | for (; it != end; ++it) { |
1805 | RoseVertex b = *it; |
1806 | if (a == b) { |
1807 | continue; |
1808 | } |
1809 | |
1810 | if (!contains(candidates, b)) { |
1811 | continue; |
1812 | } |
1813 | |
1814 | if (!sameRoleProperties(build, rai, a, b)) { |
1815 | continue; |
1816 | } |
1817 | |
1818 | // Check right-equivalence: must have same successors, reports and same |
1819 | // literals. |
1820 | |
1821 | if (g[a].literals != g[b].literals) { |
1822 | continue; |
1823 | } |
1824 | |
1825 | if (!sameSuccessors(a, b, g) |
1826 | || !sameRightRoleProperties(build, a, b)) { |
1827 | continue; |
1828 | } |
1829 | |
1830 | // An extra wrinkle: we cannot merge two vertices that are root |
1831 | // successors if their preds are different. (e.g. one is anchored and |
1832 | // one is not) |
1833 | if (!safeRootPreds(a, b, g)) { |
1834 | continue; |
1835 | } |
1836 | |
1837 | if (hasCommonPredWithBadBounds(a, b, g)) { |
1838 | continue; |
1839 | } |
1840 | |
1841 | if (hasCommonPredWithDiffRoses(a, b, g)) { |
1842 | continue; |
1843 | } |
1844 | |
1845 | return it; |
1846 | } |
1847 | |
1848 | return end; |
1849 | } |
1850 | |
1851 | static |
1852 | void splitByRightProps(const RoseGraph &g, |
1853 | vector<vector<RoseVertex>> &buckets) { |
1854 | // Successor vector used in make_split_key. We declare it here so we can |
1855 | // reuse storage. |
1856 | vector<RoseVertex> succ; |
1857 | |
1858 | // Split by {successors, literals, reports}. |
1859 | auto make_split_key = [&](RoseVertex v) { |
1860 | succ.clear(); |
1861 | insert(&succ, succ.end(), adjacent_vertices(v, g)); |
1862 | sort(succ.begin(), succ.end()); |
1863 | return hash_all(g[v].literals, g[v].reports, succ); |
1864 | }; |
1865 | splitAndFilterBuckets(buckets, make_split_key); |
1866 | } |
1867 | |
1868 | static never_inline |
1869 | vector<vector<RoseVertex>> |
1870 | splitRightMergeBuckets(const CandidateSet &candidates, |
1871 | const RoseBuildImpl &build) { |
1872 | const RoseGraph &g = build.g; |
1873 | |
1874 | vector<vector<RoseVertex>> buckets(1); |
1875 | buckets[0].reserve(candidates.size()); |
1876 | insert(&buckets[0], buckets[0].end(), candidates); |
1877 | |
1878 | DEBUG_PRINTF("at start, %zu candidates in 1 bucket\n" , candidates.size()); |
1879 | |
1880 | splitByReportSuffixBehaviour(g, buckets); |
1881 | DEBUG_PRINTF("split by report/suffix, %zu buckets\n" , buckets.size()); |
1882 | if (buckets.empty()) { |
1883 | return buckets; |
1884 | } |
1885 | |
1886 | splitByRightProps(g, buckets); |
1887 | DEBUG_PRINTF("split by right-merge properties, %zu buckets\n" , |
1888 | buckets.size()); |
1889 | if (buckets.empty()) { |
1890 | return buckets; |
1891 | } |
1892 | |
1893 | return buckets; |
1894 | } |
1895 | |
1896 | static never_inline |
1897 | void rightMergePass(CandidateSet &candidates, RoseBuildImpl &build, |
1898 | vector<RoseVertex> *dead, bool mergeRoses, |
1899 | RoseAliasingInfo &rai) { |
1900 | DEBUG_PRINTF("begin\n" ); |
1901 | |
1902 | if (candidates.empty()) { |
1903 | return; |
1904 | } |
1905 | |
1906 | auto buckets = splitRightMergeBuckets(candidates, build); |
1907 | |
1908 | for (const auto &bucket : buckets) { |
1909 | assert(!bucket.empty()); |
1910 | for (auto it = bucket.begin(); it != bucket.end(); it++) { |
1911 | RoseVertex a = *it; |
1912 | for (auto jt = bucket.begin(); jt != bucket.end(); jt++) { |
1913 | jt = findRightMergeSibling(jt, bucket.end(), a, build, rai, |
1914 | candidates); |
1915 | if (jt == bucket.end()) { |
1916 | break; |
1917 | } |
1918 | RoseVertex b = *jt; |
1919 | if (attemptRoseMerge(build, false, a, b, !mergeRoses, rai)) { |
1920 | mergeVerticesRight(a, b, build, rai); |
1921 | dead->push_back(a); |
1922 | candidates.erase(a); |
1923 | break; // consider next a |
1924 | } |
1925 | } |
1926 | } |
1927 | } |
1928 | |
1929 | DEBUG_PRINTF("%zu candidates remaining\n" , candidates.size()); |
1930 | assert(!hasOrphanedTops(build)); |
1931 | } |
1932 | |
1933 | /** |
1934 | * \brief True if the given vertex has no siblings for the purposes of a |
1935 | * diamond merge. |
1936 | * |
1937 | * This is the case if it has no successors with more than one predecessor |
1938 | * (itself), or no predecessors with more than one successor (itself). |
1939 | */ |
1940 | static |
1941 | bool hasNoDiamondSiblings(const RoseGraph &g, RoseVertex v) { |
1942 | if (has_successor(v, g)) { |
1943 | bool only_succ = true; |
1944 | for (const auto &w : adjacent_vertices_range(v, g)) { |
1945 | if (in_degree(w, g) > 1) { |
1946 | only_succ = false; |
1947 | break; |
1948 | } |
1949 | } |
1950 | if (only_succ) { |
1951 | return true; |
1952 | } |
1953 | } |
1954 | |
1955 | // Any candidate vertex will have a predecessor; the only vertices without |
1956 | // preds are the root vertices. |
1957 | assert(in_edges(v, g).first != in_edges(v, g).second); |
1958 | |
1959 | bool only_pred = true; |
1960 | for (const auto &u : inv_adjacent_vertices_range(v, g)) { |
1961 | if (out_degree(u, g) > 1) { |
1962 | only_pred = false; |
1963 | break; |
1964 | } |
1965 | } |
1966 | |
1967 | return only_pred; |
1968 | } |
1969 | |
1970 | /** |
1971 | * \brief Filter out some merge candidates that are not mergeable by a diamond |
1972 | * merge. |
1973 | */ |
1974 | static |
1975 | void filterDiamondCandidates(RoseGraph &g, CandidateSet &candidates) { |
1976 | DEBUG_PRINTF("%zu candidates enter\n" , candidates.size()); |
1977 | |
1978 | vector<RoseVertex> dead; |
1979 | for (const auto &v : candidates) { |
1980 | if (hasNoDiamondSiblings(g, v)) { |
1981 | dead.push_back(v); |
1982 | } |
1983 | } |
1984 | |
1985 | for (const auto &v : dead) { |
1986 | candidates.erase(v); |
1987 | } |
1988 | |
1989 | DEBUG_PRINTF("pruned %zu candidates, leaving %zu\n" , dead.size(), |
1990 | candidates.size()); |
1991 | } |
1992 | |
1993 | void aliasRoles(RoseBuildImpl &build, bool mergeRoses) { |
1994 | const CompileContext &cc = build.cc; |
1995 | RoseGraph &g = build.g; |
1996 | assert(!hasOrphanedTops(build)); |
1997 | assert(canImplementGraphs(build)); |
1998 | |
1999 | if (!cc.grey.roseRoleAliasing || !cc.grey.roseGraphReduction) { |
2000 | return; |
2001 | } |
2002 | |
2003 | DEBUG_PRINTF("doing role aliasing mr=%d\n" , (int)mergeRoses); |
2004 | |
2005 | RoseAliasingInfo rai(build); |
2006 | |
2007 | mergeRoses &= cc.grey.mergeRose & cc.grey.roseMergeRosesDuringAliasing; |
2008 | |
2009 | CandidateSet candidates; |
2010 | findCandidates(build, &candidates); |
2011 | |
2012 | DEBUG_PRINTF("candidates %zu\n" , candidates.size()); |
2013 | |
2014 | vector<RoseVertex> dead; |
2015 | size_t old_dead_size = 0; |
2016 | do { |
2017 | old_dead_size = dead.size(); |
2018 | leftMergePass(candidates, build, &dead, rai); |
2019 | rightMergePass(candidates, build, &dead, mergeRoses, rai); |
2020 | } while (old_dead_size != dead.size()); |
2021 | |
2022 | /* Diamond merge passes cannot create extra merges as they require the same |
2023 | * succ and preds before merging --> that if a succ/pred was ineligible due |
2024 | * to a merge to different pred/succ before a diamond merge, it will still |
2025 | * be afterwards. */ |
2026 | filterDiamondCandidates(g, candidates); |
2027 | diamondMergePass(candidates, build, &dead, mergeRoses, rai); |
2028 | |
2029 | DEBUG_PRINTF("killed %zu vertices\n" , dead.size()); |
2030 | build.removeVertices(dead); |
2031 | assert(!hasOrphanedTops(build)); |
2032 | assert(canImplementGraphs(build)); |
2033 | } |
2034 | |
2035 | namespace { |
2036 | struct DupeLeafKey { |
2037 | explicit DupeLeafKey(const RoseVertexProps &litv) |
2038 | : literals(litv.literals), reports(litv.reports), |
2039 | eod_accept(litv.eod_accept), suffix(litv.suffix), left(litv.left), |
2040 | som_adjust(litv.som_adjust) { |
2041 | DEBUG_PRINTF("eod_accept %d\n" , (int)eod_accept); |
2042 | DEBUG_PRINTF("report %u\n" , left.leftfix_report); |
2043 | DEBUG_PRINTF("lag %u\n" , left.lag); |
2044 | } |
2045 | |
2046 | bool operator<(const DupeLeafKey &b) const { |
2047 | const DupeLeafKey &a = *this; |
2048 | ORDER_CHECK(literals); |
2049 | ORDER_CHECK(eod_accept); |
2050 | ORDER_CHECK(suffix); |
2051 | ORDER_CHECK(reports); |
2052 | ORDER_CHECK(som_adjust); |
2053 | ORDER_CHECK(left.leftfix_report); |
2054 | ORDER_CHECK(left.lag); |
2055 | return false; |
2056 | } |
2057 | |
2058 | flat_set<u32> literals; |
2059 | flat_set<ReportID> reports; |
2060 | bool eod_accept; |
2061 | suffix_id suffix; |
2062 | LeftEngInfo left; |
2063 | u32 som_adjust; |
2064 | }; |
2065 | |
2066 | struct UncalcLeafKey { |
2067 | UncalcLeafKey(const RoseGraph &g, RoseVertex v) |
2068 | : literals(g[v].literals), rose(g[v].left) { |
2069 | for (const auto &e : in_edges_range(v, g)) { |
2070 | RoseVertex u = source(e, g); |
2071 | preds.insert(make_pair(u, g[e])); |
2072 | } |
2073 | } |
2074 | |
2075 | bool operator<(const UncalcLeafKey &b) const { |
2076 | const UncalcLeafKey &a = *this; |
2077 | ORDER_CHECK(literals); |
2078 | ORDER_CHECK(preds); |
2079 | ORDER_CHECK(rose); |
2080 | return false; |
2081 | } |
2082 | |
2083 | flat_set<u32> literals; |
2084 | flat_set<pair<RoseVertex, RoseEdgeProps>> preds; |
2085 | LeftEngInfo rose; |
2086 | }; |
2087 | } // namespace |
2088 | |
2089 | /** |
2090 | * This function merges leaf vertices with the same literals and report |
2091 | * id/suffix. The leaf vertices of the graph are inspected and a mapping of |
2092 | * leaf vertex properties to vertices is built. If the same set of leaf |
2093 | * properties has already been seen when we inspect a vertex, we attempt to |
2094 | * merge the vertex in with the previously seen vertex. This process can fail |
2095 | * if the vertices share a common predecessor vertex but have a differing, |
2096 | * incompatible relationship (different bounds or infix) with the predecessor. |
2097 | * |
2098 | * This takes place after \ref dedupeSuffixes to increase effectiveness as the |
2099 | * same suffix is required for a merge to occur. |
2100 | * |
2101 | * TODO: work if this is a subset of role aliasing (and if it can be eliminated) |
2102 | * or clearly document cases that would not be covered by role aliasing. |
2103 | */ |
2104 | void mergeDupeLeaves(RoseBuildImpl &build) { |
2105 | map<DupeLeafKey, RoseVertex> leaves; |
2106 | vector<RoseVertex> changed; |
2107 | |
2108 | RoseGraph &g = build.g; |
2109 | for (auto v : vertices_range(g)) { |
2110 | if (in_degree(v, g) == 0) { |
2111 | assert(build.isAnyStart(v)); |
2112 | continue; |
2113 | } |
2114 | |
2115 | DEBUG_PRINTF("inspecting vertex index=%zu in_degree %zu " |
2116 | "out_degree %zu\n" , g[v].index, in_degree(v, g), |
2117 | out_degree(v, g)); |
2118 | |
2119 | // Vertex must be a reporting leaf node |
2120 | if (g[v].reports.empty() || !isLeafNode(v, g)) { |
2121 | continue; |
2122 | } |
2123 | |
2124 | // At the moment, we ignore all successors of root or anchored_root, |
2125 | // since many parts of our runtime assume that these have in-degree 1. |
2126 | if (build.isRootSuccessor(v)) { |
2127 | continue; |
2128 | } |
2129 | |
2130 | DupeLeafKey dupe(g[v]); |
2131 | if (leaves.find(dupe) == leaves.end()) { |
2132 | leaves.insert(make_pair(dupe, v)); |
2133 | continue; |
2134 | } |
2135 | |
2136 | RoseVertex t = leaves.find(dupe)->second; |
2137 | DEBUG_PRINTF("found two leaf dupe roles, index=%zu,%zu\n" , g[v].index, |
2138 | g[t].index); |
2139 | |
2140 | vector<RoseEdge> deadEdges; |
2141 | for (const auto &e : in_edges_range(v, g)) { |
2142 | RoseVertex u = source(e, g); |
2143 | DEBUG_PRINTF("u index=%zu\n" , g[u].index); |
2144 | if (RoseEdge et = edge(u, t, g)) { |
2145 | if (g[et].minBound <= g[e].minBound |
2146 | && g[et].maxBound >= g[e].maxBound) { |
2147 | DEBUG_PRINTF("remove more constrained edge\n" ); |
2148 | deadEdges.push_back(e); |
2149 | } |
2150 | } else { |
2151 | DEBUG_PRINTF("rehome edge: add %zu->%zu\n" , g[u].index, |
2152 | g[t].index); |
2153 | add_edge(u, t, g[e], g); |
2154 | deadEdges.push_back(e); |
2155 | } |
2156 | } |
2157 | |
2158 | if (!deadEdges.empty()) { |
2159 | for (auto &e : deadEdges) { |
2160 | remove_edge(e, g); |
2161 | } |
2162 | changed.push_back(v); |
2163 | g[t].min_offset = min(g[t].min_offset, g[v].min_offset); |
2164 | g[t].max_offset = max(g[t].max_offset, g[v].max_offset); |
2165 | } |
2166 | } |
2167 | DEBUG_PRINTF("find loop done\n" ); |
2168 | |
2169 | // Remove any vertices that now have no in-edges. |
2170 | size_t countRemovals = 0; |
2171 | for (size_t i = 0; i < changed.size(); i++) { |
2172 | RoseVertex v = changed[i]; |
2173 | if (in_degree(v, g) == 0) { |
2174 | DEBUG_PRINTF("remove vertex\n" ); |
2175 | if (!build.isVirtualVertex(v)) { |
2176 | for (u32 lit_id : g[v].literals) { |
2177 | build.literal_info[lit_id].vertices.erase(v); |
2178 | } |
2179 | } |
2180 | remove_vertex(v, g); |
2181 | countRemovals++; |
2182 | } |
2183 | } |
2184 | |
2185 | // if we've removed anything, we need to renumber vertices |
2186 | if (countRemovals) { |
2187 | renumber_vertices(g); |
2188 | DEBUG_PRINTF("removed %zu vertices.\n" , countRemovals); |
2189 | } |
2190 | } |
2191 | |
2192 | /** Merges the suffixes on the (identical) vertices in \a vcluster, used by |
2193 | * \ref uncalcLeaves. */ |
2194 | static |
2195 | void mergeCluster(RoseGraph &g, const ReportManager &rm, |
2196 | const vector<RoseVertex> &vcluster, |
2197 | vector<RoseVertex> &dead, const CompileContext &cc) { |
2198 | if (vcluster.size() <= 1) { |
2199 | return; // No merge to perform. |
2200 | } |
2201 | |
2202 | // Note that we batch merges up fairly crudely for performance reasons. |
2203 | vector<RoseVertex>::const_iterator it = vcluster.begin(), it2; |
2204 | while (it != vcluster.end()) { |
2205 | vector<NGHolder *> cluster; |
2206 | map<NGHolder *, RoseVertex> rev; |
2207 | |
2208 | for (it2 = it; |
2209 | it2 != vcluster.end() && cluster.size() < MERGE_GROUP_SIZE_MAX; |
2210 | ++it2) { |
2211 | RoseVertex v = *it2; |
2212 | NGHolder *h = g[v].suffix.graph.get(); |
2213 | assert(!g[v].suffix.haig); /* should not be here if haig */ |
2214 | rev[h] = v; |
2215 | cluster.push_back(h); |
2216 | } |
2217 | it = it2; |
2218 | |
2219 | DEBUG_PRINTF("merging cluster %zu\n" , cluster.size()); |
2220 | auto merged = mergeNfaCluster(cluster, &rm, cc); |
2221 | DEBUG_PRINTF("done\n" ); |
2222 | |
2223 | for (const auto &m : merged) { |
2224 | NGHolder *h_victim = m.first; // mergee |
2225 | NGHolder *h_winner = m.second; |
2226 | RoseVertex victim = rev[h_victim]; |
2227 | RoseVertex winner = rev[h_winner]; |
2228 | |
2229 | LIMIT_TO_AT_MOST(&g[winner].min_offset, g[victim].min_offset); |
2230 | ENSURE_AT_LEAST(&g[winner].max_offset, g[victim].max_offset); |
2231 | insert(&g[winner].reports, g[victim].reports); |
2232 | |
2233 | dead.push_back(victim); |
2234 | } |
2235 | } |
2236 | } |
2237 | |
2238 | static |
2239 | void findUncalcLeavesCandidates(RoseBuildImpl &build, |
2240 | map<UncalcLeafKey, vector<RoseVertex> > &clusters, |
2241 | deque<UncalcLeafKey> &ordered) { |
2242 | const RoseGraph &g = build.g; |
2243 | |
2244 | vector<RoseVertex> suffix_vertices; // vertices with suffix graphs |
2245 | unordered_map<const NGHolder *, u32> fcount; // ref count per graph |
2246 | |
2247 | for (auto v : vertices_range(g)) { |
2248 | if (g[v].suffix) { |
2249 | if (!g[v].suffix.graph) { |
2250 | continue; /* cannot uncalc (haig/mcclellan); TODO */ |
2251 | } |
2252 | |
2253 | assert(g[v].suffix.graph->kind == NFA_SUFFIX); |
2254 | |
2255 | // Ref count all suffixes, as we don't want to merge a suffix |
2256 | // that happens to be shared with a non-leaf vertex somewhere. |
2257 | DEBUG_PRINTF("vertex %zu has suffix %p\n" , g[v].index, |
2258 | g[v].suffix.graph.get()); |
2259 | fcount[g[v].suffix.graph.get()]++; |
2260 | |
2261 | // Vertex must be a reporting pseudo accept |
2262 | if (!isLeafNode(v, g)) { |
2263 | continue; |
2264 | } |
2265 | |
2266 | suffix_vertices.push_back(v); |
2267 | } |
2268 | } |
2269 | |
2270 | for (auto v : suffix_vertices) { |
2271 | if (in_degree(v, g) == 0) { |
2272 | assert(build.isAnyStart(v)); |
2273 | continue; |
2274 | } |
2275 | |
2276 | const NGHolder *h = g[v].suffix.graph.get(); |
2277 | assert(h); |
2278 | DEBUG_PRINTF("suffix %p\n" , h); |
2279 | |
2280 | // We can't easily merge suffixes shared with other vertices, and |
2281 | // creating a unique copy to do so may just mean we end up tracking |
2282 | // more NFAs. Better to leave shared suffixes alone. |
2283 | if (fcount[h] != 1) { |
2284 | DEBUG_PRINTF("skipping shared suffix\n" ); |
2285 | continue; |
2286 | } |
2287 | |
2288 | UncalcLeafKey key(g, v); |
2289 | vector<RoseVertex> &vec = clusters[key]; |
2290 | if (vec.empty()) { |
2291 | |
2292 | ordered.push_back(key); |
2293 | } |
2294 | vec.push_back(v); |
2295 | } |
2296 | |
2297 | DEBUG_PRINTF("find loop done\n" ); |
2298 | } |
2299 | |
2300 | /** |
2301 | * This function attempts to combine identical roles (same literals, same |
2302 | * predecessors, etc) with different suffixes into a single role which |
2303 | * activates a larger suffix. The leaf vertices of the graph with a suffix are |
2304 | * grouped into clusters which have members triggered by identical roles. The |
2305 | * \ref mergeNfaCluster function (from ng_uncalc_components) is then utilised |
2306 | * to build a set of larger (and still implementable) suffixes. The graph is |
2307 | * then updated to point to the new suffixes and any unneeded roles are |
2308 | * removed. |
2309 | * |
2310 | * Note: suffixes which are shared amongst multiple roles are not considered |
2311 | * for this pass as the individual suffixes would have to continue to exist for |
2312 | * the other roles to trigger resulting in the transformation not producing any |
2313 | * savings. |
2314 | * |
2315 | * Note: as \ref mergeNfaCluster is slow when the cluster sizes are large, |
2316 | * clusters of more than \ref MERGE_GROUP_SIZE_MAX roles are split into smaller |
2317 | * chunks for processing. |
2318 | */ |
2319 | void uncalcLeaves(RoseBuildImpl &build) { |
2320 | DEBUG_PRINTF("uncalcing\n" ); |
2321 | |
2322 | map<UncalcLeafKey, vector<RoseVertex> > clusters; |
2323 | deque<UncalcLeafKey> ordered; |
2324 | findUncalcLeavesCandidates(build, clusters, ordered); |
2325 | |
2326 | vector<RoseVertex> dead; |
2327 | |
2328 | for (const auto &key : ordered) { |
2329 | DEBUG_PRINTF("cluster of size %zu\n" , clusters[key].size()); |
2330 | mergeCluster(build.g, build.rm, clusters[key], dead, build.cc); |
2331 | } |
2332 | build.removeVertices(dead); |
2333 | } |
2334 | |
2335 | } // namespace ue2 |
2336 | |