| #ifndef CLICK_CLASSIFIER_H |
| #define CLICK_CLASSIFIER_H |
| |
| #include <stdint.h> |
| #include <string> |
| #include "error.h" |
| |
| #ifdef USE_STD_VECTOR |
| # include <vector> |
| # define Vector std::vector |
| #else |
| # include "vector.h" |
| #endif |
| |
| typedef Vector<std::string> stringvec; |
| typedef stringvec::size_type vec_size_t; |
| |
| struct OffloadReq; |
| |
| class Classifier { |
| public: |
| |
| class Expr; |
| |
| Classifier(); |
| virtual ~Classifier(); |
| |
| // creating Exprs |
| enum { NEVER = -2147483647, FAILURE, SUCCESS }; |
| void add_expr(Vector<int> &, const Expr &); |
| void add_expr(Vector<int> &, int offset, uint32_t value, uint32_t mask); |
| void init_expr_subtree(Vector<int> &); |
| void start_expr_subtree(Vector<int> &); |
| void negate_expr_subtree(Vector<int> &); |
| enum Combiner { C_AND, C_OR, C_TERNARY }; |
| void finish_expr_subtree(Vector<int> &, Combiner = C_AND, int success = SUCCESS, int failure = FAILURE); |
| std::string program_string(void); |
| void dump_program(FILE *); |
| |
| int noutputs() const { return _noutputs; } |
| |
| int match(const OffloadReq &) const; |
| |
| struct Expr { |
| int offset; |
| union { |
| unsigned char c[4]; |
| uint32_t u; |
| } mask; |
| union { |
| unsigned char c[4]; |
| uint32_t u; |
| } value; |
| int32_t j[2]; |
| int32_t yes() const { return j[1]; } |
| int32_t no() const { return j[0]; } |
| int32_t &yes() { return j[1]; } |
| int32_t &no() { return j[0]; } |
| bool implies(const Expr &) const; |
| bool implies_not(const Expr &) const; |
| bool not_implies(const Expr &) const; |
| bool not_implies_not(const Expr &) const; |
| bool compatible(const Expr &) const; |
| bool flippable() const; |
| void flip(); |
| std::string s() const; |
| }; |
| |
| protected: |
| |
| Vector<Expr> _exprs; |
| int _output_everything; |
| int _noutputs; |
| |
| void redirect_expr_subtree(int first, int next, int success, int failure); |
| |
| void combine_compatible_states(); |
| bool remove_unused_states(); |
| void unaligned_optimize(); |
| void count_inbranches(Vector<int> &) const; |
| void bubble_sort_and_exprs(int sort_stopper = 0x7FFFFFFF); |
| void optimize_exprs(ErrorHandler *, int sort_stopper = 0x7FFFFFFF); |
| void compress_exprs(Vector<uint32_t> &prog, bool perform_binary_search = true, |
| unsigned int bin_search_threshold = 7) const; |
| |
| private: |
| |
| class DominatorOptimizer { public: |
| |
| DominatorOptimizer(Classifier *c); |
| |
| static int brno(int state, bool br) { return (state << 1) + br; } |
| static int stateno(int brno) { return brno >> 1; } |
| static bool br(int brno) { return brno & 1; } |
| |
| bool br_implies(int brno, int state) const; |
| bool br_implies_not(int brno, int state) const; |
| |
| void run(int); |
| void print(); |
| |
| private: |
| |
| Classifier *_c; |
| Vector<int> _dom; |
| Vector<int> _dom_start; |
| Vector<int> _domlist_start; |
| |
| enum { MAX_DOMLIST = 4 }; |
| |
| Classifier::Expr &expr(int state) const; |
| int nexprs() const; |
| |
| static void intersect_lists(const Vector<int> &, const Vector<int> &, const Vector<int> &, int pos1, int pos2, Vector<int> &); |
| static int last_common_state_in_lists(const Vector<int> &, const Vector<int> &, const Vector<int> &); |
| void find_predecessors(int state, Vector<int> &) const; |
| int dom_shift_branch(int brno, int to_state, int dom, int dom_end, Vector<int> *collector); |
| void shift_branch(int brno); |
| void calculate_dom(int state); |
| |
| }; |
| |
| friend class DominatorOptimizer; |
| }; |
| |
| #endif |