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 { RoleInfoRoleInfo55 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