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
60using namespace std;
61using boost::adaptors::map_values;
62
63namespace ue2 {
64
65static constexpr size_t MERGE_GROUP_SIZE_MAX = 200;
66
67namespace {
68// Used for checking edge sets (both in- and out-) against each other.
69struct 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
99private:
100 RoseVertex v;
101 const RoseEdgeProps &eprops;
102};
103
104struct AliasOutEdge : EdgeAndVertex {
105 AliasOutEdge(const RoseEdge &e, const RoseGraph &g) :
106 EdgeAndVertex(e, target(e, g), g) {}
107};
108
109struct AliasInEdge : EdgeAndVertex {
110 AliasInEdge(const RoseEdge &e, const RoseGraph &g) :
111 EdgeAndVertex(e, source(e, g), g) {}
112};
113
114class CandidateSet {
115public:
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
155private:
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
161struct 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.
189static
190bool 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. */
210static
211bool 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.
236static
237bool 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
273static
274bool 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
292static
293bool 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
316static
317bool 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
347static
348bool 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
360static
361bool 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
391static
392bool 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. */
429static
430bool 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
459static
460void 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 */
478static
479void 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
525static
526void 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
538static
539void 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. */
563static
564void 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. */
589static
590void 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. */
611static
612void 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 */
629static
630void 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
646static never_inline
647void 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
661static
662RoseVertex 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
680template<>
681bool contains<>(const CandidateSet &container, const RoseVertex &key) {
682 return container.contains(key);
683}
684
685// Simplified version of hasCommonPredWithBadBounds for diamond merges.
686static
687bool 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
720static
721void 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. */
756static
757void 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. */
773static
774void 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
785static
786void 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
792static
793void 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
817static
818void 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
862static
863bool 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
925static
926bool 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
1121static
1122bool 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.
1346static
1347bool 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 */
1409static
1410void 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
1421static
1422void 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 */
1437template <class SplitFunction>
1438void 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
1472static
1473void 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
1482static
1483void 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
1497static
1498void splitByNeighbour(const RoseGraph &g, vector<vector<RoseVertex>> &buckets,
1499 unordered_map<RoseVertex, size_t> &inv, bool succ) {
1500 vector<vector<RoseVertex>> extras;
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
1560static
1561vector<vector<RoseVertex>>
1562splitDiamondMergeBuckets(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
1599static never_inline
1600void 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
1663static
1664vector<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
1711static
1712void 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
1737static never_inline
1738void 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.
1774static
1775bool 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
1795static never_inline
1796vector<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
1851static
1852void 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
1868static never_inline
1869vector<vector<RoseVertex>>
1870splitRightMergeBuckets(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
1896static never_inline
1897void 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 */
1940static
1941bool 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 */
1974static
1975void 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
1993void 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
2035namespace {
2036struct 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
2066struct 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 */
2104void 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. */
2194static
2195void 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
2238static
2239void 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 */
2319void 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