nsz Git - libfirm/blob - ir/be/grgen/simd/search_tree.c

   1 /************************************************************************
   2  * Program:             Search_tree.c
   3  * Project:             SIMD optimization
   4  * Function:            Provides functions to build a search tree to
   5  *                              select the patterns for rewrite
   6  * Author:              Andreas Schoesser
   7  * Date:                        2007-07-05
   8  ************************************************************************/
   9
  10 #include <stdio.h>
  11 #include <conio.h>
  12
  13 #include "irgraph.h"
  14 #include "pmap.h"
  15 #include "irtools.h"
  16
  17 #include "grs/match.h"
  18
  19 #include "simd_presets.h"
  20 #include "search_tree_t.h"
  21 #include "firm_node_ext.h"
  22
  23
  24 struct pmap *applied_nodes;
  25 static int st_number = 0;
  26
  27
  28 /************************************************************************
  29  * Builds a search tree
  30  * TODO: Check if a match is valid, only then insert a search tree node,
  31  *       but insert it into the ignore list
  32  ************************************************************************/
  33
  34 search_tree_node_t *build_search_tree(search_tree_env_t *search_tree_env, int prio_start)
  35 //void build_search_tree(search_tree_env_t *search_tree_env)//, int struct pmap *vec_operations, struct pmap *keep_nodes, int start, statistics_t *statistics, struct pmap *replaced_ptrs)
  36 {
  37         plist_t **ignored_matches = alloca(search_tree_env->num_rules * sizeof(plist_t *));
  38         search_tree_node_t *root;
  39         int i;
  40         char st_filename[255];
  41
  42         applied_nodes = pmap_create();
  43         #if VERBOSE_REWRITE
  44                 printf("\n\nBuilding search tree for priority %d:\n\n", search_tree_env->priorities[1]);
  45         #endif
  46
  47         // Create "list of matches to ignore" for each rule type
  48         for(i = 0; i < search_tree_env->num_rules; i++)
  49                 ignored_matches[i] = plist_new();
  50
  51         root = rec_search_patterns(search_tree_env, search_tree_env->priorities[1], ignored_matches);
  52
  53         // Free "list of matches to ignore" for each rule type
  54         for(i = 0; i < search_tree_env->num_rules; i++)
  55         {
  56                 plist_clear(ignored_matches[i]);
  57                 plist_free(ignored_matches[i]);
  58         }
  59
  60         #if VERBOSE_REWRITE
  61                 sprintf(st_filename, "%s-searchtree-%d.vcg", get_entity_name(get_irg_entity(search_tree_env->irg)), st_number++);
  62                 dump_search_tree(root, st_filename, "testtree", search_tree_env);
  63         #endif
  64
  65         #if VERBOSE_REWRITE
  66                 printf("\n");
  67         #endif
  68
  69         pmap_destroy(applied_nodes);
  70
  71         return(root);
  72 }
  73
  74
  75
  76 /************************************************************************
  77  * Frees the memory occupied by the search tree data structure
  78  * Params: root: The root node of the search tree
  79  ************************************************************************/
  80
  81 void destroy_search_tree(search_tree_node_t *root)
  82 {
  83         // Free memory preds
  84         if(root->memory_preds != NULL)
  85                 pmap_destroy(root->memory_preds);
  86
  87         // Free the match and free subsequent search nodes recursively
  88         if(root->match != NULL)
  89         {
  90                 destroy_search_tree(root->with);
  91                 destroy_search_tree(root->without);
  92                 ext_grs_free_match(root->match);
  93         }
  94
  95         // Free the current search tree node itself
  96         free(root);
  97 }
  98
  99
 100
 101 /************************************************************************
 102  * Searches patterns recursively and tests what costs appear when
 103  * the pattern we found would be applied or not.
 104  ************************************************************************/
 105
 106 static search_tree_node_t *rec_search_patterns(search_tree_env_t *st_env, int prio, plist_t **ignored_matches)
 107 {
 108         int i, j, *prio_pos = st_env->priorities;
 109
 110         // Search all patterns in this priority
 111         search_tree_node_t *st_node = malloc(sizeof(*st_node));
 112
 113         memset(st_node, 0, sizeof(*st_node));
 114
 115         for(; prio_pos[1] == prio; ) // TODO! Nach oben begrenzen!
 116         {
 117                 int rule_nr = prio_pos[0];
 118                 ext_grs_match_t *match;
 119
 120                 #if VERBOSE_REWRITE
 121                         printf("\nSearching pattern %s (%d).", st_env->firmnode_names[rule_nr], rule_nr);
 122                 #endif
 123
 124                 // Get ALL matches
 125                 match = ext_grs_match(st_env->irg, st_env->m_plans[rule_nr], ext_grs_ALL, ext_grs_REGARDLESS);
 126                 assert(match != NULL && "Panic! No memory for match!");
 127                 st_env->statistics->num_matches += ext_grs_get_n_matches(match);
 128                 st_env->statistics->num_matched_nodes += ext_grs_get_n_matches(match) * ext_grs_get_match_max_node_aiid(match);
 129
 130                 // Now find the first one not to be ignored;
 131                 for(i = 0; i < ext_grs_get_n_matches(match); i++)
 132                 {
 133                         if(!ignore_match(match, i, ignored_matches, rule_nr))
 134                         {
 135                                 // Insert this match into ignore list
 136                                 plist_element_t *inserted_match = add_ignored_match(match, i, ignored_matches, rule_nr);
 137                                 plist_t *undo_vproj_info;
 138                                 int aa;
 139
 140                                 #if VERBOSE_REWRITE
 141                                         printf(" Found! %p", st_node);
 142                                 #endif
 143
 144                                 // ** First look if we're allowed to apply the match **
 145                                 // Look if the arguments are in dominating blocks
 146
 147                                 if((aa = analyze_arguments(st_env->rules[rule_nr], match, i, st_env->irg, NULL)) < 0)
 148                                 {
 149
 150                                         #if VERBOSE_REWRITE
 151                                                 if(aa == -1)
 152                                                         printf(" Invalid arguments.");
 153                                                 else
 154                                                         printf(" Argument dependency.");
 155                                         #endif
 156                                         return(st_node);
 157                                 }
 158
 159
 160                                 // Find the memory predecessors to be able to schedule the complex operation
 161                                 st_node->memory_preds = find_memory_preds(st_env->irg, ext_grs_get_match_node_map(match, i), st_env->rules[rule_nr]->max_node_aiid);
 162
 163                                 // Do alias analysis and "LOAD usage" analysis" to see if pattern is really appliable.
 164                                 if(test_alias_relation(match->nodes[i], match->max_node_id, st_node->memory_preds, st_env->replaced_ptrs) != 0)
 165                                 {
 166                                         #if VERBOSE_REWRITE
 167                                                 printf(" Rejected: Alias conflict!");
 168                                         #endif
 169                                         return(st_node);
 170                                 }
 171
 172
 173                                 // Arriving here means we're allowed to apply the match. Save information and look for
 174                                 // following matches with or without the current match.
 175                                 st_node->match = match;
 176                                 st_node->which_match = i;
 177                                 st_node->rule_nr = rule_nr;
 178
 179                                 // call recursively
 180                                 st_node->without = rec_search_patterns(st_env, prio, ignored_matches);
 181
 182                                 // Delete this pattern from the ignored ones
 183                                 delete_ignored_match(ignored_matches, inserted_match, rule_nr);
 184
 185
 186                                 // Insert vProj nodes
 187                                 undo_vproj_info = construct_vproj(st_env, st_node, rule_nr);
 188
 189                                 // call again recursively
 190                                 #if VERBOSE_REWRITE
 191                                         printf("\nApplying %p ", st_node);
 192                                 #endif
 193                                 insert_inner_nodes(st_env, st_node);
 194                                 st_node->with = rec_search_patterns(st_env, prio, ignored_matches);
 195                                 remove_inner_nodes(st_env, st_node);
 196                                 #if VERBOSE_REWRITE
 197                                         printf("\nFinished Applying %p\n", st_node);
 198                                 #endif
 199
 200                                 // Destroy VProj nodes
 201                                 deconstruct_vproj(undo_vproj_info);
 202
 203
 204                                 // Build the search tree node for this match
 205
 206                                 st_node->this_matchs_costsavings = st_env->cost_savings[rule_nr] - ext_result_costs(st_node->match, st_node->which_match);
 207                                 st_node->cost_savings = MAX((st_node->without->cost_savings), (st_node->with->cost_savings + st_node->this_matchs_costsavings));
 208
 209
 210                                 return(st_node);
 211                         }
 212                 }
 213                 prio_pos += 2;
 214         }
 215         return(st_node);
 216 }
 217
 218
 219
 220 /*_                                _                   _
 221  (_) __ _ _ __   ___  _ __ ___  __| |  _ __   ___   __| | ___  ___
 222  | |/ _` | '_ \ / _ \| '__/ _ \/ _` | | '_ \ / _ \ / _` |/ _ \/ __|
 223  | | (_| | | | | (_) | | |  __/ (_| | | | | | (_) | (_| |  __/\__ \
 224  |_|\__, |_| |_|\___/|_|  \___|\__,_| |_| |_|\___/ \__,_|\___||___/
 225         |___/                                                                                                           */
 226
 227
 228 /************************************************************************
 229  * Adds a certain match to the list of ignored matches
 230  * Prarms:      match:  The match object to be inserted
 231  *                      which:  The match number inside the match object to be inserted
 232  *                      ignored_matches: Array of list of matches to be ignored
 233  *                      rule_nr:        The rule which found the match
 234  * Returns: List element containing the ignored match
 235  ************************************************************************/
 236
 237 static plist_element_t *add_ignored_match(ext_grs_match_t *match, int which, plist_t **ignored_matches, int rule_nr)
 238 {
 239         ignored_match_t *imatch = malloc(sizeof(*imatch));
 240         //memset(imatch, 0, sizeof(*imatch));
 241
 242         imatch->nodes = generate_nodemap_hash(ext_grs_get_match_node_map(match, which), ext_grs_get_match_max_node_aiid(match));
 243         // imatch->edges = ext_grs_get_match_edge_map(match, which);
 244
 245         plist_insert_back(ignored_matches[rule_nr], imatch);
 246         return(plist_last(ignored_matches[rule_nr]));
 247 }
 248
 249
 250
 251 /************************************************************************
 252  * Removes a certain match to the list of ignored matches
 253  * Params: ignored_matches: List of matches to be ignored
 254  *                 match_to_delete: List element of ignored_matches to be deleted
 255  ************************************************************************/
 256
 257 static void delete_ignored_match(plist_t **ignored_matches, plist_element_t *match_to_delete, int rule_nr)
 258 {
 259         ignored_match_t *imatch = match_to_delete->data;
 260         pmap_destroy(imatch->nodes);
 261         free(imatch);
 262         plist_erase(ignored_matches[rule_nr], match_to_delete);
 263 }
 264
 265
 266
 267 /************************************************************************
 268  * Test, if a certain match is in the ignore list
 269  * Returns: 0 if the match is not in the list
 270  *          1 if the match has to be ignored
 271  * Prarms:      match:  The match object to be tested
 272  *                      which:  The match number inside the match object to be tested
 273  *                      ignored_matches: Array of list of matches to be ignored
 274  *                      rule_nr:        The rule which found the match
 275  ************************************************************************/
 276
 277 static int ignore_match(ext_grs_match_t *match, int which, plist_t **ignored_matches, int rule_nr)
 278 {
 279         int j;
 280         plist_element_t *el;
 281         pmap_entry *pen = NULL;
 282         ir_node **node_map = ext_grs_get_match_node_map(match, which);
 283         ir_edge_t **edge_map = ext_grs_get_match_edge_map(match, which);
 284         int max_aiid = ext_grs_get_match_max_node_aiid(match);
 285
 286         // Iterate over all matches to be ignored of rule type "rule_nr"
 287         foreach_plist(ignored_matches[rule_nr], el)
 288         {
 289                 ignored_match_t *imatch = (ignored_match_t *) el->data;
 290                 int difference = 0;
 291
 292                 for(j = 0; j <= max_aiid; j++)
 293                         // if((pen = pmap_get(imatch->nodes, node_map[j])) == NULL) /// HAEEE? Why does this not work????
 294                         if(!pmap_contains(imatch->nodes, node_map[j]))
 295                         {
 296                                 difference = 1; // We have a difference. Proceed with next saved match
 297                                 break;
 298                         }
 299
 300                 if(difference == 0)
 301                 {
 302                         #if VERBOSE_REWRITE
 303                                 printf(" Ignoring: Already matched in %p", pen);
 304                         #endif
 305                         return(1); // There is no difference beetween the two, that means we found 2 identical matches
 306                 }
 307         }
 308
 309         // Now look if match's nodes don't collide with inner nodes of already applied matches
 310         for(j = 0; j <= max_aiid; j++)
 311                 if((pen = pmap_get(applied_nodes, node_map[j])) != 0)
 312                 {
 313                         #if VERBOSE_REWRITE
 314                                 printf(" Overlapping with %p", pen);
 315                         #endif
 316                         return(1);
 317                 }
 318
 319
 320         return(0);
 321 }
 322
 323
 324 /************************************************************************
 325  * Insert inner nodes of an applied pattern into a global pmap
 326  ************************************************************************/
 327
 328 void insert_inner_nodes(search_tree_env_t *st_env, search_tree_node_t *st_node)
 329 {
 330         ir_node **nodes = ext_grs_get_match_node_map(st_node->match, st_node->which_match);
 331         int max_id = ext_grs_get_match_max_node_aiid(st_node->match, st_node->which_match);
 332         int i;
 333         ext_grs_node_t **act_nodes = st_node->match->action->nodes;
 334         int len = strlen(VECTOR_RESULT_NAME);
 335
 336         for(i = 0; i < max_id; i++)
 337         {
 338                 // Ignore Agrument nodes of the pattern
 339                 if(act_nodes[i]->op == op_IrNode) // Generic argument nodes
 340                         continue;
 341                 if(strncmp(act_nodes[i]->name, "Arg_", 4) == 0) // explicit argument nodes, that is Vector Base
 342                         continue;
 343                 if(get_irn_opcode(nodes[i]) == iro_Const)
 344                         continue;
 345                 if(get_irn_opcode(nodes[i]) == iro_VProj)
 346                         continue;
 347                 if(get_irn_opcode(nodes[i]) == iro_Block)
 348                         continue;
 349                 pmap_insert(applied_nodes, nodes[i], (void *) st_node); // Annotate which node produced that node
 350         }
 351 }
 352
 353
 354
 355 /************************************************************************
 356  *
 357  ************************************************************************/
 358
 359 void remove_inner_nodes(search_tree_env_t *st_env, search_tree_node_t *st_node)
 360 {
 361         ir_node **nodes = ext_grs_get_match_node_map(st_node->match, st_node->which_match);
 362         int max_id = ext_grs_get_match_max_node_aiid(st_node->match, st_node->which_match);
 363         int i;
 364
 365         for(i = 0; i < max_id; i++)
 366                 if(pmap_contains(applied_nodes, nodes[i]))
 367                         pmap_insert(applied_nodes, nodes[i], 0); // Ugly, can't remove from pmap!
 368 }
 369
 370
 371
 372 /* ___                     _    __     ______            _
 373   |_ _|_ __  ___  ___ _ __| |_  \ \   / /  _ \ _ __ ___ (_)
 374    | || '_ \/ __|/ _ \ '__| __|  \ \ / /| |_) | '__/ _ \| |
 375    | || | | \__ \  __/ |  | |_    \ V / |  __/| | | (_) | |
 376   |___|_| |_|___/\___|_|   \__|    \_/  |_|   |_|  \___// |
 377                                                       |__/ */
 378
 379 /************************************************************************
 380  * Insert "artificial" VProj and Complex Instruction nodes
 381  * Annotate at these nodes which match "created" them.
 382  ************************************************************************/
 383
 384 static plist_t *construct_vproj(search_tree_env_t *st_env, search_tree_node_t *st_node, int rule_nr)
 385 {
 386         char node_name[50];
 387         int result_nr = 0, result_aiid;
 388         plist_t *undo_info = plist_new();
 389         ext_grs_match_t *match = st_node->match;
 390         int which =     st_node->which_match;
 391
 392         // Find out if the match has VProj results and how many
 393         // This is done by looking for the node names Result_0_... - Result_n_...
 394         // The right node names have to be created by the pattern creator before!
 395
 396         sprintf(node_name, "%s%d", VECTOR_RESULT_NAME, result_nr);
 397         if((result_aiid = ext_grs_act_get_node_aiid_n(st_env->rules[rule_nr], node_name, strlen(node_name))) >= 0)
 398         {                                                                                                                                               // Yes, it has vector results
 399                 ir_node **nodes = ext_grs_get_match_node_map(match, which);
 400                 ir_node *ins[1], *dataproj, *block, *complex;
 401                 pmap_entry *pen;
 402
 403                 block = get_nodes_block(nodes[result_aiid]);
 404
 405                 // Insert artificial complex instruction
 406                 ins[0] = NULL;
 407                 pmap_foreach(st_node->memory_preds, pen)
 408                 {
 409                         ins[0] = get_irn_n(pen->key, 0); //(pen->key);
 410                         pmap_break(st_node->memory_preds);
 411                 }
 412                 complex = new_ir_node(NULL, st_env->irg, block, op_FakeComplex, mode_T, (ins[0] == NULL) ? 0 : 1, &ins[0]);
 413                 ins[0] = complex;
 414                 dataproj = new_ir_node_with_update(NULL, st_env->irg, block, op_Proj, mode_LLu, 1, ins);
 415                 insert_which_match_vproj(st_env, dataproj, st_node->match, st_node->which_match, -1);
 416                 ins[0] = dataproj;
 417
 418                 // Insert the VProjs, connect them with the complex instruction node
 419                 do
 420                 {
 421                         ir_node *result_node = nodes[result_aiid];
 422                         ir_node *new_vproj;
 423                         ir_edge_t *res_succ, **outs;
 424                         int n_edges, i = 0;
 425                         undo_vproj_t *undo_vproj = malloc(sizeof(*undo_vproj));
 426
 427                         // Create a new VProj node
 428                         new_vproj = new_ir_node_with_update(NULL, st_env->irg, get_nodes_block(result_node), op_VProj, get_irn_mode(result_node), 1, ins);
 429                         set_VProj_proj(new_vproj, result_nr);
 430
 431                         // Save undo info for that VProj node
 432                         undo_vproj -> vproj_node = new_vproj;
 433                         undo_vproj -> org_result = result_node;
 434                         plist_insert_back(undo_info, undo_vproj);
 435
 436                         // Save for each VProj, which match "created" them
 437                         //pmap_insert(st_env->which_match_vproj, new_vproj, st_node);
 438                         insert_which_match_vproj(st_env, new_vproj, st_node->match, st_node->which_match, result_aiid);
 439
 440                         // Now connect the result's successors to the Vproj, remember the old connections
 441                         n_edges = get_irn_n_edges(result_node);
 442                         NEW_ARR_A(ir_edge_t *, outs, n_edges);
 443
 444                         foreach_out_edge(result_node, res_succ)
 445                         {
 446                                 assert(i < n_edges);
 447                                 outs[i++] = res_succ;
 448                         }
 449
 450                         for(i = 0; i < n_edges; i++)
 451                         {
 452                                 // Rewire
 453                                 set_irn_n(outs[i]->src, outs[i]->pos, new_vproj);
 454                         }
 455
 456
 457                         // Search the next node.
 458                         sprintf(node_name, "%s%d", VECTOR_RESULT_NAME, ++result_nr);
 459                 } while((result_aiid = ext_grs_act_get_node_aiid_n(st_env->rules[rule_nr], node_name, strlen(node_name))) >= 0);
 460         }
 461
 462         //dump_ir_block_graph(st_env->irg, "inserted_vproj");
 463
 464         return(undo_info);
 465
 466 }
 467
 468
 469
 470 /************************************************************************
 471  * Connects the successors of the inserted VProjs with their original
 472  * arguments again. Does NOT erase the VProj nodes from the graph,
 473  * they are still needed.
 474  * Frees the undo info
 475  ************************************************************************/
 476
 477 static void deconstruct_vproj(plist_t *undo_vproj_info)
 478 {
 479         plist_element_t *el;
 480
 481         // Undo every VProj inserted
 482         foreach_plist(undo_vproj_info, el)
 483         {
 484                 undo_vproj_t *undo_vproj = el->data;
 485                 ir_edge_t **outs, *vproj_succ;
 486                 int i = 0, n_edges;
 487
 488                 assert(get_irn_opcode(undo_vproj->vproj_node) == iro_VProj);
 489
 490                 // Save all outs
 491                 n_edges = get_irn_n_edges(undo_vproj->vproj_node);
 492                 NEW_ARR_A(ir_edge_t *, outs, n_edges);
 493                 foreach_out_edge(undo_vproj->vproj_node, vproj_succ)
 494                 {
 495                         assert(i < n_edges);
 496                         outs[i++] = vproj_succ;
 497                 }
 498
 499                 // Rewire
 500                 for(i = 0; i < n_edges; i++)
 501                         set_irn_n(outs[i]->src, outs[i]->pos, undo_vproj->org_result);
 502
 503                 // TODO!! Remove VProjs from matchers nodes list!
 504
 505                 // Free undo info
 506                 free(undo_vproj);
 507
 508         }
 509
 510         plist_clear(undo_vproj_info);
 511         plist_free(undo_vproj_info);
 512 }
 513
 514
 515
 516 /************************************************************************
 517  * Creates an entry in the which_match_vproj pmap to indicate
 518  * which match created which vproj node and where to find the
 519  * the REAL vproj node that was created by the replacement
 520  ************************************************************************/
 521
 522 static void insert_which_match_vproj(search_tree_env_t *st_env, ir_node *vproj, ext_grs_match_t *match, int which, int aiid)
 523 {
 524         which_match_vproj_t *wmv = obstack_alloc(st_env->obst, sizeof(*wmv));
 525
 526         wmv->match = match;
 527         wmv->which = which;
 528         wmv->aiid  = aiid;
 529
 530         pmap_insert(st_env->which_match_vproj, vproj, wmv);
 531 }
 532
 533
 534 /*              _                                     _
 535  _ __ ___ _ __ | | __ _  ___ ___ _ __ ___   ___ _ __ | |_
 536 | '__/ _ \ '_ \| |/ _` |/ __/ _ \ '_ ` _ \ / _ \ '_ \| __|
 537 | | |  __/ |_) | | (_| | (_|  __/ | | | | |  __/ | | | |_
 538 |_|  \___| .__/|_|\__,_|\___\___|_| |_| |_|\___|_| |_|\__|
 539          |_|                                                  */
 540
 541 /************************************************************************
 542  * Walk over search tree
 543  * Replace those patterns with the greates saving of costs
 544  * Params: root: root of the search tree
 545  ************************************************************************/
 546
 547 void replace_search_tree(search_tree_node_t *root, replace_st_env_t *rep_env)
 548 {
 549         char force_apply, suggestion;
 550
 551         if(root->match == NULL)
 552                 return;
 553
 554         #if VERBOSE_REWRITE
 555         suggestion = ((root->without->cost_savings) > (root->with->cost_savings + root->this_matchs_costsavings)) ? 'n' : 'y';
 556         printf("\nApply RULE %s? Suggested: %c (y/n): ", rep_env->firmnode_names[root->rule_nr], suggestion);
 557                 #if PROMPT_REWRITE
 558                         force_apply = getch();
 559                 #endif
 560         #endif
 561
 562
 563         #if VERBOSE_REWRITE && PROMPT_REWRITE
 564         if(force_apply == 'n' || force_apply == 'N')  // User driven
 565         #else
 566         if((root->without->cost_savings) >= (root->with->cost_savings + root->this_matchs_costsavings)) // Cost driven
 567         #endif
 568         {
 569                 #if VERBOSE_REWRITE
 570                         printf("n");
 571                 #endif
 572                 // Go on with the "not replaced" edge
 573                 replace_search_tree(root->without, rep_env);
 574         }
 575         else
 576         {
 577                 int which[1];
 578                 char match_postfix[100];
 579
 580                 #if VERBOSE_REWRITE
 581                         printf("y");
 582                 #endif
 583
 584                 // Manipulate the match to use the VProjs of its predecessor
 585                 manipulate_match(rep_env, root->match, root->which_match);
 586
 587                 // Rewrite the Match
 588                 which[0] = root->which_match;
 589                 ext_grs_finish_match(root->match, 1, &which[0]);
 590
 591                 connect_complex_memory(rep_env->rules[root->rule_nr], root->match, root->which_match, root->memory_preds);
 592                 save_complex_operation(rep_env->rules[root->rule_nr], root->match, root->which_match, rep_env->vec_operations, root->rule_nr);
 593                 save_keep_nodes(rep_env->rules[root->rule_nr], root->match, root->which_match, rep_env->keep_nodes);
 594                 set_complex_operation_block(rep_env->irg, root->match, root->which_match);
 595
 596                 //sprintf(match_postfix, "-REWRITTEN-%d-%d", i, j);
 597                 //dump_ir_block_graph(irg, match_postfix);
 598                 rep_env->statistics -> num_instructions_inserted++;
 599                 rep_env->statistics -> num_replaced_nodes += root->match->n_nodes;
 600                 rep_env->statistics -> rewritten_patterns[root->rule_nr]++;
 601
 602                 // Go on with the "replaced" edge
 603                 replace_search_tree(root->with, rep_env);
 604         }
 605 }
 606
 607
 608
 609 /************************************************************************
 610  * Manipulate Match object before replacement to not use the
 611  * temporarily created VProj nodes but the VProj nodes created by
 612  * the previous replacement.
 613  ************************************************************************/
 614
 615 static void manipulate_match(replace_st_env_t *rep_env, ext_grs_match_t *match, int which)
 616 {
 617         /*      TODO:
 618                 * Find out which nodes and edges have to be manipulated
 619                   - Iterate through matches array
 620                   - Look if a  node is inside the which_match_vproj map
 621                   - Retrieve the preceeding match object
 622                   -
 623         */
 624
 625         int max_aiid = ext_grs_get_match_max_node_aiid(match);
 626         ir_node **node_map = ext_grs_get_match_node_map(match, which);
 627         which_match_vproj_t *wmv;
 628         int i;
 629
 630         // Manipulate nodes
 631         for(i = 0; i < max_aiid; i++)
 632         {
 633                 if((wmv = (which_match_vproj_t *) pmap_get(rep_env->which_match_vproj, node_map[i])) != NULL)
 634                 {
 635                         // We found an entry that has to be rewired.
 636                         if(wmv->aiid >= 0)
 637                         {
 638                                 // It's a retyped result node. Follow "kept" array that points to the replace_node_map
 639                                 ir_node **repl_node_map = wmv->match->repl_nodes[wmv->which];
 640                                 node_map[i] = repl_node_map[wmv->match->action->pattern_node_kept[wmv->aiid]];
 641                         }
 642                         else
 643                         {
 644                                 // It's the vector proj, which is not in the "kept" array since it was newly inserted.
 645                                 // Search for it by name in the replace_node_map
 646                                 int aiid = ext_grs_act_get_node_aiid(wmv->match->action, VECTOR_OP_PROJDATA_NAME);
 647                                 ir_node **repl_node_map = wmv->match->repl_nodes[wmv->which];
 648                                 assert(aiid >= 0 && "Vector_Op_ProjData not found!");
 649                                 node_map[i] = repl_node_map[aiid];
 650                         }
 651                 }
 652         }
 653
 654         // Manipulate edges! Maybe not even necessary! As well as Vprojs, we just need the
 655         // Vector_op_ProjData node!
 656 }
 657
 658
 659
 660 /************************************************************************
 661 * Find the block to place the complex operation in
 662 * We have to think here:
 663 * Maybe we should prefer the blocks of the memory nodes. If no memory
 664 * nodes there, the algorithm should be correct.
 665 ************************************************************************/
 666
 667 void set_complex_operation_block(ir_graph *irg, ext_grs_match_t *match, int which)
 668 {
 669         ir_node **nodes = ext_grs_get_replace_node_map(match, which);
 670         int max_id = match->action->max_repl_node_aiid;
 671         int i, aiid;
 672
 673         ir_node *current_block = NULL;
 674
 675         assure_doms(irg);
 676
 677         for(i = 0; i <= max_id; i++)
 678         {
 679                 if(nodes[i] != NULL)
 680                 {
 681                         ir_opcode opc = get_irn_opcode(nodes[i]);
 682                         if(opc != iro_Conv && match->action->replacement_nodes[i]->op != op_IrNode /* Its a generic Vector Base */ && opc != iro_VProj && opc != iro_MultipleAdd && opc != iro_Block && opc != iro_Const && strncmp(match->action->replacement_nodes[i]->name, "Arg_", 4) != 0)
 683                         {
 684                                 if(current_block == NULL)
 685                                         current_block = get_nodes_block(nodes[i]);
 686                                 else
 687                                 {
 688                                         ir_node *this_block = get_nodes_block(nodes[i]);
 689                                         if(this_block && this_block != current_block && block_dominates(this_block, current_block))
 690                                                 current_block = this_block;
 691                                 }
 692                         }
 693                 }
 694         }
 695
 696         // Set the Block for the complex operation and it's projs
 697         assert(current_block != NULL);
 698         set_nodes_block(nodes[ext_grs_act_get_node_aiid(match->action,  VECTOR_OP_PROJDATA_NAME)], current_block);
 699         set_nodes_block(nodes[ext_grs_act_get_node_aiid(match->action,  VECTOR_OP_NAME)], current_block);
 700         if((aiid = ext_grs_act_get_node_aiid(match->action,  VECTOR_OP_PROJM_NAME)) >= 0)
 701                 set_nodes_block(nodes[aiid], current_block);
 702 }
 703
 704
 705
 706
 707 /*                       _       _                       _
 708  ___  ___  __ _ _ __ ___| |__   | |_ _ __ ___  ___    __| |_   _ _ __ ___  _ __   ___ _ __
 709 / __|/ _ \/ _` | '__/ __| '_ \  | __| '__/ _ \/ _ \  / _` | | | | '_ ` _ \| '_ \ / _ \ '__|
 710 \__ \  __/ (_| | | | (__| | | | | |_| | |  __/  __/ | (_| | |_| | | | | | | |_) |  __/ |
 711 |___/\___|\__,_|_|  \___|_| |_|  \__|_|  \___|\___|  \__,_|\__,_|_| |_| |_| .__/ \___|_|
 712                                                                                   |_|                  */
 713
 714 /***********************************************************************
 715  * Dumps search trees in VCG Format
 716  ************************************************************************/
 717
 718 int glob_node_nr = 0;
 719 void dump_search_tree(search_tree_node_t *root, char *file, char *graph_name, search_tree_env_t *st_env)
 720 {
 721         FILE *fp = fopen(file, "wt");
 722         assert(fp && "Could not open file to dump");
 723
 724         // Print vcg header
 725         fprintf(fp,
 726                 "graph: { title: \"ir graph of %s\"\n"
 727                 "display_edge_labels: yes\n"
 728                 "layoutalgorithm: mindepth\n"
 729                 "manhattan_edges: yes\n"
 730                 "port_sharing: no\n"
 731                 //"orientation: %s\n"
 732                 "infoname 1: \"Test\"\n",
 733                 graph_name);//, label, orientation);
 734         fprintf(fp, "\n");        /* a separator */
 735
 736         glob_node_nr = 0;
 737         rec_dump_search_tree(root, fp, 0, st_env, 1);
 738
 739         // Dump Footer
 740         fprintf(fp, "}\n");
 741         fclose(fp);
 742 }
 743
 744
 745
 746 /************************************************************************
 747  * Called for each search tree node recursively and dumps its
 748  * information
 749  * Params: bestcost:    1 If we're on the path with the best costs
 750  ************************************************************************/
 751
 752 int rec_dump_search_tree(search_tree_node_t *node, FILE *fp, int this_node_nr, search_tree_env_t *st_env, int best_cost)
 753 {
 754         int next_node_nr = this_node_nr;
 755         ir_node **nodes;
 756         char args[1000], arg_name[20], tmp[1000];
 757         int i = 0, aiid, replace;
 758         args[0] = 0;
 759
 760         if(node->match != NULL)
 761         {
 762                 nodes = ext_grs_get_match_node_map(node->match, node->which_match);
 763
 764                 do
 765                 {
 766                         sprintf(arg_name, "Arg_%d", i);
 767                         aiid = ext_grs_act_get_node_aiid(node->match->action, arg_name);
 768                         if(aiid >= 0)
 769                         {
 770                                 sprintf(tmp, "Arg_%d: %s %d ", i, get_irn_opname(nodes[aiid]), get_irn_node_nr(nodes[aiid]));
 771                                 strcat(args, tmp);
 772                                 strcat(args, "\n");
 773                         }
 774                         i++;
 775                 } while(aiid >= 0);
 776                 sprintf(tmp, "st_node: %p\n", node);
 777                 strcat(args, tmp);
 778                 sprintf(tmp, "CostSavings: %d\n", node->cost_savings);
 779                 strcat(args, tmp);
 780                 sprintf(tmp, "CostSavings this node %d\n", node->this_matchs_costsavings);
 781                 strcat(args, tmp);
 782
 783                 replace = ((node->without->cost_savings) > (node->with->cost_savings + node->this_matchs_costsavings)) ? 0 : 1;
 784
 785                 fprintf(fp, "node: { title: \"n%d\" label: \"%s\" color:%s info1: \"%s\" }\n", this_node_nr, st_env->rules[node->rule_nr]->name, (replace && best_cost) ? "red" : "white", args);
 786
 787                 if(node->with->match != NULL)
 788                 {
 789                         fprintf(fp, "edge: { sourcename: \"n%d\" targetname: \"n%d\" label: \"1\" color:%s}\n", this_node_nr, this_node_nr+1, (replace==1 && best_cost) ? "red" : "black");
 790                         next_node_nr = rec_dump_search_tree(node->with, fp, this_node_nr + 1, st_env, (replace==1 && best_cost));
 791                 }
 792
 793                 if(node->without->match != NULL)
 794                 {
 795                         fprintf(fp, "edge: { sourcename: \"n%d\" targetname: \"n%d\" label: \"0\" color:%s}\n", this_node_nr, next_node_nr+1, (replace==0 && best_cost) ? "red" : "black");
 796                         next_node_nr = rec_dump_search_tree(node->without, fp, next_node_nr + 1, st_env, (replace==0 && best_cost));
 797                 }
 798         }
 799
 800         return(next_node_nr);
 801 }