/* * Copyright (c) 2015-2017, Intel Corporation * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * * Redistributions of source code must retain the above copyright notice, * this list of conditions and the following disclaimer. * * Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * Neither the name of Intel Corporation nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGE. */ #ifndef GOUGHCOMPILE_INTERNAL_H #define GOUGHCOMPILE_INTERNAL_H #include "gough_internal.h" #include "mcclellancompile.h" #include "ue2common.h" #include "util/charreach.h" #include "util/flat_containers.h" #include "util/noncopyable.h" #include "util/order_check.h" #include <map> #include <memory> #include <set> #include <vector> #include <boost/graph/adjacency_list.hpp> namespace ue2 { struct Grey; struct GoughSSAVar; struct GoughSSAVarJoin; struct GoughVertexProps { GoughVertexProps() {} explicit GoughVertexProps(u32 state_in) : state_id(state_in) {} u32 state_id = ~0U; std::vector<std::shared_ptr<GoughSSAVarJoin> > vars; /* owns variables */ std::vector<std::pair<ReportID, GoughSSAVar *> > reports; /**< report som, som variable */ std::vector<std::pair<ReportID, GoughSSAVar *> > reports_eod; }; struct GoughEdgeProps { GoughEdgeProps(void) : top(false) {} bool top; CharReach reach; std::vector<std::shared_ptr<GoughSSAVar> > vars; /* owns variables */ }; struct GoughGraphProps { boost::adjacency_list_traits<boost::vecS, boost::vecS>::vertex_descriptor initial_vertex; /* for triggered nfas, dead state; * for others start anchored or start floating */ }; typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, GoughVertexProps, GoughEdgeProps, GoughGraphProps> GoughGraph; typedef GoughGraph::vertex_descriptor GoughVertex; typedef GoughGraph::edge_descriptor GoughEdge; struct gough_edge_id { gough_edge_id(const GoughGraph &g, const GoughEdge &e) : src(g[source(e, g)].state_id), dest(g[target(e, g)].state_id), first_char(g[e].reach.find_first()) {} bool operator<(const gough_edge_id &b) const { const gough_edge_id &a = *this; ORDER_CHECK(src); ORDER_CHECK(dest); ORDER_CHECK(first_char); return false; } const u32 src; const u32 dest; const u32 first_char; /* ~0U if only top */ }; struct GoughSSAVarWithInputs; struct GoughSSAVarMin; struct GoughSSAVarJoin; struct GoughSSAVar : noncopyable { GoughSSAVar(void) : seen(false), slot(INVALID_SLOT) {} virtual ~GoughSSAVar(); const flat_set<GoughSSAVar *> &get_inputs() const { return inputs; } const flat_set<GoughSSAVarWithInputs *> &get_outputs() const { return outputs; } virtual void replace_input(GoughSSAVar *old_v, GoughSSAVar *new_v) = 0; virtual void generate(std::vector<gough_ins> *out) const = 0; bool seen; /* for temp use by remove_dead alg */ u32 slot; void clear_outputs(); /** remove all inputs and outputs of the vertex, call before * removing vertex */ virtual void clear_all() { clear_outputs(); } protected: flat_set<GoughSSAVar *> inputs; flat_set<GoughSSAVarWithInputs *> outputs; friend struct GoughSSAVarWithInputs; friend struct GoughSSAVarMin; friend struct GoughSSAVarJoin; }; struct GoughSSAVarNew : public GoughSSAVar { explicit GoughSSAVarNew(u32 adjust_in) : adjust(adjust_in) {} void replace_input(GoughSSAVar *, GoughSSAVar *) override { assert(0); } void generate(std::vector<gough_ins> *out) const override; const u32 adjust; }; struct GoughSSAVarWithInputs : public GoughSSAVar { GoughSSAVarWithInputs(void) {} void replace_input(GoughSSAVar *old_v, GoughSSAVar *new_v) override = 0; virtual void clear_inputs() = 0; void clear_all() override; protected: virtual void remove_input_raw(GoughSSAVar *v) = 0; friend struct GoughSSAVar; }; struct GoughSSAVarMin : public GoughSSAVarWithInputs { GoughSSAVarMin(void) {} void generate(std::vector<gough_ins> *out) const override; void clear_inputs() override; void replace_input(GoughSSAVar *old_v, GoughSSAVar *new_v) override; virtual void add_input(GoughSSAVar *v) { inputs.insert(v); v->outputs.insert(this); } protected: void remove_input_raw(GoughSSAVar *v) override; }; struct GoughSSAVarJoin : public GoughSSAVarWithInputs { GoughSSAVarJoin(void) {} /* dummy; all joins at a point must be generated simultaneously */ void generate(std::vector<gough_ins> *out) const override; GoughSSAVar *get_input(const GoughEdge &prev) const; void clear_inputs() override; void replace_input(GoughSSAVar *old_v, GoughSSAVar *new_v) override; void add_input(GoughSSAVar *v, GoughEdge prev); const flat_set<GoughEdge> &get_edges_for_input(GoughSSAVar *input) const; const std::map<GoughSSAVar *, flat_set<GoughEdge>> &get_input_map() const; protected: void remove_input_raw(GoughSSAVar *v) override; private: std::map<GoughSSAVar *, flat_set<GoughEdge>> input_map; }; struct gough_accel_state_info { u32 margin; bool two_byte; gough_accel_state_info(u32 margin_in, bool two_byte_in) : margin(margin_in), two_byte(two_byte_in) { } }; u32 assign_slots(GoughGraph &g, const Grey &grey); void find_allowed_accel_states(const GoughGraph &g, const std::map<gough_edge_id, std::vector<gough_ins> > &blocks, std::map<dstate_id_t, gough_accel_state_info> *out); bool find_normal_self_loop(GoughVertex v, const GoughGraph &g, GoughEdge *out); } // namespace ue2 // Note: C structure, can't be in namespace ue2 static inline bool operator==(const gough_ins &a, const gough_ins &b) { return a.op == b.op && a.dest == b.dest && a.src == b.src; } static inline bool operator<(const gough_ins &a, const gough_ins &b) { return std::tie(a.op, a.src, a.dest) < std::tie(b.op, b.src, b.dest); } #endif