1 | /* |
2 | * Copyright (c) 2017, Intel Corporation |
3 | * |
4 | * Redistribution and use in source and binary forms, with or without |
5 | * modification, are permitted provided that the following conditions are met: |
6 | * |
7 | * * Redistributions of source code must retain the above copyright notice, |
8 | * this list of conditions and the following disclaimer. |
9 | * * Redistributions in binary form must reproduce the above copyright |
10 | * notice, this list of conditions and the following disclaimer in the |
11 | * documentation and/or other materials provided with the distribution. |
12 | * * Neither the name of Intel Corporation nor the names of its contributors |
13 | * may be used to endorse or promote products derived from this software |
14 | * without specific prior written permission. |
15 | * |
16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE |
20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
26 | * POSSIBILITY OF SUCH DAMAGE. |
27 | */ |
28 | |
29 | /** \file |
30 | * \brief exclusive analysis for infix and suffix engines. |
31 | * Two engines are considered as exclusive if they can never be alive |
32 | * at the same time. This analysis takes advantage of the property of |
33 | * triggering literal + engine graph. If the triggering literals of |
34 | * two engines can make all the states dead in each other's graph, |
35 | * then they are exclusive. |
36 | */ |
37 | #ifndef ROSE_BUILD_EXCLUSIVE_H |
38 | #define ROSE_BUILD_EXCLUSIVE_H |
39 | |
40 | #include "ue2common.h" |
41 | |
42 | #include "rose_build_impl.h" |
43 | #include "util/alloc.h" |
44 | #include "util/charreach.h" |
45 | |
46 | #include <map> |
47 | #include <set> |
48 | #include <vector> |
49 | |
50 | namespace ue2 { |
51 | |
52 | /** \brief role info structure for exclusive analysis */ |
53 | template<typename role_id> |
54 | struct RoleInfo { |
55 | RoleInfo(role_id role_in, u32 id_in) : role(role_in), id(id_in) {} |
56 | bool operator==(const RoleInfo &b) const { |
57 | return id == b.id; |
58 | } |
59 | bool operator!=(const RoleInfo &b) const { return !(*this == b); } |
60 | bool operator<(const RoleInfo &b) const { |
61 | const RoleInfo &a = *this; |
62 | if (a.score != b.score) { |
63 | return a.score > b.score; |
64 | } |
65 | ORDER_CHECK(id); |
66 | return false; |
67 | } |
68 | |
69 | std::vector<std::vector<CharReach>> literals; // prefix literals |
70 | CharReach prefix_cr; // reach of prefix literals |
71 | CharReach last_cr; // reach of the last character of literals |
72 | CharReach cr; // reach of engine graph |
73 | const role_id role; // infix or suffix info |
74 | const u32 id; // infix or suffix id |
75 | u32 score = ~0U; // score for exclusive analysis |
76 | }; |
77 | |
78 | /** |
79 | * \brief add triggering literals to infix info. |
80 | */ |
81 | bool setTriggerLiteralsInfix(RoleInfo<left_id> &roleInfo, |
82 | const std::map<u32, std::vector<std::vector<CharReach>>> &triggers); |
83 | |
84 | /** |
85 | * \brief add triggering literals to suffix info. |
86 | */ |
87 | bool setTriggerLiteralsSuffix(RoleInfo<suffix_id> &roleInfo, |
88 | const std::map<u32, std::vector<std::vector<CharReach>>> &triggers); |
89 | |
90 | /** |
91 | * Exclusive analysis for infix engines. |
92 | * |
93 | * @param build rose build info mainly used to set exclusive chunk size here |
94 | * @param vertex_map mapping between engine id and rose vertices |
95 | * related to this engine |
96 | * @param roleInfoSet structure contains role properties including infix info, |
97 | * triggering literals and literal reachabilities. |
98 | * Used for exclusive analysis. |
99 | * @param exclusive_roles output mapping between engine id and its exclusive |
100 | * group id |
101 | */ |
102 | void exclusiveAnalysisInfix(const RoseBuildImpl &build, |
103 | const std::map<u32, std::vector<RoseVertex>> &vertex_map, |
104 | std::set<RoleInfo<left_id>> &roleInfoSet, |
105 | std::vector<std::vector<u32>> &exclusive_roles); |
106 | |
107 | /** |
108 | * Exclusive analysis for suffix engines. |
109 | * |
110 | * @param build rose build info mainly used to set exclusive chunk size here |
111 | * @param vertex_map mapping between engine id and rose vertices |
112 | * related to this engine |
113 | * @param roleInfoSet structure contains role properties including suffix info, |
114 | * triggering literals and literal reachabilities. |
115 | * Used for exclusive analysis. |
116 | * @param exclusive_roles output mapping between engine id and its exclusive |
117 | * group id |
118 | */ |
119 | void exclusiveAnalysisSuffix(const RoseBuildImpl &build, |
120 | const std::map<u32, std::vector<RoseVertex>> &vertex_map, |
121 | std::set<RoleInfo<suffix_id>> &roleInfoSet, |
122 | std::vector<std::vector<u32>> &exclusive_roles); |
123 | |
124 | } // namespace ue2 |
125 | |
126 | #endif //ROSE_BUILD_EXCLUSIVE_H |
127 | |
128 | |