nsz Git - libfirm/blob - ir/be/grgen/match.c

   1 /*
   2  * Project:     libFIRM/extension module/graph rewriting system
   3  * File name:   ext/grs/match.c
   4  * Purpose:     provides functions for subgraph matching
   5  * Author:      Veit Batz
   6  * Modified by: Andreas Schoesser
   7  * Created:             7. Junly 2005
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 2005 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12
  13 #include <stdlib.h>
  14 #include <libcore/lc_pset.h>
  15 #include "firm.h"
  16 #ifdef _WIN32
  17 #include <malloc.h>
  18 #else
  19 #include <alloca.h>
  20 #endif
  21 #include "firm_types.h"
  22 #include "array.h"
  23 #include "ircons_t.h"
  24 #include "irdump_t.h"
  25 #include "irnode_t.h"
  26 #include "iredges.h"
  27 #include "base_t.h"
  28 #include "match_t.h"
  29
  30
  31 /* just a prototype */
  32 static void match_rec(void);
  33
  34
  35 #undef MAX
  36 #define MAX(a,b) ((a) >= (b) ? (a) : (b))
  37
  38
  39
  40 /* the match dumper stores ir nodes and edges of a given match in hash tables
  41  * such that it can determine whether a ir node or edge has to be highlighted or not */
  42 typedef struct _ext_grs_matched_graph_elem_t {
  43         /* tells whether a node or an edge is matched */
  44         ext_grs_elem_kind_t kind;
  45         /* the matched graph elem (a node or an edge) */
  46         union {ir_node *irn; const ir_edge_t *ire;} elem;
  47         /* tells whether this elem is matched for a given match id */
  48         int *matched;
  49         /* an array of index lists, tells the indeces in the
  50          * espective match (if matched at all) */
  51         lc_list_t *aiids;
  52 }
  53 ext_grs_matched_graph_elem_t;
  54
  55 typedef struct {
  56         int aiid;
  57         lc_list_t list;
  58 } ext_grs_matched_aiids_t;
  59
  60
  61 /* elem of the list of found matches */
  62 struct ext_grs_match_list_head {
  63         lc_list_t list;
  64         ir_node **nodes;
  65         ir_edge_t **edges;
  66 };
  67
  68
  69
  70 /* Some global variables needed by the recursive matching algorithm.
  71  * This helps saving parameters */
  72
  73 /* the current matcher prog */
  74 static ext_grs_match_op_t *prog = NULL;
  75 /* the length of the current matcher prog */
  76 static int length = 0;
  77 /* the current position in the match program */
  78 static int mpos = 0;
  79 /* the maximum number of matches that shall be found (-1 means ALL) */
  80 static int max_n_matches;
  81 /* tells whether the matching shall guaranty the parallel
  82  * applicability of the given action for ALL found matches:
  83  * zero means no, nonzero mens yes */
  84 static int match_compliant;
  85 /* the current visit phase of the current irg. This info is necessary
  86  * to mark all nodes and edges which have already been matched by a
  87  * pattern node which does not guaranty parallel applicability in
  88  * multiple matches */
  89 static unsigned long irg_visit_phase;
  90 /* tells to which op index the backtracking has to brunch back, when a match
  91  * is found */
  92 static int return_to_mop_index;
  93
  94 /* flag, tells whether a invocation of match_rec is for the pattern or a NAC */
  95 static int match_negative_pattern = 0;
  96 static int found_negative;
  97
  98 /** the node map of the current graph homomorphism */
  99 static ir_node **node_map;
 100 /** the edge map of the current graph homomorphism */
 101 static ir_edge_t **edge_map;
 102
 103 static ir_node   **positive_node_map;
 104 static ir_edge_t **positive_edge_map;
 105
 106 /* the current match object */
 107 static ext_grs_match_t *match = NULL;
 108 /* private data of the current irg */
 109 static ext_grs_irg_private_t *pr_g = NULL;
 110 /* the list of already found matches (to be copied into the
 111  * match object at the end of the matching process) */
 112 static struct ext_grs_match_list_head match_list_head;
 113
 114
 115 /* an obstack needed by the match dumper */
 116 static struct obstack dump_obst;
 117 /* the hash table needed in the dump process mentioned above */
 118 static lc_pset *dump_node_map, *dump_edge_map;
 119 /* the number of matches in the match which is currently dumped */
 120 static int dump_n_matches;
 121
 122
 123
 124
 125
 126
 127
 128 int matched_graph_elem_cmp_func(const void *o1, const void *o2) {
 129         ext_grs_matched_graph_elem_t *e1, *e2;
 130         e1 = (ext_grs_matched_graph_elem_t *) o1;
 131         e2 = (ext_grs_matched_graph_elem_t *) o2;
 132
 133         assert (e1->kind == e2->kind);
 134
 135         return (((unsigned) e1->elem.irn) - ((unsigned) e2->elem.irn));
 136 }
 137
 138 int dump_matched_node_vcgattr(FILE *F, ir_node *node, ir_node *local) {
 139
 140         ext_grs_matched_graph_elem_t *elem = alloca(sizeof(*elem));
 141
 142         /* check wether the given node is matched or not */
 143         elem->kind = ext_grs_k_node;
 144         elem->elem.irn = node;
 145         elem = lc_pset_find(dump_node_map, elem, HASH_PTR(node));
 146         /* if it is matched... */
 147         if (elem) {
 148                 fprintf (F, "color: magenta");
 149                 return 1;
 150         }
 151         return 0;
 152 }
 153
 154 int dump_matched_edge_vcgattr(FILE *F, ir_node *node, int to) {
 155
 156         ext_grs_matched_graph_elem_t *elem = alloca(sizeof(*elem));
 157
 158         const ir_edge_t *edge =  get_irn_edge(get_irn_irg(node), node, to);
 159
 160         /* check whether the given node is matched or not */
 161         elem->kind = ext_grs_k_edge;
 162         elem->elem.ire = edge;
 163         elem = lc_pset_find(dump_edge_map, elem, HASH_PTR(edge));
 164         /* if it is matched... */
 165         if (elem) {
 166                 fprintf (F, "color:magenta");
 167                 return 1;
 168         }
 169         return 0;
 170 }
 171
 172 int dump_graph_match_nodes(FILE *F, ir_graph *irg) {
 173
 174         int which;
 175         for (which = 0; which < dump_n_matches; which++) {
 176                 fprintf(F, "node: {title: \"match%d\" label: \"Match %d\" ", which, which);
 177                 fprintf(F, "color: cyan}\n");
 178         }
 179
 180         return 0;
 181 }
 182
 183 int dump_match_edges(FILE *F, ir_node *node) {
 184
 185         ext_grs_matched_graph_elem_t *elem = alloca(sizeof(*elem));
 186         int which;
 187         lc_list_t *pos;
 188
 189         /* check wether the given node is matched or not */
 190         elem->kind = ext_grs_k_node;
 191         elem->elem.irn = node;
 192         elem = lc_pset_find(dump_node_map, elem, HASH_PTR(node));
 193         /* if it is matched... */
 194         if (elem)
 195                 for (which = 0; which < dump_n_matches; which++)
 196                         if (elem->matched[which])
 197                                 lc_list_for_each (pos, & elem->aiids[which]) {
 198                                         /* get the index in the node map */
 199                                         ext_grs_matched_aiids_t *aiid_wrapper =
 200                                                 lc_list_entry(pos, ext_grs_matched_aiids_t, list);
 201                                         /* gen an edge from match node to matched node */
 202                                         fprintf(F, "edge: {sourcename: \"match%d\" targetname: \"", which);
 203                                         PRINT_NODEID(node);
 204                                         fprintf(F, "\" ");
 205                                         fprintf(F, "label: \"%d\" color:cyan}\n", aiid_wrapper->aiid);
 206                                 }
 207
 208         return 0;
 209 }
 210
 211 void ext_grs_dump_match(ext_grs_match_t *match, const char *suffix) {
 212
 213         int i;
 214         int which, aiid;
 215         ext_grs_matched_graph_elem_t *elem;
 216         ext_grs_matched_aiids_t *aiid_wrapper;
 217         DUMP_NODE_EDGE_FUNC remember;
 218
 219         obstack_init(& dump_obst);
 220
 221         /* establish hash tables to determine, whether a nodes
 222          *  or edges have been matched or not */
 223         dump_node_map =
 224                 lc_pset_new(matched_graph_elem_cmp_func, match->n_nodes * match->n_matches);
 225         dump_edge_map =
 226                 lc_pset_new(matched_graph_elem_cmp_func, match->n_edges * match->n_matches);
 227
 228         for (which = 0; which < match->n_matches; which++) {
 229                 for (aiid = 0; aiid < match->n_nodes; aiid ++) {
 230
 231                         ir_node *irn = match->nodes[which][aiid];
 232
 233                         elem = alloca(sizeof(*elem));
 234                         elem->kind = ext_grs_k_node;
 235                         elem->elem.irn = irn;
 236                         elem = lc_pset_find(dump_node_map, elem, HASH_PTR(irn));
 237
 238                         if (!elem) {
 239
 240                                 elem = obstack_alloc(& dump_obst, sizeof(*elem));
 241                                 elem->matched = obstack_alloc(
 242                                         & dump_obst, match->n_matches * sizeof(*elem->matched));
 243                                 elem->aiids = obstack_alloc(
 244                                         & dump_obst, match->n_matches * sizeof(*elem->aiids));
 245                                 /* init to 'not matched' for each match */
 246                                 memset(elem->matched, 0, match->n_matches * sizeof(*elem->matched));
 247                                 /* init the list heads in the aiid array */
 248                                 for (i = 0; i < match->n_matches; i++)
 249                                         LC_INIT_LIST_HEAD( &(elem->aiids[i]) );
 250
 251                                 elem->kind = ext_grs_k_node;
 252                                 elem->elem.irn = irn;
 253                                 lc_pset_insert(dump_node_map, elem, HASH_PTR(irn));
 254                         }
 255                         elem->matched[which] = 1;
 256                         aiid_wrapper = obstack_alloc(& dump_obst, sizeof(*aiid_wrapper));
 257                         aiid_wrapper->aiid = aiid;
 258                         lc_list_add(& aiid_wrapper->list, & (elem->aiids[which]));
 259                 }
 260                 for (aiid = 0; aiid < match->n_edges; aiid ++) {
 261
 262                         const ir_edge_t *ire = match->edges[which][aiid];
 263
 264                         elem = alloca(sizeof(*elem));
 265                         elem->kind = ext_grs_k_edge;
 266                         elem->elem.ire = ire;
 267                         elem = lc_pset_find(dump_edge_map, elem, HASH_PTR(ire));
 268
 269                         if (!elem) {
 270                                 elem = obstack_alloc(& dump_obst, sizeof(*elem));
 271                                 elem->matched = obstack_alloc(
 272                                         & dump_obst, match->n_matches * sizeof(*elem->matched));
 273                                 elem->aiids = obstack_alloc(
 274                                         & dump_obst, match->n_matches * sizeof(*elem->aiids));
 275                                 /* init to 'not matched' for each match */
 276                                 memset(elem->matched, 0, match->n_matches * sizeof(*elem->matched));
 277                                 /* init the list heads in the indices array */
 278                                 for (i = 0; i < match->n_matches; i++)
 279                                         LC_INIT_LIST_HEAD( &(elem->aiids[i]) );
 280
 281                                 elem->kind = ext_grs_k_edge;
 282                                 elem->elem.ire = ire;
 283                                 lc_pset_insert(dump_edge_map, elem, HASH_PTR(ire));
 284                         }
 285                         elem->matched[which] = 1;
 286                         aiid_wrapper = obstack_alloc(& dump_obst, sizeof(*aiid_wrapper));
 287                         aiid_wrapper->aiid = aiid;
 288                         lc_list_add(& aiid_wrapper->list, & (elem->aiids[which]));
 289                 }
 290         }
 291
 292         /* set some hooks to produce the needed output in the generated vcg file */
 293         set_dump_node_vcgattr_hook(dump_matched_node_vcgattr);
 294         set_dump_edge_vcgattr_hook(dump_matched_edge_vcgattr);
 295         set_dump_ir_graph_hook(dump_graph_match_nodes);
 296
 297         remember = get_dump_node_edge_hook();
 298         set_dump_node_edge_hook(dump_match_edges);
 299
 300         /* dump the ir graph */
 301         dump_n_matches = match->n_matches;
 302         dump_ir_graph(match->irg, suffix);
 303
 304         /* reset the hooks */
 305         set_dump_node_vcgattr_hook(NULL);
 306         set_dump_edge_vcgattr_hook(NULL);
 307         set_dump_ir_graph_hook(NULL);
 308         set_dump_node_edge_hook(remember);
 309
 310         /* delete auxillary data structures */
 311         lc_pset_del(dump_node_map);
 312         lc_pset_del(dump_edge_map);
 313         obstack_free(& dump_obst, NULL);
 314         obstack_finish(& dump_obst);
 315 }
 316
 317
 318
 319
 320
 321 /* initialize the matching mechanism */
 322 void _ext_grs_match_init(void) {
 323         /* init the node map */
 324         node_map = NEW_ARR_F(ir_node*, 100);
 325         memset(node_map, 0, sizeof(*node_map) * 100);
 326         /* init the edge map */
 327         edge_map = (ir_edge_t **) NEW_ARR_F(ir_edge_t*, 100);
 328         memset(edge_map, 0, sizeof(*edge_map) * 100);
 329 }
 330
 331
 332
 333 static INLINE void store_match(void) {
 334
 335         int aiid;
 336         ir_node *node;
 337         ir_edge_t *edge;
 338         struct ext_grs_match_list_head *match_list_elem;
 339         ext_grs_iredges_private_t *pr_e;
 340
 341         int n_all_pattern_nodes = match->action->max_node_aiid + 1;
 342         int n_all_pattern_edges = match->action->max_edge_aiid + 1;
 343
 344         /* allocate new list elem on the match internal obstack */
 345         match_list_elem = obstack_alloc(& match->obst, sizeof(*match_list_elem));
 346         memset(match_list_elem, 0, sizeof(match_list_elem));
 347
 348         /* add this new wrapper for the found match to the list */
 349         lc_list_add(& match_list_elem->list, & match_list_head.list);
 350
 351         /* allocate space for the arrays representing the node and edge map */
 352         match_list_elem->nodes =
 353                 obstack_alloc(& match->obst, n_all_pattern_nodes * sizeof(ir_node *));
 354         match_list_elem->edges =
 355                 obstack_alloc(& match->obst, n_all_pattern_edges * sizeof(ir_edge_t *));
 356
 357         memset(match_list_elem->nodes, 0, n_all_pattern_nodes * sizeof(*match_list_elem->nodes));
 358         memset(match_list_elem->edges, 0, n_all_pattern_edges * sizeof(*match_list_elem->edges));
 359
 360         /* copy node map into match object */
 361         for (aiid = 0; aiid < n_all_pattern_nodes; aiid++) {
 362
 363                 ext_grs_node_t *pat_node = match->action->nodes[aiid];
 364
 365                 if (pat_node->graph->kind != ext_grs_k_pattern) continue;
 366                 node = node_map[aiid];
 367
 368                 assert(node && "a pattern node should have been matched");
 369                 assert(pat_node->kind == ext_grs_k_node &&
 370                         "a pseudo node should not have been matched");
 371
 372                 match_list_elem->nodes[aiid] = node;
 373
 374                 if (match_compliant && match->action->node_critical[aiid])
 375                         if (node) {
 376                                 set_irn_visited(node, irg_visit_phase);
 377                                 return_to_mop_index =
 378                                         return_to_mop_index < match->action->nodes[aiid]->first_mop_index ?
 379                                                 return_to_mop_index : match->action->nodes[aiid]->first_mop_index;
 380                         }
 381         }
 382
 383         /* copy edge map into match object */
 384         for (aiid = 0; aiid < n_all_pattern_edges; aiid++) {
 385
 386                 ext_grs_edge_t *pat_edge = match->action->edges[aiid];
 387
 388                 /* check wether the current edge is a not pseudo-edge */
 389                 if (pat_edge->kind != ext_grs_k_edge) continue;
 390                 /* check wether the current edge belongs to the pattern graph
 391                  * (and not to e.g. a negative graph) */
 392                 if (pat_edge->graph->kind != ext_grs_k_pattern) continue;
 393
 394                 edge = edge_map[aiid];
 395
 396                 assert(edge && "a pattern edge should have been matched");
 397                 assert(pat_edge->kind == ext_grs_k_edge &&
 398                         "a pseudo edge should not have been matched");
 399
 400                 match_list_elem->edges[aiid] = edge;
 401
 402                 if (match_compliant && match->action->edge_critical[aiid]) {
 403
 404                         pr_e = get_edge_private_data(edge, _ext_grs_private_ofs_e);
 405                         pr_e->visited = irg_visit_phase;
 406                         return_to_mop_index =
 407                                 return_to_mop_index < match->action->edges[aiid]->first_mop_index ?
 408                                         return_to_mop_index : match->action->edges[aiid]->first_mop_index;
 409                 }
 410         }
 411
 412         /* increment counter for the found matches */
 413         match->n_matches++;
 414 }
 415
 416 static void fill_match_result(ext_grs_match_plan_t *plan) {
 417
 418         int match_counter = 0;
 419         struct ext_grs_match_list_head *list_elem;
 420
 421         ext_grs_match_t *restore_match;
 422         ext_grs_match_t *neg_match;
 423
 424         lc_list_t *pos;
 425
 426         /* allocate space for the two arrays containing the node and edge maps */
 427         match->nodes = obstack_alloc(& match->obst, match->n_matches * sizeof(*match->nodes));
 428         match->edges = obstack_alloc(& match->obst, match->n_matches * sizeof(*match->edges));
 429         match->repl_nodes = obstack_alloc(& match->obst, match->n_matches * sizeof(*match->repl_nodes));
 430
 431         restore_match = match;
 432         neg_match = alloca(sizeof(*neg_match));
 433
 434         /* init that match object */
 435
 436
 437         /* store the node and edge maps */
 438         match_counter = 0;
 439         /* Walk through the list of matches */
 440         lc_list_for_each(pos, & match_list_head.list) {
 441                 int i;
 442                 lc_list_t *neg_pattern_list;
 443
 444                 list_elem = lc_list_entry(pos, struct ext_grs_match_list_head, list);
 445
 446                 /* for the current positive match ensure that no NAC occurs in the host graph */
 447                 match = neg_match;
 448                 neg_pattern_list = &plan->action->negatives;
 449                 neg_pattern_list = neg_pattern_list->next;
 450                 /* act->negatives is the list head, call next node to find the first object in list */
 451                 for(i = 1; i < plan -> num_progs; i++)
 452                 {
 453                         ext_grs_graph_t *pat = lc_list_entry(neg_pattern_list, ext_grs_graph_t, negative_list);
 454
 455                         memset(match, 0, sizeof(*neg_match));
 456                         match->n_nodes = pat->n_nodes;
 457                         match->n_edges = pat->n_edges;
 458                         match->action = plan->action;
 459                         match->irg = restore_match->irg;
 460                         match->max_node_id = plan->action->max_node_aiid;
 461                         match->max_edge_id = plan->action->max_edge_aiid;
 462                         match->compliant = ext_grs_REGARDLESS;
 463
 464
 465                         return_to_mop_index = plan->length[i] - 1;
 466                         length = plan->length[i];
 467                         prog = plan->progs[i];
 468                         mpos = 0;
 469                         match_negative_pattern = 1;
 470                         found_negative = 0;
 471                         match_compliant = 0;
 472                         max_n_matches = 1;
 473                         positive_node_map = list_elem->nodes;
 474                         positive_edge_map = list_elem->edges;
 475
 476                         /* if program has length 0 ... do nothing */
 477                         if(plan->length[i] <= 0)
 478                                 break;
 479
 480                         match_rec();
 481                         if(found_negative == 1)
 482                                 break;
 483                         neg_pattern_list = neg_pattern_list->next;
 484                 }
 485                 match_negative_pattern = 0;
 486                 match = restore_match;
 487
 488                 if(found_negative == 1)
 489                         continue;
 490
 491
 492                 match->nodes[match_counter] = list_elem->nodes; /* node_map */
 493                 match->edges[match_counter] = list_elem->edges; /* edge_map */
 494
 495                 match_counter++;
 496         }
 497         /* Some positive matches could have been eliminated due to NAC's,
 498            so adapt number of matches */
 499         match->n_matches = match_counter;
 500         assert(match_counter <= match->n_matches && "wrong number of matches stored");
 501 }
 502
 503
 504
 505 /* ---------------
 506    What does this?
 507    --------------- */
 508 static INLINE int match_preset_rec(
 509          ext_grs_node_t *pattern_node, ext_grs_match_op_t *current_mop, ir_node *host_node)
 510 {
 511         ext_grs_irn_private_t *pr_n;
 512         ext_grs_node_t *alredy_matched_pattern_node;
 513
 514         /* Get the private ir data of the host node */
 515         pr_n = get_irn_data(host_node, ext_grs_irn_private_t, _ext_grs_private_ofs_n);
 516
 517         assert(pattern_node->mode == mode_ANY || get_irn_mode(host_node) == pattern_node->mode);
 518
 519         assert(get_irn_opcode(host_node) == get_op_code(pattern_node->op) ||
 520                 _ext_grs_OP_IS_A(get_irn_opcode(host_node),     get_op_code(pattern_node->op))
 521         );
 522
 523         assert(
 524                 match->action->node_critical[pattern_node->aiid] == 0 ||
 525                 match->action->node_critical[pattern_node->aiid] == 1
 526         );
 527
 528         assert(!pr_n->deleted &&
 529                 "a node deleted by a rewrite step should not be a member of a node list");
 530
 531         /* if pattern is negative, compliant matching makes no sense */
 532         assert(! (match_compliant && match_negative_pattern));
 533
 534         if (match_compliant && match->action->node_critical[pattern_node->aiid]) {
 535                 assert(get_irn_visited(host_node) <= irg_visit_phase &&
 536                         "visited in a future phase?");
 537                 if (get_irn_visited(host_node) == irg_visit_phase) return;  // TODO! Return a value here!
 538         }
 539
 540         /* check whether the current host graph node has not already
 541         * been matched. But if it has, the according host nodes have
 542         * to be allowed to be matched homomorphic with the current
 543         * host node */
 544         alredy_matched_pattern_node = pr_n->preimage;
 545         if (alredy_matched_pattern_node == NULL ||
 546                 match->action->hom[pattern_node->aiid][alredy_matched_pattern_node->aiid])
 547         {
 548
 549                 /* if the host node has NOT already been matched before
 550                 * remember the pattern node as already matched to the host node */
 551                 int matched_first = 0;
 552                 if (alredy_matched_pattern_node == NULL) {
 553                         matched_first = 1;
 554                 }
 555
 556                 pr_n->preimage = pattern_node;
 557
 558                 /* add the pair (pattern_node, host_node) to the node map */
 559                 node_map[pattern_node->aiid] = host_node;
 560
 561
 562
 563                 /* check the condition if present */
 564                 if (!current_mop->condition || current_mop->condition(node_map, edge_map)) {
 565                         /* call recursively to process the next matcher op */
 566                         mpos++;
 567                         match_rec();
 568                         mpos--;
 569                 }
 570
 571
 572                 /* remove the pair (pattern_node, host_node) from the node map */
 573                 node_map[pattern_node->aiid] = NULL;
 574                 /* remember whether this matching is no more */
 575
 576
 577                 /* if the pattern node was the first node to be matched with
 578                 * the host node,  */
 579                 if (matched_first)
 580                         pr_n->preimage = NULL;
 581
 582                 /* check whether matching is already complete */
 583                 if (match->n_matches == max_n_matches) return 1;
 584                 assert(match->n_matches < max_n_matches || max_n_matches == -1);
 585                 /* check whether backjumping is needed
 586                 * (this only happens for compliant matching) */
 587                 if (return_to_mop_index < mpos) return 1;
 588                 return_to_mop_index = length - 1;
 589         }
 590
 591
 592         /* matching not yet complete (or no backjumping needed),
 593         * do more matching if possible */
 594         return 0;
 595 }
 596
 597
 598 static INLINE int match_node_rec(
 599         ext_grs_node_t *pattern_node, ext_grs_match_op_t *current_mop, ir_opcode opc, modecode mc)
 600 {
 601         lc_list_t *node_list_head = & _ext_grs_NODE_LIST(pr_g, opc, mc);
 602         lc_list_t *pos;
 603         ir_node *host_node;
 604
 605         /* FOR all ir nodes in the node list of the current op
 606          * and the pattern nodes mode DO... */
 607         /* In other words: Start a new match for each host-node with the current op. (Backtracking) */
 608
 609         lc_list_for_each (pos, node_list_head) {
 610
 611                 ext_grs_irn_private_t *pr_n;
 612                 ext_grs_node_t *alredy_matched_pattern_node;
 613
 614 #if DUMP_WHILE_MATCHING
 615                 printf("Next node...\n");
 616 #endif
 617
 618                 pr_n = lc_list_entry(pos, ext_grs_irn_private_t, node_list);
 619                 host_node = get_irn_data_base(pr_n, _ext_grs_private_ofs_n);
 620
 621                 assert(pattern_node->mode == mode_ANY || get_irn_mode(host_node) == pattern_node->mode);
 622
 623                 assert(get_irn_opcode(host_node) == get_op_code(pattern_node->op) ||
 624                         _ext_grs_OP_IS_A(
 625                                         get_irn_opcode(host_node),
 626                                         get_op_code(pattern_node->op)
 627                                 )
 628                 );
 629
 630                 assert(
 631                         match->action->node_critical[pattern_node->aiid] == 0 ||
 632                         match->action->node_critical[pattern_node->aiid] == 1);
 633
 634                 assert(!pr_n->deleted &&
 635                         "a node deleted by a rewrite step should not be a member of a node list");
 636
 637                 if (match_compliant && match->action->node_critical[pattern_node->aiid]) {
 638                         assert(get_irn_visited(host_node) <= irg_visit_phase &&
 639                                 "visited in a future phase?");
 640                         if (get_irn_visited(host_node) == irg_visit_phase) continue;
 641                 }
 642
 643                 /* check whether the current host graph node has not already
 644                  * been matched. But if it has, the according host nodes have
 645                  * to be allowed to be matched homomorphic with the current
 646                  * host node */
 647                 alredy_matched_pattern_node = pr_n->preimage;
 648                 if (alredy_matched_pattern_node == NULL ||
 649                         match->action->hom[pattern_node->aiid][alredy_matched_pattern_node->aiid])
 650                 {
 651
 652                         /* if the host node has NOT already been matched before
 653                          * remember the pattern node as already matched to the host node */
 654                         int matched_first = 0;
 655                         if (alredy_matched_pattern_node == NULL) {
 656                                 matched_first = 1;
 657                         }
 658
 659                         pr_n->preimage = pattern_node;
 660
 661                         /* add the pair (pattern_node, host_node) to the node map */
 662                         node_map[pattern_node->aiid] = host_node;
 663
 664                         /* check the condition if present */
 665                         if (!current_mop->condition || current_mop->condition(node_map, edge_map)) {
 666                                         /* call recursively to process the next matcher op */
 667                                         mpos++;
 668                                         match_rec();
 669                                         mpos--;
 670                                 }
 671
 672
 673
 674                         /* remove the pair (pattern_node, host_node) from the node map */
 675                         node_map[pattern_node->aiid] = NULL;
 676                         /* remember whether this matching is no more */
 677
 678
 679                         /* if the pattern node was the first node to be matched with
 680                          * the host node,  */
 681                         if (matched_first)
 682                                 pr_n->preimage = NULL;
 683
 684                         /* check whether matching is already complete */
 685                         if (match->n_matches == max_n_matches) return 1;
 686                         assert(match->n_matches < max_n_matches || max_n_matches == -1);
 687                         /* check whether backjumping is needed
 688                          * (this only happens for compliant matching) */
 689                         if (return_to_mop_index < mpos) return 1;
 690                         return_to_mop_index = length - 1;
 691                 }
 692         }
 693         /* matching not yet complete (or no backjumping needed),
 694          * do more matching if possible */
 695         return 0;
 696 }
 697
 698
 699
 700 static void match_edge_rec(
 701         ext_grs_node_t *pattern_node,
 702         ext_grs_edge_t *pattern_edge,
 703         ext_grs_node_t *other_pattern_node,
 704         ir_node *host_node, ir_edge_t *host_edge, ir_node *other_host_node)
 705 {
 706
 707         ext_grs_irn_private_t *pr_n;
 708         ext_grs_iredges_private_t *pr_e =
 709                 get_edge_private_data(host_edge, _ext_grs_private_ofs_e);
 710
 711         int matched_first = 0;
 712         int both_nodes_matched = 0;
 713         ext_grs_edge_t *already_matched_pattern_edge;
 714         ext_grs_node_t *already_matched_other_pattern_node;
 715
 716 #if DUMP_WHILE_MATCHING
 717         printf("%d: Checking %s%d -> %s%d (%s->%s) (%s->%s)\n", mpos, get_op_name(get_irn_op(host_node)), host_node->node_nr, get_op_name(get_irn_op(other_host_node)), other_host_node->node_nr, get_op_name(pattern_node->op), get_op_name(other_pattern_node->op), pattern_node->name, other_pattern_node->name);
 718 #endif
 719
 720         assert(
 721                 match->action->edge_critical[pattern_edge->aiid] == 0 ||
 722                 match->action->edge_critical[pattern_edge->aiid] == 1);
 723
 724         /* if node has already been delted on a rewrite step and it still reached
 725          * (maybe by a matching comming from the igrs Bad node) it is nevertheless
 726          * NOT matched! */
 727         pr_n = _ext_grs_get_irn_private(other_host_node);
 728         if (pr_n->deleted) {
 729                 assert(host_node == get_irg_bad(match->irg) &&
 730                         "this node has been deleted by a rewrite step, the only chance" &&
 731                         "to meet it should have been coming from the irgs bad node");
 732                 return;
 733         }
 734
 735         if (match_compliant) {
 736                 if (match->action->edge_critical[pattern_edge->aiid]) {
 737                         assert(pr_e->visited <= irg_visit_phase && "visited in a future phase?");
 738                         if (pr_e->visited == irg_visit_phase) return;
 739                 }
 740                 if (match->action->node_critical[other_pattern_node->aiid]) {
 741                         assert(get_irn_visited(other_host_node) <= irg_visit_phase &&
 742                                 "visited in a future phase?");
 743                         if (get_irn_visited(other_host_node) == irg_visit_phase) return;
 744                 }
 745         }
 746         /* check whether the op of the host edge matches
 747          * the op of the current pattern edge */
 748         if (get_irn_op(other_host_node) != other_pattern_node->op &&
 749                 ! _ext_grs_OP_IS_A(get_irn_opcode(other_host_node), get_op_code(other_pattern_node->op)))
 750                 return;
 751
 752         /* check whether the mode of the node at the other end of the host edge
 753          * matches the mode of the pattern node at the other end of the pattern edge */
 754         if (
 755                 /* if the other pattern node allows any mode, dont check the mode
 756                  * of the other host node at all */
 757                 other_pattern_node->mode != mode_ANY &&
 758                 /* otherwise check whether the modecode of the other
 759                  * pattern and the other host node are equal */
 760                 other_pattern_node->mode != get_irn_mode(other_host_node)
 761         ) return;
 762
 763         /* check whether the current host edge has not already been matched */
 764         already_matched_pattern_edge = pr_e->preimage;
 765         if ( already_matched_pattern_edge != NULL ) return;
 766
 767
 768         /* if both pattern nodes have already been matched, check whether the other
 769          * host nodes preimage equals the other pattern node */
 770         if (node_map[other_pattern_node->aiid] != NULL) {
 771                 /* in the case that both nodes are already matched check whether the
 772                  * current host edge connects these nodes */
 773                 if (node_map[other_pattern_node->aiid] != other_host_node) return;
 774                 both_nodes_matched = 1;
 775         }
 776         else {
 777                 /* if the current host edge is NOT loop... */
 778                 if (other_host_node != host_node) {
 779
 780                         /* check whether the host node at the other end of the current
 781                          * host edge has not already been matched OR, if it HAS, whether the already
 782                          * matched pattern node is permitted to be matched homomorphic with the
 783                          * pattern node at the other end of the current pattern edge */
 784                         already_matched_other_pattern_node = pr_n->preimage;
 785                         if (already_matched_other_pattern_node != NULL) {
 786                                 if (! match->action->hom
 787                                                 [other_pattern_node->aiid][already_matched_other_pattern_node->aiid]
 788                                 ) return;
 789                         }
 790                         else {
 791                                 /* if the other host node has not already been matched, this
 792                                  * is matching is for the first time */
 793                                 pr_n->preimage = other_pattern_node;
 794                                 matched_first = 1;
 795                         }
 796
 797                         /* add the pair (other_pattern_node, other_host_node) to the node map */
 798                         node_map[other_pattern_node->aiid] = other_host_node;
 799                 }
 800         }
 801
 802
 803         /* add the pair (pattern_edge, host_edge) to the node map */
 804         edge_map[pattern_edge->aiid] = host_edge;
 805         pr_e->preimage = pattern_edge;
 806
 807         /* check the condition if present */
 808         if (!prog[mpos].condition || prog[mpos].condition(node_map, edge_map)) {
 809                 /* call recursively to process the next matcher op */
 810                 mpos++;
 811 #if DUMP_WHILE_MATCHING
 812                 printf("found it.\n");
 813 #endif
 814                 match_rec();
 815                 mpos--;
 816         }
 817 #if DUMP_WHILE_MATCHING
 818         else if(prog[mpos].condition)
 819                 printf("Condition failed\n");
 820 #endif
 821
 822         /* if the current host edge is NOT loop... */
 823         if (! both_nodes_matched)
 824                 if (other_host_node != host_node) {
 825                         /* remove the pair (pattern_node, host_node) from the node map */
 826                         node_map[other_pattern_node->aiid] = NULL;
 827                 }
 828         edge_map[pattern_edge->aiid] = NULL;
 829         pr_e->preimage = NULL;
 830
 831         /* if the pattern node was the first node to be matched with
 832          * the host node... */
 833         if (matched_first)
 834                 pr_n->preimage = NULL;
 835 }
 836
 837
 838
 839
 840
 841
 842
 843
 844
 845
 846 static void match_preset_edge_rec(
 847                                                    ext_grs_node_t *pattern_node,
 848                                                    ext_grs_edge_t *pattern_edge,
 849                                                    ext_grs_node_t *other_pattern_node,
 850
 851                                                    ir_node *host_node, ir_edge_t *host_edge, ir_node *other_host_node)
 852 {
 853
 854         ext_grs_irn_private_t *pr_n;
 855         ext_grs_iredges_private_t *pr_e =
 856                 get_edge_private_data(host_edge, _ext_grs_private_ofs_e);
 857
 858         int matched_first = 0;
 859         int both_nodes_matched = 0;
 860         ext_grs_edge_t *already_matched_pattern_edge;
 861         ext_grs_node_t *already_matched_other_pattern_node;
 862
 863         assert(
 864                 match->action->edge_critical[pattern_edge->aiid] == 0 ||
 865                 match->action->edge_critical[pattern_edge->aiid] == 1);
 866
 867         /* if node has already been deleted on a rewrite step and it still reached
 868         * (maybe by a matching coming from the irgs Bad node) it is nevertheless
 869         * NOT matched! */
 870
 871         pr_n = _ext_grs_get_irn_private(other_host_node);
 872         if (pr_n->deleted) {
 873                 assert(host_node == get_irg_bad(match->irg) &&
 874                         "this node has been deleted by a rewrite step, the only chance" &&
 875                         "to meet it should have been coming from the irgs bad node");
 876                 return;
 877         }
 878
 879         if (match_compliant) {
 880                 if (match->action->edge_critical[pattern_edge->aiid]) {
 881                         assert(pr_e->visited <= irg_visit_phase && "visited in a future phase?");
 882                         if (pr_e->visited == irg_visit_phase) return;
 883                 }
 884                 if (match->action->node_critical[other_pattern_node->aiid]) {
 885                         assert(get_irn_visited(other_host_node) <= irg_visit_phase &&
 886                                 "visited in a future phase?");
 887                         if (get_irn_visited(other_host_node) == irg_visit_phase) return;
 888                 }
 889         }
 890         /* check wether the op of the host edge matches
 891         * the op of the current pattern edge */
 892         if (
 893                 get_irn_op(other_host_node) != other_pattern_node->op &&
 894                 ! _ext_grs_OP_IS_A(get_irn_opcode(other_host_node), get_op_code(other_pattern_node->op))
 895                 ) return;
 896
 897         /* check wether the mode of the node at the other end of the host edge
 898         * matches the mode of the pattern node at the other end of the pattern edge */
 899         if (
 900                 /* if the other pattern node allows any mode, dont check the mode
 901                 * of the other host node at all */
 902                 other_pattern_node->mode != mode_ANY &&
 903                 /* otherwise check wether the modecode of the other
 904                 * pattern and the other host node are equal */
 905                 other_pattern_node->mode != get_irn_mode(other_host_node)
 906                 ) return;
 907
 908         /* check wether the current host edge has not already been matched */
 909         already_matched_pattern_edge = pr_e->preimage;
 910         if ( already_matched_pattern_edge != NULL ) return;
 911
 912
 913         /* if both pattern nodes have already been matched, check wether the other
 914         * host nodes preimage equals the other pattern node */
 915         if (node_map[other_pattern_node->aiid] != NULL) {
 916                 /* in the case that both nodes are already matched check wether the
 917                 * current host edge connects these nodes */
 918                 if (node_map[other_pattern_node->aiid] != other_host_node) return;
 919                 both_nodes_matched = 1;
 920         }
 921         else {
 922                 /* if the current host edge is NOT loop... */
 923                 if (other_host_node != host_node) {
 924
 925                         /* check wether the host node at the other end of the current
 926                         * host edge has not alredy been matched OR, if it HAS, wether the already
 927                         * matched pattern node is permitted to be matched homomorphic with the
 928                         * pattern node at the other end of the current pattern edge */
 929                         already_matched_other_pattern_node = pr_n->preimage;
 930                         if (already_matched_other_pattern_node != NULL) {
 931                                 if (! match->action->hom
 932                                         [other_pattern_node->aiid][already_matched_other_pattern_node->aiid]
 933                                 ) return;
 934                         }
 935                         else {
 936                                 /* if the other host node has not already been matched, this
 937                                 * is matching is for the first time */
 938                                 pr_n->preimage = other_pattern_node;
 939                                 matched_first = 1;
 940                         }
 941
 942                         /* add the pair (other_pattern_node, other_host_node) to the node map */
 943                         node_map[other_pattern_node->aiid] = other_host_node;
 944                 }
 945         }
 946
 947
 948         /* add the pair (pattern_edge, host_edge) to the node map */
 949         edge_map[pattern_edge->aiid] = host_edge;
 950         pr_e->preimage = pattern_edge;
 951
 952         /* check the condition if present */
 953         if (!prog[mpos].condition || prog[mpos].condition(node_map, edge_map)) {
 954                 /* call recursively to process the next matcher op */
 955                 mpos++;
 956                 match_rec();
 957                 mpos--;
 958         }
 959
 960         /* if the current host edge is NOT loop... */
 961         if (! both_nodes_matched)
 962                 if (other_host_node != host_node) {
 963                         /* remove the pair (pattern_node, host_node) from the node map */
 964                         node_map[other_pattern_node->aiid] = NULL;
 965                 }
 966                 edge_map[pattern_edge->aiid] = NULL;
 967                 pr_e->preimage = NULL;
 968
 969                 /* if the pattern node was the first node to be matched with
 970                 * the host node... */
 971                 if (matched_first)
 972                         pr_n->preimage = NULL;
 973 }
 974
 975
 976
 977
 978
 979
 980
 981
 982
 983
 984
 985
 986
 987
 988
 989
 990 /* The matching loop, actually recursive but implemented as
 991  * while loop by using a (only conceptually existing) stack.
 992  * The stack is not implicitly materialized by appropriate
 993  * fields present in the match op structs.
 994  * */
 995 static void match_rec(void) {
 996
 997         ext_grs_match_op_t *current_mop = NULL;
 998
 999         ext_grs_edge_t *pattern_edge = NULL;
1000         ext_grs_node_t *pattern_node = NULL;
1001         ext_grs_node_t *other_pattern_node = NULL;
1002
1003         ir_node *host_node = NULL;
1004         ir_node *other_host_node = NULL;
1005         ir_edge_t *host_edge = NULL;
1006
1007
1008         assert(prog != NULL && "global ptr to matcher program is NULL");
1009
1010         /* if the hole match prog has been processed... */
1011         if (mpos >= length) {
1012                 /* ...a complete match has been found */
1013                 /* so add this complete match to the match object */
1014
1015                 if(match_negative_pattern == 0)
1016                         store_match();
1017                 else
1018                 {
1019                         found_negative = 1;
1020                         match->n_matches = 1;
1021                 }
1022                 return;
1023         }
1024
1025         current_mop = & prog[mpos];
1026         /* execute the current match op */
1027         /* if the current match op is a node-op... */
1028
1029         if(current_mop->kind == ext_grs_k_mop_preset)
1030         {
1031                 /* loop counters */
1032                 ir_op *current_op;
1033                 ir_mode *current_mode;
1034                 ir_opcode opc;
1035                 modecode mc;
1036
1037                 int matching_complete_or_backjump;
1038
1039                 pattern_node = current_mop->node;
1040                 current_mode = pattern_node->mode;
1041
1042                 host_node = positive_node_map[pattern_node->related_node->aiid];
1043                 current_op = host_node->op;
1044
1045                 /* Pattern_node == NAC node */
1046                 assert(pattern_node->related_node != NULL && "preset node is not related!!");
1047
1048                 opc = get_op_code(current_op);
1049                 mc  = get_mode_modecode(current_mode);
1050
1051
1052                 /* if there is an op condition, check whether it holds */
1053                 if (current_mop->op_condition && !current_mop->op_condition(current_op)) return;
1054
1055                 /* if there is an mode condition, check whether it holds */
1056                 if (current_mop->mode_condition && !current_mop->mode_condition(current_mode)) return;
1057
1058                 matching_complete_or_backjump =
1059                         match_preset_rec(pattern_node, current_mop, host_node);
1060
1061                 if (matching_complete_or_backjump) return;
1062
1063                 return;
1064         }
1065         else if(current_mop->kind == ext_grs_k_mop_preset_edge)
1066         {
1067                 ir_edge_t *host_edge;
1068                 ir_graph *irg = match->irg;
1069
1070                 pattern_edge = current_mop->edge;
1071                 pattern_node = current_mop->node;
1072
1073                 /* check  whether the given pattern node is incident to the given pattern edge */
1074                 assert(pattern_node == pattern_edge->func || pattern_node == pattern_edge->arg);
1075
1076                 host_edge = positive_edge_map[pattern_edge->related_edge->aiid];
1077                 edge_map[pattern_edge->aiid] = host_edge;
1078                 if(current_mop->condition && !current_mop->condition(node_map, edge_map))
1079                 {
1080                         mpos++;
1081                         match_rec();
1082                         mpos--;
1083                 }
1084
1085         }
1086         else if (current_mop->kind == ext_grs_k_mop_node) {
1087
1088                 /* loop counters */
1089                 int i,j;
1090                 int n_sub_ops;
1091                 /* inheritance related stuff */
1092                 ir_op **sub_op_array;
1093                 pattern_node = current_mop->node;
1094
1095
1096                 sub_op_array = _ext_grs_all_sub_ops_of_op[ get_op_code(pattern_node->op) ];
1097                 n_sub_ops = ARR_LEN(sub_op_array);
1098
1099                 /* FOR all sub ops of the pattern nodes op DO... */
1100                 /* Find all nodes in the host graph that have the same op or a sub_op as the pattern node: */
1101                 for (i = 0; i < n_sub_ops; i++) {
1102
1103                         ir_op *current_op = sub_op_array[i];
1104                         ir_mode *current_mode = pattern_node->mode;
1105                         ir_opcode opc = get_op_code(current_op);
1106                         modecode mc = get_mode_modecode(current_mode);
1107
1108                         int matching_complete_or_backjump;
1109
1110                         /* if there is an op condition, check whether it holds */
1111                         if (current_mop->op_condition && !current_mop->op_condition(current_op)) continue;
1112
1113                         /* if pattern nodes mode is ANY match for ALL modes */
1114                         if (current_mode == mode_ANY) {
1115                                 for (j = 0; j <= _ext_grs_max_modecode; j++) {
1116                                         /* if no mode condition present, simply perform matching */
1117                                         if (
1118                                                 current_mop->mode_condition &&
1119                                                 !current_mop->mode_condition(_ext_grs_mode_map[j])
1120                                         ) continue; /* ??? */
1121
1122                                         /* Start backtracking for all nodes in the host graph that have the current mop */
1123                                         matching_complete_or_backjump =
1124                                                 match_node_rec(pattern_node, current_mop, opc, j);
1125
1126                                         if (matching_complete_or_backjump) return;
1127                                 }
1128                         }
1129                         else {
1130                                 /* Even theres only ONE possible mode, the mode condition has to
1131                                  * be checked all the same! E.g. the user may have registered a
1132                                  * mode condition function which depends on a global state... */
1133                                 if (
1134                                         current_mop->mode_condition &&
1135                                         ! current_mop->mode_condition(current_mode) /* <<<  NOT may be WRONG!!!! */
1136                                 ) continue;
1137
1138                                 matching_complete_or_backjump =
1139                                         match_node_rec(pattern_node, current_mop, opc, mc);
1140
1141                                 if (matching_complete_or_backjump) return;
1142                         }
1143
1144                 }
1145                 return;
1146         }
1147         else if (current_mop->kind == ext_grs_k_mop_edge) {
1148
1149                 ir_graph *irg = match->irg;
1150
1151                 pattern_edge = current_mop->edge;
1152                 pattern_node = current_mop->node;
1153
1154                 /* check  whether the given pattern node is incident to the given pattern edge */
1155                 assert(pattern_node == pattern_edge->func || pattern_node == pattern_edge->arg);
1156
1157
1158
1159                 /* if the pattern edge is an outgoing (i.e. in-flow) edge... */
1160                 if (pattern_node == pattern_edge->func) {
1161
1162                         int i = -1; /* -1 for the block edge */
1163                         int upper_pos_bound;
1164
1165                         assert(node_map[pattern_node->aiid] != NULL &&
1166                                 "this node should have been matched already");
1167
1168                         other_pattern_node = pattern_edge->arg;
1169                         host_node = node_map[pattern_node->aiid];
1170
1171                         /* only Block nodes have NO block edge (i.e. an edge at pos = -1) */
1172                         if (get_irn_op(host_node) == op_Block) i = 0;
1173
1174                         /* if the current pattern edge gives a fixed edge pos... */
1175                         upper_pos_bound = get_irn_arity(host_node);
1176                         if (pattern_edge->pos != ext_grs_NO_EDGE_POS) {
1177                                 /* ...then we do NOT have to iterate over the edges.
1178                                  * Instead of that we can access and check the host edge directly: */
1179                                 i = pattern_edge->pos;
1180                                 upper_pos_bound = i + 1;
1181                         }
1182
1183                         /* FOR all outgoing (i.e. in-flow) edges of the pattern
1184                          * nodes current image DO */
1185                         for ( ; i < upper_pos_bound; i++) {
1186
1187                                 other_host_node = get_irn_n(host_node, i);
1188                                 host_edge = get_irn_edge(irg, host_node, i);
1189
1190                                 /* if theres no such edge this is no valid match */
1191                                 if (! host_edge) continue;
1192
1193                                 match_edge_rec(
1194                                         pattern_node, pattern_edge, other_pattern_node,
1195                                         host_node, host_edge, other_host_node);
1196
1197                                 if (match->n_matches == max_n_matches) return;
1198                                 assert(match->n_matches < max_n_matches || max_n_matches == -1);
1199
1200                                 if (return_to_mop_index < mpos) return;
1201                                 return_to_mop_index = length - 1;
1202
1203                         }
1204                         return;
1205                 }
1206
1207                 /* or an incoming (i.e. out-flow) edge otherwise */
1208                 else {
1209
1210                         assert(pattern_node == pattern_edge->arg &&
1211                                 "pattern node not incident to pattern edge");
1212
1213                         assert(node_map[pattern_node->aiid] != NULL &&
1214                                 "this node should have been matched already");
1215
1216                         other_pattern_node = pattern_edge->func;
1217                         host_node = node_map[pattern_node->aiid];
1218
1219                         foreach_out_edge(host_node, host_edge) {
1220                                 int edg_src_pos;
1221
1222                                 /* if the pattern edge determines a fixed pos as outgoing
1223                                  * (i.e. in-flow) edge  of its func node, check wether the
1224                                  * pos of the current edge does equal this determined pos */
1225                                 if (pattern_edge->pos != ext_grs_NO_EDGE_POS &&
1226                                         (edg_src_pos = get_edge_src_pos(host_edge)) != pattern_edge->pos)
1227                                         continue;
1228
1229                                 other_host_node = get_edge_src_irn(host_edge);
1230
1231                                 match_edge_rec(
1232                                         pattern_node, pattern_edge, other_pattern_node,
1233                                         host_node, host_edge, other_host_node);
1234
1235                                 if (match->n_matches == max_n_matches) return;
1236                                 assert(match->n_matches < max_n_matches || max_n_matches == -1);
1237
1238                                 if (return_to_mop_index < mpos) return;
1239                                 return_to_mop_index = length - 1;
1240
1241                         }
1242                         return;
1243
1244
1245                 }
1246
1247
1248         }
1249         else {
1250                 assert(current_mop->kind == ext_grs_k_mop_condition);
1251                 assert(current_mop->condition && "a conditon mop should have a condition function");
1252
1253                 /* check the condition */
1254                 if ( ! current_mop->condition(node_map, edge_map) ) return ;
1255
1256                 /* call recursively to process the next matcher op */
1257                 mpos++;
1258                 match_rec();
1259                 mpos--;
1260
1261                 return;
1262         }
1263
1264 }
1265
1266 ext_grs_match_t *ext_grs_match(
1267         ir_graph *irg, ext_grs_match_plan_t *plan, int n, int compliant)
1268 {
1269         ext_grs_graph_t *pattern = plan->action->pattern;
1270
1271         if (!irg) {
1272                 printf("module ext/grs: WARNING in function ext_grs_match()\n");
1273                 printf("  Given ir graph was NULL.\n\n");
1274                 return NULL;
1275         }
1276
1277         if (!plan) {
1278                 printf("module ext/grs: WARNING in function ext_grs_match()\n");
1279                 printf("  Given match plan was NULL.\n\n");
1280                 return NULL;
1281         }
1282
1283         /* get the private_data of the current irg */
1284         pr_g = _ext_grs_get_irg_private(irg);
1285
1286         if (!pr_g->matching_enabled) {
1287                 printf("module ext/grs: ERROR in function ext_grs_match()\n");
1288                 printf("  Matching is disabeled for the given irg.\n\n");
1289                 return NULL;
1290         }
1291
1292         /* allocate a new match object */
1293         match = (ext_grs_match_t *) malloc(sizeof(*match));
1294         if (match == NULL)
1295                 return NULL;
1296         memset(match, 0, sizeof(*match));
1297         /* init that match object */
1298         match->action = plan->action;
1299         match->irg = irg;
1300         match->n_nodes = pattern->n_nodes;
1301         match->n_edges = pattern->n_edges;
1302         match->max_node_id = plan->action->max_node_aiid;
1303         match->max_edge_id = plan->action->max_edge_aiid;
1304         match->compliant = compliant;
1305
1306         /* initialize this match's internal obstack */
1307         obstack_init(& match->obst);
1308
1309         /* if program has length 0 just return an empty match */
1310         if(plan->length[0] <= 0 || n == 0) {
1311                 match->n_matches = 0;
1312                 return match;
1313         }
1314
1315         /* ..................... WHAT DOES THE FOLLOWING???? ............................. */
1316
1317
1318         max_n_matches = n;
1319         match_compliant = compliant;
1320
1321         irg_visit_phase = get_irg_visited(irg) + 1;
1322         set_irg_visited(irg, irg_visit_phase);
1323
1324         /* if node map is not great enough extend it */
1325 #if 0
1326         old_size = ARR_LEN(node_map);
1327         ARR_EXTO(ir_node*, node_map, match->action->max_node_aiid + 1);
1328         /* if array resized reset it to '0' */
1329         if (old_size < ARR_LEN(node_map))
1330                 memset(node_map, 0, sizeof(*node_map) * ARR_LEN(node_map));
1331         /* if edge map is not great enough extend it */
1332         old_size = ARR_LEN(edge_map);
1333         ARR_EXTO(ir_edge_t*, edge_map, match->action->max_edge_aiid + 1);
1334         /* if array resized reset it to '0' */
1335         if (old_size < ARR_LEN(edge_map))
1336                 memset(edge_map, 0, sizeof(*edge_map) * ARR_LEN(edge_map));
1337 #endif
1338
1339         node_map = (ir_node **) alloca((match->action->max_node_aiid + 1) * sizeof(*node_map));
1340         memset(node_map, 0, sizeof(*node_map) * (match->action->max_node_aiid + 1));
1341         edge_map = (ir_edge_t **) alloca((match->action->max_edge_aiid + 1) * sizeof(*edge_map));
1342         memset(edge_map, 0, sizeof(*edge_map) * (match->action->max_edge_aiid + 1));
1343
1344
1345         /* init the list of found matches */
1346         LC_INIT_LIST_HEAD(& match_list_head.list);
1347
1348         /* .................................................................................... */
1349
1350         /* execute the search plan */
1351         return_to_mop_index = plan->length[0] - 1;
1352         length = plan->length[0];
1353         prog = plan->progs[0];
1354         mpos = 0;
1355         match_negative_pattern = 0;
1356         match_rec();
1357
1358         /* transfer the found matches to the match result object */
1359         fill_match_result(plan);
1360
1361         pr_g = NULL;
1362
1363         return match;
1364 }
1365
1366 static int _get_op_n_args(ir_op *op) {
1367
1368         switch (op->opar)
1369         {
1370                 case oparity_zero: return 0;
1371                 case oparity_unary: return 1;
1372                 case oparity_binary: return 2;
1373                 case oparity_trinary: return 3;
1374                 default: return 0;
1375         }
1376
1377         return 0;
1378 }
1379
1380 int compute_new_arity(ir_node **node_map, ir_node **repl_node_map, ext_grs_node_t *pat_node, ext_grs_node_t *replace_node, int repl_node_greatest_edge_pos)
1381 {
1382         int n_free_edges = 0;
1383         int old_arity =0, new_arity = 0;
1384         int k;
1385         ir_node *host_node;
1386
1387
1388         /* get the ir node matched by the the pattern node associated with the
1389         * current replacement node */
1390         host_node = node_map[pat_node->aiid];
1391         assert(host_node && "replacement node associated with NULL pattern node");
1392         old_arity = get_irn_arity(host_node);
1393
1394 /*      if(host_node->node_nr == 675)
1395                 printf("found\n"); */
1396
1397         /* compute the number of free slots in the current
1398         * in array (free means NULL or pointing to a Bad node) */
1399         for (k = 0; /*(get_irn_opcode(host_node) == iro_Block) ? 0 : -1;*/ k < old_arity; k++) {
1400                 ir_node *arg = get_irn_n(host_node, k);
1401                 if (!arg || get_irn_op(arg) == op_Bad)
1402                         n_free_edges++;
1403         }
1404
1405
1406         if (repl_node_greatest_edge_pos == ext_grs_NO_EDGE_POS) {
1407                 new_arity = old_arity + replace_node->n_append_edges - n_free_edges; // New arity may also be shorter!
1408                         //old_arity + MAX(0, (replace_node->n_append_edges - n_free_edges));
1409         }
1410         else {
1411                 assert(repl_node_greatest_edge_pos >= -1 && "invalid edge pos encountered");
1412                 new_arity = MAX(repl_node_greatest_edge_pos + 1,  old_arity + replace_node->n_append_edges - n_free_edges);
1413                    //MAX(repl_node_greatest_edge_pos + 1, old_arity) + MAX(0, (replace_node->n_append_edges - n_free_edges));
1414         }
1415         // new_arity = MAX(new_arity, _get_op_n_args(replace_node->op));
1416         return(new_arity);
1417 }
1418
1419
1420 void ext_grs_finish_match(ext_grs_match_t *match, int n, int *which) {
1421
1422         ext_grs_action_t *action;
1423         ir_node **node_map;
1424         const ir_edge_t **edge_map;
1425
1426         ir_node **repl_node_map;
1427         ir_edge_t **repl_edge_map;
1428         ir_node *host_node;
1429
1430         int n_matches;
1431         int i, j, k;
1432         lc_list_t *pos;
1433
1434         ir_node *bad;
1435         ext_grs_irg_private_t *pr_g;
1436         ir_graph *remeber_current_irg = current_ir_graph;
1437
1438         /* array of positions where the next edge without given pos can be appended, the
1439          * index is the replacement aiid of the replacement node the edge is incoming on */
1440         int *next_append_pos;
1441
1442         int *repl_edge_positions;
1443         int *repl_node_greatest_edge_pos;
1444
1445
1446         if (!match) {
1447                 printf("module ext/grs: ERROR in function ext_grs_finish_match()\n");
1448                 printf("  Given match object was NULL.\n");
1449                 printf("  No rewrite has been performed.\n\n");
1450                 return;
1451         }
1452
1453
1454         action = match->action;
1455         pr_g = _ext_grs_get_irg_private(match->irg);
1456
1457         if (!pr_g->matching_enabled && action->kind != ext_grs_k_test) {
1458                 printf("module ext/grs: ERROR in function ext_grs_finish_match()\n");
1459                 printf("  Tried to finish an action which is not of kind test, while\n");
1460                 printf("  matching has been disabled for the respective ir graph.\n");
1461                 printf("  This means that some internal data needed in this is no more");
1462                 printf("  there. So no transformation of the ir graph has been done.\n\n");
1463
1464                 obstack_free(& match->obst, NULL);
1465                 free(match);
1466
1467                 return;
1468         }
1469
1470         bad = get_irg_bad(match->irg);
1471
1472         //repl_node_map = alloca(sizeof(*repl_node_map) * (action->max_repl_node_aiid + 1));    Allocated on the obst now to be available after rewrite
1473         repl_edge_map = alloca(sizeof(*repl_edge_map) * (action->max_repl_edge_aiid + 1));
1474         next_append_pos = alloca(sizeof(*next_append_pos) * (action->max_repl_node_aiid + 1));
1475         repl_edge_positions = alloca(sizeof(*repl_edge_positions) * (action->max_repl_edge_aiid + 1));
1476         repl_node_greatest_edge_pos =
1477                 alloca(sizeof(*repl_node_greatest_edge_pos) * (action->max_repl_node_aiid + 1));
1478
1479         /* if action is a test no replacement will be done */
1480         if (action->kind == ext_grs_k_test) n = 0;
1481
1482         current_ir_graph = match->irg;
1483
1484         if (n == ext_grs_ALL) {
1485                 n_matches = match->n_matches;
1486         }
1487         else if (n >= 0) {
1488                 if (n > match->n_matches) {
1489                         printf("module ext/grs: WARNING in function ext_grs_finish_match()\n");
1490                         printf("  Given number of matches (%d) to be replaced exceeds the", n);
1491                         printf("  number of matches found (%d).\n\n", match->n_matches);
1492                         n_matches = match->n_matches;
1493                 }
1494                 else {
1495                         n_matches = n;
1496                 }
1497         }
1498         else {
1499                 printf("module ext/grs: ERROR in function ext_grs_finish_match()\n");
1500                 printf("  Given number of matches to be replaced is invalid: %d.\n", n);
1501                 printf("  No rewrite has been performed.\n\n");
1502
1503                 obstack_free(& match->obst, NULL);
1504                 free(match);
1505
1506                 return;
1507         }
1508
1509         /* parallel rewrites are forbidden for match objects,
1510          * which are not prepared for such things */
1511         if ( !match->compliant && n_matches > 1 ) {
1512                 n_matches = 1;
1513                 printf("module ext/grs: WARNING in function ext_grs_finish_match()\n");
1514                 printf("  Parallel rewriting was demanded but the given match object\n");
1515                 printf("  is not compliant. So only ONE match is replaced.\n\n");
1516         }
1517
1518         /* check for empty which array */
1519         if (n != ext_grs_ALL && n != 0 && !which) {
1520                 printf("module ext/grs: ERROR in function ext_grs_finish_match()\n");
1521                 printf("  The set of match numbers to be replaced was NULL.\n");
1522                 printf("  No rewrite has been performed.\n\n");
1523
1524                 obstack_free(& match->obst, NULL);
1525                 free(match);
1526
1527                 return;
1528         }
1529
1530
1531
1532         /* perform replacement of several matches */
1533         //i = 0;
1534         for(i = 0; i < n_matches; i++)
1535         {
1536                 // while (i < n_matches) {
1537
1538                 repl_node_map = obstack_alloc(&(match->obst), sizeof(*repl_node_map) * (action->max_repl_node_aiid + 1)); //)alloca(sizeof(*repl_node_map) * (action->max_repl_node_aiid + 1));
1539                 memset(repl_node_map, 0, sizeof(*repl_node_map) * (action->max_repl_node_aiid + 1));
1540                 memset(repl_edge_map, 0, sizeof(*repl_edge_map) * (action->max_repl_edge_aiid + 1));
1541
1542                 /* get the node and edge map of the current match */
1543                 if (n == ext_grs_ALL) {
1544                         match->repl_nodes[i] = repl_node_map;
1545                         node_map = match->nodes[i];
1546                         edge_map = match->edges[i];
1547                 }
1548                 else {
1549                         if (which[i] > match->n_matches) {
1550                                 printf("module ext/grs: ERROR in function ext_grs_finish_match()\n");
1551                                 printf("  A given match number exceeds the number of found matches.\n");
1552                                 printf("  No rewrite is performed for this number.\n\n");
1553
1554 //                              obstack_free(& match->obst, NULL);
1555 //                              free(match);
1556
1557                                 continue;
1558                         }
1559                         match->repl_nodes[which[i]] = repl_node_map;
1560                         node_map = match->nodes[which[i]];
1561                         edge_map = match->edges[which[i]];
1562                 }
1563
1564
1565
1566                 /* Before any graph transformations are done...
1567                  * ...the eval-in functions of the current action are evaluated for
1568                  * the current node and edge map */
1569                 lc_list_for_each(pos, &action->listed_evals) {
1570                         /* get the current eval descriptor...  */
1571                         ext_grs_eval_descr_t *descr =
1572                                 lc_list_entry(pos, ext_grs_eval_descr_t, eval_list);
1573                         /* get the current eval-in function... */
1574                         if(descr->eval_in != NULL) // AS
1575                         {
1576                                 ext_grs_eval_in_func_t in_func = descr->eval_in;
1577                                 /* ...and call it */
1578                                 descr->data = in_func(node_map, edge_map);
1579                         }
1580
1581                 }
1582
1583
1584
1585
1586
1587                 /* First: remove all remove edges of the pattern */
1588                 lc_list_for_each(pos, & action->pattern->edges) {
1589
1590                         ir_node *n, *in;
1591                         int edge_pos;
1592                         const ir_edge_t *remove_edge;
1593                         ext_grs_edge_t *pattern_edge =
1594                                 lc_list_entry(pos, ext_grs_edge_t, edge_list);
1595
1596                         assert(
1597                                 (
1598                                         pattern_edge->kind == ext_grs_k_edge ||
1599                                         pattern_edge->kind == ext_grs_k_pseudo_edge
1600                                 ) && "wrong kind encountered in edge list"
1601                         );
1602
1603                         /* pseudo edges can't be removed (because they are not mapped) */
1604                         if (pattern_edge->kind != ext_grs_k_edge) continue;
1605                         /* check whether the pattern edge is to be kept */
1606                         if (action->pattern_edge_kept[pattern_edge->aiid] >= 0) continue;
1607                         remove_edge = edge_map[pattern_edge->aiid];
1608
1609                         n = get_edge_src_irn(remove_edge);
1610                         in = get_irn_n(n, 0);
1611                         edge_pos = get_edge_src_pos(remove_edge);
1612
1613                         if(n->node_nr == 675)
1614                                 printf("found");
1615
1616                         /* let the remove_edges src node point to a Bad node, for
1617                          * a complete removal is not permitted by the FIRM syntax */
1618                 set_irn_n(
1619                                 get_edge_src_irn(remove_edge),
1620                                 get_edge_src_pos(remove_edge),
1621                                 bad);
1622                 }
1623
1624
1625
1626
1627
1628                 /* Second: Go through all replacement node, insert the new ones and
1629                  * retype the kept ones if necessary. Furthermore establish a map
1630                  * which maps replacement node aiids to ir node pointers. */
1631                 for (j = 0; j <= action->max_repl_node_aiid; j++) {
1632
1633                         ext_grs_node_t *replace_node = action->replacement_nodes[j];
1634                         ir_node *block = NULL;
1635
1636                         ir_node **new_in;
1637                         int old_arity = 0;
1638                         int new_arity;
1639
1640                         /* private area of a host node */
1641                         ext_grs_irn_private_t *pr_n;
1642
1643                         repl_node_greatest_edge_pos[j] = ext_grs_NO_EDGE_POS;
1644
1645                         /* check for gaps in the set of aiids */
1646                         if (!replace_node) continue;
1647
1648                         assert (action->replacement_node_kept[j] >= -1 && "invalid entry found");
1649
1650
1651                         /* for the current replacement node determine the positions of the
1652                          * outgoing (i.e. inflowing) edges to be newly inserted and the
1653                          * greatest pos among the outgoing (i.e. in-flowing) edges of each
1654                          * node */
1655                         lc_list_for_each (pos, & replace_node->edges[ext_grs_in]) {
1656                                 ext_grs_edge_t *in_edge = lc_list_entry(pos, ext_grs_edge_t, list[ext_grs_in]);
1657
1658                                 if (in_edge->position_func) {
1659                                         int h;
1660                                         assert(in_edge->pos == ext_grs_NO_EDGE_POS &&
1661                                                 "a replacement edge with pos function should not have a fixed position");
1662                                         assert(action->replacement_edge_kept[in_edge->aiid] == -1 &&
1663                                                 "a replacement edge with pos function is supposed to be newly inserted");
1664                                         h = in_edge->position_func(in_edge, node_map, edge_map);
1665                                         repl_edge_positions[in_edge->aiid] = h;
1666                                         repl_node_greatest_edge_pos[j] = MAX(h, repl_node_greatest_edge_pos[j]);
1667                                 }
1668                                 else if (in_edge->pos != ext_grs_NO_EDGE_POS) {
1669
1670                                         /*      Was soll diese Assertion?
1671                                                 Kept-Edges duerfen keine feste Position haben oder wie?
1672                                                 Besser: Pruefe die neue Position auf Gleichheit mit der alten!
1673
1674                                                 Warum trat diese Assertion frueher nicht auf? */
1675
1676                                         /*assert(action->replacement_edge_kept[in_edge->aiid] == -1 &&
1677                                                 "a replacement edge with fixed position supposed to be newly inserted"); */
1678                                         repl_edge_positions[in_edge->aiid] = in_edge->pos;
1679                                         repl_node_greatest_edge_pos[j] =
1680                                                 MAX(in_edge->pos, repl_node_greatest_edge_pos[j]);
1681                                 }
1682                         }
1683
1684
1685                         /* if node is to be newly inserted */
1686                         if (action->replacement_node_kept[j] == -1) {
1687
1688                                 ir_opcode opc;
1689                                 modecode mc;
1690
1691                                 if (repl_node_greatest_edge_pos[j] == ext_grs_NO_EDGE_POS) {
1692                                         new_arity = replace_node->n_append_edges;
1693                                 }
1694                                 else {
1695                                         assert(repl_node_greatest_edge_pos[j] >= -1 && "invalid edge pos encountered");
1696                                         new_arity = repl_node_greatest_edge_pos[j] + 1 + replace_node->n_append_edges;
1697                                 }
1698                                 new_arity = MAX(new_arity, _get_op_n_args(replace_node->op));
1699
1700                                 /* non Block nodes initially get a Bad block, block nodes a NULL block */
1701                                 if (replace_node->op != op_Block)
1702                                         block = bad;
1703                                 else
1704                                         block = NULL;
1705
1706                                 if (new_arity > 0) {
1707                                         new_in = alloca( sizeof(*new_in) * new_arity );
1708                                         for (k = 0; k < new_arity; k++)
1709                                                 new_in[k] = bad;
1710                                         /* create a new node */
1711                                         host_node = new_ir_node(
1712                                                                 NULL, match->irg, block,
1713                                                                 replace_node->op, replace_node->mode,
1714                                                                 new_arity, new_in);
1715                                 }
1716                                 else {
1717                                         host_node = new_ir_node(
1718                                                                 NULL, match->irg, block,
1719                                                                 replace_node->op, replace_node->mode,
1720                                                                 0, NULL);
1721                                 }
1722
1723                                 /* insert the new node in the respective node list */
1724                                 opc = get_irn_opcode(host_node);
1725                                 mc = get_irn_modecode(host_node);
1726
1727                                 pr_n = _ext_grs_get_irn_private(host_node);
1728                                 lc_list_add(&pr_n->node_list, & _ext_grs_NODE_LIST(pr_g, opc, mc));
1729                         }
1730                         /* otherwise give the already existing node a new op or mode (if necessary) */
1731                         else {
1732
1733                                 /* the pattern node associated with the kept replace node */
1734                                 ext_grs_node_t *pat_node = action->nodes[action->replacement_node_kept[j]];
1735                                 /* tells whether a preserved node is changed somehow (op or mode) */
1736                                 int op_or_mode_changed = 0;
1737                                 int old_arity, new_arity;
1738                                 ir_node *old_node = NULL;
1739
1740                                 host_node = node_map[pat_node->aiid];
1741                                 old_arity = get_irn_arity(host_node);
1742                                 new_arity = compute_new_arity(node_map, repl_node_map, pat_node, replace_node, repl_node_greatest_edge_pos[j]);
1743
1744 #if 0
1745                                 int n_free_edges = 0;
1746
1747
1748                                 /* get the ir node matched by the the pattern node associated with the
1749                                  * current replacement node */
1750                                 host_node = node_map[pat_node->aiid];
1751                                 assert(host_node && "replacement node associated with NULL pattern node");
1752                                 old_arity = get_irn_arity(host_node);
1753
1754                                 /* compute the number of free slots in the current
1755                                  * in array (free means NULL or pointing to a Bad node) */
1756                                 for (k = -1; k < old_arity; k++) {
1757                                         ir_node *arg = get_irn_n(host_node, k);
1758                                         if (!arg || get_irn_op(arg) == op_Bad)
1759                                                 n_free_edges++;
1760                                 }
1761
1762
1763
1764                                 if (repl_node_greatest_edge_pos[j] == ext_grs_NO_EDGE_POS) {
1765                                         new_arity =
1766                                                 old_arity + MAX(0, (replace_node->n_append_edges - n_free_edges));
1767                                 }
1768                                 else {
1769                                         assert(repl_node_greatest_edge_pos[j] >= -1 && "invalid edge pos encountered");
1770                                         new_arity = MAX(repl_node_greatest_edge_pos[j] + 1, old_arity) +
1771                                                                                 MAX(0, (replace_node->n_append_edges - n_free_edges));
1772                                 }
1773                                 new_arity = MAX(new_arity, _get_op_n_args(replace_node->op));
1774 #endif
1775
1776
1777
1778                                 /* change op if necessary */
1779                                 if ( pat_node->op != replace_node->op || pat_node->mode != replace_node->mode) {
1780
1781                                         /* if op changes from Block to something else
1782                                          * a bad block will be inserted */
1783                                         if (get_irn_op(host_node) == op_Block && replace_node->op != op_Block) {
1784                                                 assert(0 && "Not possible right now");
1785                                                 set_irn_op(host_node, replace_node->op);
1786                                                 set_nodes_block(host_node, bad);
1787                                         }
1788                                         /* if op changes to Block from something else
1789                                          * the Block edge will be deleted */
1790                                         else if (get_irn_op(host_node) != op_Block && replace_node->op == op_Block) {
1791                                                 assert(0 && "Not possible right now");
1792                                                 assert(get_irn_op(host_node) != op_Bad && "nodes op should change");
1793                                                 set_irn_n(host_node, -1, NULL);
1794                                                 set_irn_op(host_node, replace_node->op);
1795                                         }
1796                                         /* simply change the op otherwise */
1797                                         else {
1798
1799                                                 ir_node *exchange_node;
1800                                                 //new_arity = compute_new_arity(node_map, repl_node_map, pat_node, replace_node, repl_node_greatest_edge_pos[j]);
1801
1802                                                 /* if the edges to be inserted require a greater in-array, create one */
1803                                                 //if (old_arity != new_arity) {
1804                                                         new_in = alloca( sizeof(*new_in) * new_arity );
1805                                                         for (k = 0; k < new_arity; k++) {
1806                                                                 if (k < old_arity)
1807                                                                         new_in[k] = get_irn_n(host_node, k);
1808                                                                 else
1809                                                                         new_in[k] = bad;
1810                                                         }
1811                                                 //}
1812                                                 exchange_node = new_ir_node(NULL, current_ir_graph, get_nodes_block(host_node), replace_node->op, replace_node->mode/*get_irn_mode(host_node)*/, new_arity, new_in);
1813                                                 old_node = host_node;
1814                                                 exchange(host_node, exchange_node);
1815                                                 repl_node_map[j] = exchange_node;
1816                                                 host_node = exchange_node;
1817
1818                                                 //set_irn_op(host_node, replace_node->op);
1819                                         }
1820                                         /* remember op or mode was changed */
1821                                         op_or_mode_changed = 1;
1822                                 }
1823                                 else if(old_arity < new_arity)
1824                                 {
1825                                         /* if the edges to be inserted require a greater in-array, create one */
1826                                         // op or mode are not changed, we do not need to insert a new node and exchange it
1827                                         // This is the case e.g. for Phi, Sync or Block nodes.
1828                                         if (old_arity < new_arity) {
1829                                                 new_in = alloca( sizeof(*new_in) * new_arity );
1830                                                 for (k = 0; k < new_arity; k++) {
1831                                                         if (k < old_arity)
1832                                                                 new_in[k] = get_irn_n(host_node, k);
1833                                                         else
1834                                                                 new_in[k] = bad;
1835                                                 }
1836                                                 /* note: a nodes block is preserved by set_irn_in() */
1837                                                 set_irn_in(host_node, new_arity, new_in);
1838                                         }
1839                                 }
1840 #if 0
1841                                 // This is done by inserting a new node and exchanging now.
1842                                 /* or change mode if necessary */
1843                                 if ( pat_node->mode != replace_node->mode ) {
1844                                         set_irn_mode(host_node, replace_node->mode);
1845                                         /* remember node was changed */
1846                                         op_or_mode_changed = 1;
1847                                 }
1848 #endif
1849
1850                                 /* if mode or op was changed this node must be
1851                                  * moved to another node list */
1852
1853                                 /* Lists:        each node contains in its private data the list head of the
1854                                                          list he resides in. */
1855
1856                                 if (op_or_mode_changed) {
1857
1858                                         ir_opcode opc = get_irn_opcode(host_node);
1859                                         modecode mc = get_irn_modecode(host_node);
1860
1861                                         pr_n = _ext_grs_get_irn_private(host_node);
1862
1863                                         if(old_node == NULL)
1864                                         {
1865                                                 lc_list_move(&pr_n->node_list, & _ext_grs_NODE_LIST(pr_g, opc, mc));
1866                                         }
1867                                         else
1868                                         {
1869                                                 // exchange was used
1870                                                 ext_grs_irn_private_t *pr_n_old;
1871
1872                                                 pr_n_old = _ext_grs_get_irn_private(old_node);
1873                                                 lc_list_add(&pr_n->node_list, & _ext_grs_NODE_LIST(pr_g, opc, mc));
1874                                                 lc_list_del(&pr_n_old->node_list/*, & _ext_grs_NODE_LIST(pr_g, opc, mc)*/);
1875                                         }
1876
1877                                 }
1878                         }
1879
1880                         /* store the pos where the first edge with unspecified pos can be inserted */
1881                         for(k = (get_irn_opcode(host_node) == iro_Block) ? 0 : -1; k < get_irn_arity(host_node); k++) {
1882                                 ir_node *arg = get_irn_n(host_node, k);
1883                                 if (!arg || get_irn_op(arg) == op_Bad)
1884                                 {
1885                                         next_append_pos[j] = k;
1886                                         break; // AS
1887                                 }
1888                         }
1889
1890                         /* set up the map of replace nodes to host graph nodes */
1891                         repl_node_map[replace_node->aiid] = host_node;
1892
1893                         assert(
1894                                 (
1895                                         get_op_code(get_irn_op(host_node)) == get_op_code(replace_node->op) ||
1896                                         _ext_grs_OP_IS_A(
1897                                                 get_op_code(get_irn_op(host_node)), get_op_code(replace_node->op)
1898                                         )
1899                                 )
1900                                 && "replace map should map nodes with compatible op");
1901                 }
1902
1903
1904
1905
1906
1907
1908                 /* Third: insert all edges not associated with an pattern edge */
1909                 for (j = 0; j <= action->max_repl_edge_aiid; /* AS n_replacement_edges;*/ j++) {
1910
1911                         ext_grs_edge_t *replace_edge = action->replacement_edges[j];
1912                         ext_grs_node_t *rpl_src_node, *rpl_tgt_node;
1913
1914                         ir_node *host_src_node, *host_tgt_node;
1915
1916 /*                      if(j == 12)
1917                                 printf("found!"); */
1918
1919                         /* there might be gaps in the array, if an potential aiid
1920                          * is not assigned to an edge */
1921                         if (!replace_edge) continue;
1922
1923                         /* if edge not to be newly inserted, skip this edge */
1924                         if (action->replacement_edge_kept[replace_edge->aiid] >= 0) continue;
1925
1926                         rpl_src_node = replace_edge->func;
1927                         rpl_tgt_node = replace_edge->arg;
1928                         host_src_node = repl_node_map[rpl_src_node->aiid];
1929                         host_tgt_node = repl_node_map[rpl_tgt_node->aiid];
1930
1931                         assert(
1932                                 (
1933                                         get_op_code(get_irn_op(host_src_node)) == get_op_code(rpl_src_node->op) ||
1934                                         _ext_grs_OP_IS_A(
1935                                                 get_op_code(get_irn_op(host_src_node)), get_op_code(rpl_src_node->op)
1936                                         )
1937                                 )
1938                                 && "replace map should map nodes with compatible op");
1939
1940                         assert(
1941                                 (
1942                                         get_op_code(get_irn_op(host_tgt_node)) == get_op_code(rpl_tgt_node->op) ||
1943                                         _ext_grs_OP_IS_A(
1944                                                 get_op_code(get_irn_op(host_tgt_node)), get_op_code(rpl_tgt_node->op)
1945                                         )
1946                                 )
1947                                 && "replace map should map nodes with compatible op");
1948
1949                         /* if the host src (i.e. func) node is a Bad node */
1950                         if (get_irn_op(host_src_node) == op_Bad) {
1951                                 printf("module ext/grs: ERROR in function ext_grs_finish_match()\n");
1952                                 printf("  malformed replacement graph: Bad node cannot have an incoming\n");
1953                                 printf("  edge, edge was not inserted!\n");
1954                                 continue;
1955                         }
1956
1957                         /* insert and edge with specified position */
1958                         if (replace_edge->pos != ext_grs_NO_EDGE_POS) {
1959                                 if (replace_edge->pos == -1 && get_irn_op(host_tgt_node) != op_Block) {
1960                                         printf("module ext/grs: ERROR in function ext_grs_finish_match()\n");
1961                                         printf("  malformed replacement graph: incomming edge has pos -1, but\n");
1962                                         printf("  the argument is NOT a Block node! No edge inserted.\n");
1963                                         continue;
1964                                 }
1965                                 if (replace_edge->pos == -1 && get_irn_op(host_src_node) == op_Block) {
1966                                         printf("module ext/grs: ERROR in function ext_grs_finish_match()\n");
1967                                         printf("  malformed replacement graph: incomming edge has pos -1, but!\n");
1968                                         printf("  the src node is a Block node! No edge inserted.\n");
1969                                         continue;
1970                                 }
1971                                 set_irn_n(host_src_node, replace_edge->pos, host_tgt_node);
1972                         }
1973                         /* if no position is specified the edge is inserted to
1974                          * free places of the in-array */
1975                         else {
1976
1977                                 ir_node *arg;
1978                                 for (k = next_append_pos[rpl_src_node->aiid]; ; k++) {
1979                                         arg = get_irn_n(host_src_node, k);
1980                                         if (!arg || get_irn_op(arg) == op_Bad) break;
1981                                 }
1982
1983                                 assert(k < get_irn_arity(host_src_node) && "append pos exceeds in-array");
1984                                 set_irn_n(host_src_node, k, host_tgt_node);
1985                                 next_append_pos[rpl_src_node->aiid] =
1986                                                 MAX(k, next_append_pos[rpl_src_node->aiid] + 1);
1987                         }
1988                 }
1989
1990
1991                 /* Fourth: remove all nodes to be removed and all incident edges */
1992                 lc_list_for_each(pos, & action->pattern->nodes) {
1993
1994                         ext_grs_node_t *pat_node =
1995                                 lc_list_entry(pos, ext_grs_node_t, node_list);
1996
1997                         /* private area of a host node */
1998                         ext_grs_irn_private_t *pr_n;
1999
2000                         if (pat_node->kind == ext_grs_k_node) {
2001
2002                                 const ir_edge_t *edge;
2003                                 const ir_edge_t *ne;
2004                                 ir_node *remove_host_node;
2005
2006                                 /* if node is to be kept it is skiped */
2007                                 if (action->pattern_node_kept[pat_node->aiid] >= 0) continue;
2008                                 assert(pat_node->kind == ext_grs_k_node && "no pseudo node expected");
2009
2010                                 /* get the host the pat node is maped to, then remove it */
2011                                 remove_host_node = node_map[pat_node->aiid];
2012                                 assert(remove_host_node && "a pattern node should have been matched");
2013                                 /* all out edges of that node have to be changed that they
2014                                  * point to the graphs bad node */
2015                                 foreach_out_edge_safe(remove_host_node, edge, ne) {
2016                                         set_irn_n(get_edge_src_irn(edge), get_edge_src_pos(edge), bad);
2017                                 }
2018                                 /* all in edges of the remove node have also altered that they point to bad */
2019                                 for (j = 0; j < get_irn_arity(remove_host_node); j++) {
2020                                         set_irn_n(remove_host_node, j, bad);
2021                                 }
2022                                 /* remove the node from the node list */
2023                                 pr_n = _ext_grs_get_irn_private(remove_host_node);
2024                                 if ( ! pr_n->deleted ) {
2025                                         lc_list_del(&pr_n->node_list);
2026                                         pr_n->deleted = 1;
2027                                 }
2028                         }
2029                 }
2030
2031
2032                 /* After each graph transformations ...
2033                  * ...the eval-out functions of the current action are evaluated for
2034                  * the current node and edge map of the replacement graph biuld during
2035                  * the graph transforamtion */
2036                 lc_list_for_each(pos, &action->listed_evals) {
2037                         /* get the current eval descriptor...  */
2038                         ext_grs_eval_descr_t *descr =
2039                                 lc_list_entry(pos, ext_grs_eval_descr_t, eval_list);
2040                         /* get the current eval-in function... */
2041                         if(descr->eval_out != NULL) // AS
2042                         {
2043                                 ext_grs_eval_out_func_t in_func = descr->eval_out;
2044                                 /* ...and call it */
2045                                 in_func(repl_node_map, repl_edge_map, node_map, descr->data);
2046                         }
2047                 }
2048
2049                 //i++;
2050
2051         }
2052         current_ir_graph = remeber_current_irg;
2053 }
2054
2055 /* AS: Added to keep the match node map etc after a match
2056    When this information is not needed any more, ext_grs_free_match has to be called. */
2057
2058 void ext_grs_free_match(ext_grs_match_t *match)
2059 {
2060         /* clear the match object */
2061         /* first: free the match objects obstack */
2062         obstack_free(&(match->obst), NULL);
2063         /* second: free the match object itself */
2064         free(match);
2065 }
2066
2067
2068
2069 int ext_grs_get_n_matches(ext_grs_match_t *match) {
2070         if (! match) {
2071                 printf("module ext/grs: ERROR in function ext_grs_get_n_matches()\n");
2072                 printf("  the match id given was to large\n");
2073                 assert(0);
2074                 return 0;
2075         }
2076
2077         return match->n_matches;
2078 }
2079
2080
2081 ir_graph *ext_grs_get_match_irg(ext_grs_match_t *match) {
2082         if (! match) {
2083                 printf("module ext/grs: ERROR in function ext_grs_get_match_irg()\n");
2084                 printf("  the match id given was to large\n");
2085                 assert(0);
2086                 return NULL;
2087         }
2088
2089         return match->irg;
2090 }
2091
2092
2093 ir_node **ext_grs_get_match_node_map(ext_grs_match_t *match, int which) {
2094
2095         if (which >= match->n_matches) {
2096                 printf("module ext/grs: ERROR in function ext_grs_get_match_node_map()\n");
2097                 printf("  the match id given was to large\n");
2098                 assert(0);
2099                 return NULL;
2100         }
2101
2102         return match->nodes[which];
2103 }
2104
2105 ir_node **ext_grs_get_replace_node_map(ext_grs_match_t *match, int which) {
2106
2107         if (which >= match->n_matches) {
2108                 printf("module ext/grs: ERROR in function ext_grs_get_match_node_map()\n");
2109                 printf("  the match id given was to large\n");
2110                 assert(0);
2111                 return NULL;
2112         }
2113
2114         return match->repl_nodes[which];
2115 }
2116
2117
2118
2119 const ir_edge_t **ext_grs_get_match_edge_map(ext_grs_match_t *match, int which) {
2120
2121         if (which >= match->n_matches) {
2122                 printf("module ext/grs: ERROR in function ext_grs_get_match_node_map()\n");
2123                 printf("  the match id given was to large\n");
2124                 assert(0);
2125                 return NULL;
2126         }
2127
2128         return match->edges[which];
2129 }
2130
2131
2132 int ext_grs_get_match_max_node_aiid(ext_grs_match_t *match)
2133 {
2134         return(match->max_node_id);
2135 }
2136
2137 int ext_grs_get_match_max_edge_aiid(ext_grs_match_t *match)
2138 {
2139         return(match->max_edge_id);
2140 }