nsz Git - libfirm/blob - ir/be/grgen/action_t.h

   1 #ifndef _EXT_GRS_ACTION_T_H_
   2 #define _EXT_GRS_ACTION_T_H_
   3
   4 /*
   5  * Project:     libFIRM/extension module/graph rewriting system
   6  * File name:   ext/grs/action_t.h
   7  * Purpose:     provides an internal interface for the creation of actions
   8  *                              (i.e. rewriting rules and patterns to be found without
   9  *              performing a rewriting step)
  10  * Author:      Veit Batz
  11  * Created:             29. August 2005
  12  * CVS-ID:      $Id$
  13  * Copyright:   (c) 2005 Universität Karlsruhe
  14  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  15  */
  16
  17
  18 #include <libcore/lc_bitset.h>
  19
  20 #include "common_t.h"
  21 #include "action.h"
  22
  23
  24
  25
  26
  27
  28 /** the kind of a graph elem (node or edge) */
  29 typedef enum {
  30         /** a graph node */
  31         ext_grs_k_node,
  32         /** a graph edge */
  33         ext_grs_k_edge,
  34         /** a pseudo node  */
  35         ext_grs_k_pseudo_node,
  36         /** a pseudo edge  */
  37         ext_grs_k_pseudo_edge
  38 } ext_grs_elem_kind_t;
  39
  40
  41 typedef double ext_grs_edge_cost_t;
  42
  43
  44
  45 /** represents a node in a grs rule */
  46 struct _ext_grs_node_t
  47 {
  48         ext_grs_elem_kind_t kind; /** mus be ext_grs_k_node or ext_grs_k_pseudo_node */
  49
  50         /* this nodes graph */
  51         ext_grs_graph_t *graph;
  52
  53         char *name; /**< the name of this node */
  54         /** This nodes action internal id. This id is also used
  55          *  as index for match storage. */
  56         int aiid;
  57         /** this nodes ir op */
  58         ir_op *op;
  59         /** this nodes ir mode */
  60         ir_mode *mode;
  61         /** arrays of incoming and outgoing edges */
  62         lc_list_t edges[2];
  63         /** represents the memberships in the graphs node list  */
  64         lc_list_t node_list;
  65         /** a function representing a condition regarding the op of a firm
  66          *  node which shall be matched with this (pattern or negative) node */
  67         ext_grs_op_condition_func_t op_condition;
  68         /** a function representing a condition regarding the mode of a firm
  69          *  node which shall be matched with this (pattern or negative) node */
  70         ext_grs_mode_condition_func_t mode_condition;
  71         /** number of incoming replace edges not associated with a pattern
  72          *  edge and having no specified position, these edges will be appended
  73          *  to the exisiting in array in the rwrite step (only used in replacement
  74          *  graphs) */
  75         int n_append_edges;
  76
  77         /** index of the matcher op by which this node is first matched */
  78         int first_mop_index;
  79
  80         /** some auxilary data needed to maintain a list of not yet processed nodes
  81          * (see impl of Edmonds alogrithm in vs search planing) */
  82         lc_list_t not_visited_list;
  83
  84         ext_grs_node_t *related_node;
  85 };
  86
  87 typedef struct {
  88         ext_grs_elem_kind_t kind;
  89         union { ext_grs_node_t *n; struct _ext_grs_edge_t *e;} val;
  90 } ext_grs_elem_t;
  91
  92 /** represents an edge in a grs rule */
  93 struct _ext_grs_edge_t
  94 {
  95         ext_grs_elem_kind_t kind; /** mus be ext_grs_k_edge or ext_grs_k_pseudo_edge */
  96
  97         /* this edges graph */
  98         ext_grs_graph_t *graph;
  99
 100         char *name; /**< the name of this edge */
 101         /** This edges action internal id. This id is also used
 102          *  as index for match storage. */
 103         int aiid;
 104         /** this edges position as an argument of its source node */
 105         int pos;
 106         /** this edges argument node, i.e. the node the result of which is
 107          * processed by the function node */
 108         ext_grs_node_t *arg;
 109         /** this edges function node, i.e. the node using the argument for
 110          *  further computations */
 111         ext_grs_node_t *func;
 112         /** if edge is a pseudo edge it represents follwing an edge against
 113          *  its direction or the matching of a start node. Then this member
 114          *  is a ptr to the edge or node represented */
 115         ext_grs_elem_t genuine_elem;
 116         /** for actual (non pseudo) edges: points to the pseudo edge
 117          * representing the backward traversal of this edge */
 118         ext_grs_edge_t *backward_edge;
 119         /** for replacement edges, which have to be newly inserted, this function
 120          *  computes the position the edge is inserted with at its func-node */
 121         ext_grs_edge_pos_func_t position_func;
 122         /* represents the membership in the graphs edge list
 123          * (not for pseudo edges) */
 124         lc_list_t edge_list;
 125         /** represents the membership in this edge src- and tgt-nodes
 126          * in and out lists (not for pseudo edges)  */
 127         lc_list_t list[2];
 128         /** index of the matcher op by which this edge is first matched */
 129         int first_mop_index;
 130
 131
 132         /** A field needed in the planing process:
 133          *  represents this edges mambership in a
 134          *  meldable priority queue of edges */
 135         lc_list_t mpq_list;
 136         /** A field needed in the planing process:
 137          *  represents this edges cost in this actions cost graph during the planing process */
 138         ext_grs_edge_cost_t cost;
 139
 140         ext_grs_edge_t *related_edge;
 141 };
 142
 143 typedef enum {
 144         ext_grs_k_pattern,
 145         ext_grs_k_negative,
 146         ext_grs_k_replacement
 147 } ext_grs_graph_kind_t;
 148
 149 /** represents a pattern graph to be matched or inserted or
 150  *  a negetive pattern graph */
 151 struct _ext_grs_graph_t {
 152         ext_grs_graph_kind_t kind;
 153         /** the action this pattern graph belongs to */
 154         ext_grs_action_t *action;
 155         /** number of this graphs nodes */
 156         int n_nodes;
 157          /** number of this graphs edges */
 158         int n_edges;
 159         /** number of this graphs conditions */
 160         int n_conditions;
 161         /**this graphs nodes */
 162         lc_list_t nodes;
 163         /**this graphs edges */
 164         lc_list_t edges;
 165         /** if this graph is a negative pattern this field represents the
 166          *  membership in this graphs actions list of negative patterns */
 167         lc_list_t negative_list;
 168         /** A pseudo node needed for the computation of matching plans.
 169          *  all edges incident to this node are pseudo edges representing
 170          *  some kind of cost used in match planning */
 171         ext_grs_node_t root_node;
 172 };
 173
 174
 175 /** An action the grs can perform. Possible kinds of actions are rules
 176  * and tests. A rule describes the replacement of pattern graphs by a
 177  * replacement graph, a test only describes the lookup for occurences of
 178  * the pattern graphs, where it is not intended to perform a replacement */
 179 struct _ext_grs_action_t
 180 {
 181         /** this actions kind (e.g. rule or test)*/
 182         ext_grs_action_kind_t kind;
 183         /** this actions id */
 184         int id;
 185         /** this actions name */
 186         char *name;
 187         /** flag: tells wether this action is mature or not. No changes
 188          *  can be performed on the pattern, replacement or negative
 189          *  patterns of a mature action */
 190         int mature;
 191
 192
 193         /* information concerning the matching */
 194
 195         /** the pattern graph */
 196         ext_grs_graph_t *pattern;
 197         /** list of all negative patterns if this action */
 198         lc_list_t negatives;
 199         /** overall number of real nodes of this action without pseudo and negative nodes */
 200         int n_nodes;
 201         /** overall number of real edges of this action without pseudo and negative edges */
 202         int n_edges;
 203         /** overall number of negative nodes of this action */
 204         int n_neg_nodes;
 205         /** overall number of negative edges of this action */
 206         int n_neg_edges;
 207         /** overall number of pseudo nodes of this action excluding the root node */
 208         int n_pseudo_nodes;
 209         /** overall number of pseudo edges of this action */
 210         int n_pseudo_edges;
 211
 212         /** overall number of conditions registered with this action
 213         *  (without op and mode conditions) */
 214         int n_conditions;
 215         /** the conditions registered with this action (without op and mode conditions) */
 216         ext_grs_condition_func_t *conditions;
 217         /** the aiids of the nodes involved in the condition with the given index */
 218         lc_bitset_t **conds_involved_nodes;
 219         /** the aiids of the edges involved in the condition with the given index */
 220         lc_bitset_t **conds_involved_edges;
 221         /** All conditions of this action stored as list of condition descriptors.
 222         *  Only needed when the action is not yet mature. */
 223         lc_list_t listed_conditions;
 224
 225         /** maximum (pattern or negative) node aiid present */
 226         int max_node_aiid;
 227         /** maximum (pattern or negative) edge aiid present */
 228         int max_edge_aiid;
 229         /** all (positive or negative) nodes of
 230          *  this action (no replacement nodes) */
 231         ext_grs_node_t **nodes;
 232         /** the indices of the conditions refering the node of a given aiid */
 233         lc_bitset_t **nodes_refering_conds;
 234         /** all (positive or negative) edges of this action
 235          *  (no replacement edges) */
 236         ext_grs_edge_t **edges;
 237         /** the indices of the conditions refering the edge of a given aiid */
 238         lc_bitset_t **edges_refering_conds;
 239
 240         /** tells wether two nodes are allowed to be matched homomorphic.<br>
 241          *  Usage: <code>act->hom[node1_id][mode2_id]</code> */
 242         int **hom;
 243
 244         /** tells wether a positive and a negative node are related
 245          *  Usage: <code>act->neg_node_relate[pat_node][neg_node]d</code>
 246         int *neg_node_d;*/
 247
 248         /** tells wether a positive and a negative edge are related
 249          * Usage: <code>act->neg_edge_relate[pat_edge][neg_edge]d</code>
 250         int *neg_edge_related;*/
 251
 252         /** tells wether a node is allowed for multiple matching when
 253          *  parallel rule application is intended
 254          *  Usage: <code>act->critical[node_id]</code> */
 255         int *node_critical;
 256
 257         /** tells wether an edge is allowed for multiple matching when
 258          *  parallel rule application is intended
 259          *  Usage: <code>act->critical[edge_id]</code> */
 260         int *edge_critical;
 261
 262
 263
 264         /* information concerning the replacement */
 265
 266         /** the replacament graph (if action is a rule) */
 267         ext_grs_graph_t *replacement;
 268
 269         /** if pattern node is to be kept
 270          *      pattern_node_kept[pattern_node_index]
 271          *  yields the replacement aiid of the corresponding
 272          *  replace node and -1 otherwise */
 273         int *pattern_node_kept;
 274         /** if pattern edge is to be kept
 275          *      pattern_node_kept[pattern_edge_index]
 276          *  yields the replacement aiid of the corresponding
 277          *  replace edge and -1 otherwise */
 278         int *pattern_edge_kept;
 279
 280         /** number of nodes of the replacement graph */
 281         int n_replacement_nodes;
 282         /** The nodes of the replacement graph. The index is the nodes aiid, which is
 283          *  unique ONLY for replacement nodes */
 284         ext_grs_node_t **replacement_nodes;
 285         /** number of edges of the replacement graph */
 286         int n_replacement_edges;
 287         /** the edges of the rplacement graph, index is the nodes aiid, which is
 288          *  unique ONLY for replacement nodes */
 289         ext_grs_edge_t **replacement_edges;
 290         /** Tells wether a replacement node is to be newly inserted or kept:
 291          *  -1 means to be inserted, >=0 means kept. If the node is kept,
 292          *  the value equals the aiid of the corresponding pattern node.
 293          *  USAGE: replacement_node_kept[replace_node_aiid] */
 294         int *replacement_node_kept;
 295         /** Tells wether a replacement edge is to be newly inserted or kept:
 296          *  -1 means to be inserted, >=0 means kept. If the edge is kept,
 297          *  the value equals the aiid of the corresponding pattern edge.
 298          *  USAGE: replacement_edge_kept[replace_edge_aiid] */
 299         int *replacement_edge_kept;
 300         /** maximum replacement node aiid present */
 301         int max_repl_node_aiid;
 302         /** maximum replacement edge aiid present */
 303         int max_repl_edge_aiid;
 304         /** the list of functions to be evaluated directly after each rewrite step,
 305          *  the evaluation is done in the order, the functions are stored
 306          *  in this list */
 307         lc_list_t listed_evals;
 308
 309         /** Stores pairs of nodes and edges associated to be kept nodes/edge.
 310          *  Only needed when the action is not yet mature. */
 311         lc_pset *kept_elems;
 312 };
 313
 314
 315 /** A condition descriptor. Describes which (pattern or negative) nodes
 316  *  and/or edfes are involved in the condition represented by the given
 317  *  condition function */
 318 typedef struct {
 319         /** the action this condition belongs to */
 320         struct _ext_grs_graph_t *graph;
 321         /** the function representing the condition */
 322         ext_grs_condition_func_t condition;
 323         /** the number of involved nodes */
 324         int n_nodes;
 325         /** the involved nodes */
 326         ext_grs_node_t **nodes;
 327         /** the number of involved edges */
 328         int n_edges;
 329         /** the involved edges */
 330         ext_grs_edge_t **edges;
 331         /** represents the list of onditions of an action */
 332         lc_list_t condition_list;
 333 } ext_grs_cond_descr_t;
 334
 335 /** An eval descriptor. Respresents an eval function in
 336  *  an actions list of evals */
 337 typedef struct {
 338         /** the eval-in function */
 339         ext_grs_eval_in_func_t eval_in;
 340         /** the eval-out function */
 341         ext_grs_eval_out_func_t eval_out;
 342         /** represents the list of evals of an action */
 343         lc_list_t eval_list;
 344         /** some auxilary data used when finishing a match */
 345         void *data;
 346 } ext_grs_eval_descr_t;
 347
 348 /** Initialize the action part of the exr/grs module of the libfirm.
 349  *  This is an internal function. */
 350 void _ext_grs_act_init(void);
 351
 352 /** Finalize the action part of the exr/grs module of the libfirm.
 353  *  This is an internal function. */
 354 void _ext_grs_act_finalize(void);
 355
 356
 357
 358 #endif /* _EXT_GRS_ACTION_T_H_ */