nsz Git - libfirm/blob - ir/be/grgen/simd/search_tree_t.h

   1 /************************************************************************
   2 * Program:              Search_tree.c
   3 * Project:              SIMD optimization
   4 * Function:             Provides functions to build a search tree to
   5 *                               select the patterns for rewrite
   6 * Author:               Andreas Schoesser
   7 * Date:                 2007-07-05
   8 ************************************************************************/
   9
  10 #ifndef __SEARCH_TREE_T_H__
  11 #define __SEARCH_TREE_T_H__
  12
  13 #include "plist.h"
  14 #include "obstack.h"
  15
  16 #include "grs/grs.h"
  17 #include "grs/match_t.h"
  18 #include "grs/matchplan.h"
  19 #include "grs/matchplan_t.h"
  20
  21 #include "simd_opt_t.h"
  22
  23 ext_grs_match_plan_t *mplans;
  24
  25 #define THIS_MATCHS_COSTSAVINGS 3
  26
  27
  28 /** Entry of a ignore_match list */
  29 typedef struct
  30 {
  31         pmap                    *nodes;
  32         //ir_edge_t             **edges;
  33 } ignored_match_t;
  34
  35
  36 /** A node of the search tree */
  37 typedef struct search_tree_node_t
  38 {
  39         ext_grs_match_t         *match;
  40         int                                     which_match;
  41         struct search_tree_node_t       *with;
  42         struct search_tree_node_t       *without;
  43         int                                                     cost_savings;
  44         int                                                     this_matchs_costsavings;
  45         int                                                     rule_nr;
  46         struct pmap                                     *memory_preds;
  47 } search_tree_node_t;
  48
  49 /** Information to delete vproj nodes again */
  50 typedef struct
  51 {
  52         ir_node *vproj_node;
  53         ir_node *org_result;
  54 } undo_vproj_t;
  55
  56 /** Environment passed while building the search tree recursively */
  57 typedef struct
  58 {
  59         ir_graph                                *irg;
  60         int                                             num_rules;
  61         ext_grs_match_plan_t    **m_plans;
  62         int                                             *priorities;
  63         ext_grs_action_t        **rules;
  64         struct pmap                             *which_match_vproj;
  65         struct pmap                             *replaced_ptrs;
  66         char                                    **firmnode_names;
  67         struct obstack                  *obst;
  68         statistics_t                    *statistics;
  69         int                                             *cost_savings;
  70 } search_tree_env_t;
  71
  72 /** To be filled before replacement */
  73 typedef struct
  74 {
  75         ir_graph                        *irg;
  76         struct pmap                     *keep_nodes;
  77         struct pmap                     *vec_operations;
  78         struct pmap                     *which_match_vproj;
  79         statistics_t            *statistics;
  80         ext_grs_action_t    **rules;
  81         char                            **firmnode_names;
  82         struct obstack          *obst;
  83 } replace_st_env_t;
  84
  85 typedef struct
  86 {
  87         ext_grs_match_t *match;
  88         int                             which;
  89         int                             aiid;
  90 } which_match_vproj_t;
  91
  92
  93 // Public
  94 search_tree_node_t *build_search_tree(search_tree_env_t *search_tree_env, int prio_start);//, int struct pmap *vec_operations, struct pmap *keep_nodes, int start, statistics_t *statistics, struct pmap *replaced_ptrs)
  95 void replace_search_tree(search_tree_node_t *root, replace_st_env_t *rep_env);
  96 void destroy_search_tree(search_tree_node_t *root);
  97
  98 // Private
  99 static search_tree_node_t *rec_search_patterns(search_tree_env_t *st_env, int prio, plist_t **ignored_matches);
 100 static plist_element_t *add_ignored_match(ext_grs_match_t *match, int which, plist_t **ignored_matches, int rule_nr);
 101 static void delete_ignored_match(plist_t **ignored_matches, plist_element_t *match_to_delete, int rule_nr);
 102 static int ignore_match(ext_grs_match_t *match, int which, plist_t **ignored_matches, int rule_nr);
 103 static plist_t *construct_vproj(search_tree_env_t *st_env, search_tree_node_t *st_node, int rule_nr);
 104 static void deconstruct_vproj(plist_t *undo_vproj_info);
 105 static void insert_which_match_vproj(search_tree_env_t *st_env, ir_node *vproj, ext_grs_match_t *match, int which, int aiid);
 106 static void manipulate_match(replace_st_env_t *rep_env, ext_grs_match_t *match, int which);
 107
 108 void dump_search_tree(search_tree_node_t *root, char *file, char *graph_name, search_tree_env_t *st_env);
 109 int rec_dump_search_tree(search_tree_node_t *node, FILE *fp, int this_node_nr, search_tree_env_t *st_env, int best_cost);
 110
 111 void insert_inner_nodes(search_tree_env_t *st_env, search_tree_node_t *st_node);
 112 void remove_inner_nodes(search_tree_env_t *st_env, search_tree_node_t *st_node);
 113
 114 void set_complex_operation_block(ir_graph *irg, ext_grs_match_t *match, int which);
 115
 116 #endif