nsz Git - libfirm/blob - ir/ir/ircgcons.c

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/ir/ircgcons.c
   4  * Purpose:     Construction and removal of interprocedural representation
   5  *              (explicit interprocedural dependencies).
   6  * Author:      Hubert Schmid
   7  * Modified by:
   8  * Created:     09.06.2002
   9  * CVS-ID:      $Id$
  10  * Copyright:   (c) 2002-2003 Universität Karlsruhe
  11  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  12  */
  13 #ifdef HAVE_CONFIG_H
  14 # include <config.h>
  15 #endif
  16
  17 #include <string.h>
  18 #include <stdbool.h>
  19 #include "ircgcons.h"
  20
  21 #include "array.h"
  22 #include "irprog.h"
  23 #include "irnode_t.h"
  24 #include "irprog_t.h"
  25 #include "ircons_t.h"
  26 #include "irgmod.h"
  27 #include "irgwalk.h"
  28 #include "irflag_t.h"
  29
  30
  31 /* Return the current state of the interprocedural view. */
  32 ip_view_state get_irp_ip_view_state(void) {
  33   return irp->ip_view;
  34 }
  35
  36 /* Set the current state of the interprocedural view. */
  37 static void set_irp_ip_view(ip_view_state state) {
  38   irp->ip_view = state;
  39 }
  40
  41 /* Set the state of the interprocedural view to invalid. */
  42 void set_irp_ip_view_invalid(void) {
  43   set_irp_ip_view(ip_view_invalid);
  44 }
  45
  46
  47 /* Data for each method */
  48 typedef struct {
  49   int count;                      /* Number of calleers. */
  50   bool open;                      /* Open method: called by an unknown caller */
  51   ir_node * reg, * mem, ** res;   /* EndReg, Mem and Method return values */
  52   ir_node * except, * except_mem; /* EndExcept and Mem for exception return */
  53 } irg_data_t;
  54
  55 static irg_data_t * irg_data_create(void) {
  56   irg_data_t * data = xmalloc(sizeof(irg_data_t));
  57   memset(data, 0, sizeof(irg_data_t)); /* init */
  58   return data;
  59 }
  60
  61 /** Count the number of callers of each method and mark open methods.
  62  *
  63  *  Fills the irg_data data structure.
  64  *  Open methods are methods with an unknown caller, I.e., methods that
  65  *   - are external visible
  66  *   - are dereferenced somewhere within the program (i.e., the address of the
  67  *     method is stored somewhere). */
  68 static void caller_init(int arr_length, entity ** free_methods) {
  69   int i, j;
  70   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
  71     set_entity_link(get_irg_entity(get_irp_irg(i)), irg_data_create());
  72   }
  73   for (i = arr_length - 1; i >= 0; --i) {
  74     irg_data_t * data = get_entity_link(free_methods[i]);
  75     data->open = true;
  76   }
  77   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
  78     ir_graph * irg = get_irp_irg(i);
  79     ir_node * call;
  80     /* We collected all call nodes in a link list at the end node. */
  81     for (call = get_irn_link(get_irg_end(irg)); call; call = get_irn_link(call)) {
  82       if (get_irn_op(call) != op_Call) continue;
  83       for (j = get_Call_n_callees(call) - 1; j >= 0; --j) {
  84         entity * ent = get_Call_callee(call, j);
  85         if (get_entity_irg(ent)) {
  86           irg_data_t * data = get_entity_link(ent);
  87 # ifndef CATE_jni
  88           assert(get_entity_irg(ent) && data);
  89           ++data->count;
  90 # endif /* ndef CATE_jni */
  91         } else {
  92           set_entity_link(ent, NULL);
  93         }
  94       }
  95     }
  96   }
  97 }
  98
  99
 100 static INLINE void clear_link(ir_node * node, void * env) {
 101   set_irn_link(node, NULL);
 102 }
 103
 104 /*
 105 static INLINE ir_node * tail(ir_node * node) {
 106   ir_node * link;
 107   for (; (link = get_irn_link(node)); node = link) ;
 108   return node;
 109 }
 110 */
 111
 112 /* Call-Operationen an die "link"-Liste von "call_tail" anhängen (und
 113  * "call_tail" aktualisieren), Proj-Operationen in die Liste ihrer Definition
 114  * (auch bei Proj->Call Operationen) und Phi-Operationen in die Liste ihres
 115  * Grundblocks einfügen. */
 116 static void collect_phicallproj_walker(ir_node * node, ir_node ** call_tail) {
 117   if (get_irn_op(node) == op_Call) {
 118     /* Die Liste von Call an call_tail anhängen. */
 119     ir_node * link;
 120     assert(get_irn_link(*call_tail) == NULL);
 121     set_irn_link(*call_tail, node);
 122     /* call_tail aktualisieren: */
 123     for (link = get_irn_link(*call_tail); link; *call_tail = link, link = get_irn_link(link)) ;
 124   } else if (get_irn_op(node) == op_Proj) {
 125     ir_node * head = skip_Proj(get_Proj_pred(node));
 126     set_irn_link(node, get_irn_link(head));
 127     set_irn_link(head, node);
 128     /* call_tail gegebenenfalls aktualisieren: */
 129     if (head == *call_tail) {
 130       *call_tail = node;
 131     }
 132   } else if (get_irn_op(node) == op_Phi) {
 133     ir_node * block = get_nodes_block(node);
 134     set_irn_link(node, get_irn_link(block));
 135     set_irn_link(block, node);
 136   }
 137 }
 138
 139
 140 static void link(ir_node * head, ir_node * node) {
 141   if (node) {
 142     set_irn_link(node, get_irn_link(head));
 143     set_irn_link(head, node);
 144   }
 145 }
 146
 147
 148 /* Die Call-Operationen aller Graphen an den End-Operationen
 149  * verlinken, die Proj-Operationen an ihren Definitionen und die
 150  * Phi-Operationen an ihren Grundblöcken. Die Liste der Calls sieht
 151  * dann so aus: End -> Call -> Proj -> ... -> Proj -> Call -> Proj ->
 152  * ... -> Proj -> NULL. */
 153 static void collect_phicallproj(void) {
 154   int i;
 155   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 156     ir_graph * irg = get_irp_irg(i);
 157     ir_node * start = get_irg_start(irg);
 158     ir_node * end = get_irg_end(irg);
 159     current_ir_graph = irg;
 160     assert(irg && start);
 161     /* Die speziellen Parameter der Start-Operation extra verlinken,
 162      * auch wenn sie nicht im intraprozeduralen Graphen erreichbar
 163      * sind. */
 164     link(start, get_irg_frame(irg));
 165     link(start, get_irg_globals(irg));
 166     /* walk */
 167     irg_walk_graph(irg, clear_link, (irg_walk_func *) collect_phicallproj_walker, &end);
 168   }
 169 }
 170
 171
 172 /* Proj-Operation durch Filter-Operation im aktuellen Block ersetzen. */
 173 static ir_node * exchange_proj(ir_node * proj) {
 174   ir_node * filter;
 175   assert(get_irn_op(proj) == op_Proj);
 176   filter = new_Filter(get_Proj_pred(proj), get_irn_mode(proj), get_Proj_proj(proj));
 177   /* Die Proj- (Id-) Operation sollte im gleichen Grundblock stehen, wie die
 178    * Filter-Operation. */
 179   set_nodes_block(proj, get_nodes_block(filter));
 180   exchange(proj, filter);
 181   return filter;
 182 }
 183
 184
 185 /* Echt neue Block-Operation erzeugen. CSE abschalten! */
 186 static ir_node * create_Block(int n, ir_node ** in) {
 187   /* Turn off optimizations so that blocks are not merged again. */
 188   int rem_opt = get_opt_optimize();
 189   ir_node * block;
 190   set_optimize(0);
 191   block = new_Block(n, in);
 192   set_optimize(rem_opt);
 193   return block;
 194 }
 195
 196
 197 static void prepare_irg_end(ir_graph * irg, irg_data_t * data);
 198 static void prepare_irg_end_except(ir_graph * irg, irg_data_t * data);
 199
 200
 201 /* If we use new_Unknown we get the Unknown of a graph.  This can
 202  * cause cycles we don't want to see, as Unknwon is in the Start Block
 203  * of the procedure. Use unknown of outermost irg where the start
 204  * block has no predecessors. */
 205 static INLINE ir_node *get_cg_Unknown(ir_mode *m) {
 206   assert((get_Block_n_cfgpreds(get_irg_start_block(get_irp_main_irg())) == 1) &&
 207          (get_nodes_block(get_Block_cfgpred(get_irg_start_block(get_irp_main_irg()), 0)) ==
 208           get_irg_start_block(get_irp_main_irg())));
 209   return new_r_Unknown(get_irp_main_irg(), m);
 210 }
 211
 212
 213 /* IRG vorbereiten. Proj-Operationen der Start-Operation in Filter-Operationen
 214  * umwandeln. Die künstlichen Steuerzusammenflüsse EndReg und EndExcept
 215  * einfügen. An der Start-Operation hängt nach dem Aufruf eine Liste der
 216  * entsprechenden Filter-Knoten. */
 217 static void prepare_irg(ir_graph * irg, irg_data_t * data) {
 218   ir_node * start_block = get_irg_start_block(irg);
 219   ir_node * link, * proj;
 220   int n_callers = data->count + (data->open ? 1 : 0);
 221   ir_node ** in = NEW_ARR_F(ir_node *, n_callers);
 222
 223   current_ir_graph = irg;
 224   set_irg_current_block(irg, start_block);
 225
 226   /* Grundblock interprozedural machen. */
 227   /* "in" ist nicht initialisiert. Das passiert erst in "construct_start". */
 228   set_Block_cg_cfgpred_arr(start_block, n_callers, in);
 229   /* Proj-Operationen durch Filter-Operationen ersetzen und (sonst) in
 230    * den Start-Block verschieben. */
 231   for (proj = get_irn_link(get_irg_start(irg)); proj; proj = get_irn_link(proj)) {
 232     if (get_Proj_pred(proj) != get_irg_start(irg)
 233     || (get_Proj_proj(proj) != pn_Start_X_initial_exec && get_Proj_proj(proj) != pn_Start_T_args)) {
 234       ir_node * filter = exchange_proj(proj);
 235       set_Filter_cg_pred_arr(filter, n_callers, in);
 236     } else {
 237       set_nodes_block(proj, start_block);
 238     }
 239   }
 240
 241   DEL_ARR_F(in);
 242
 243   /* Liste der Filter-Operationen herstellen. Dabei muss man beachten,
 244    * dass oben für "verschiedene" Proj-Operationen wegen CSE nur eine
 245    * Filter-Operation erzeugt worden sein kann. */
 246   for (link = get_irg_start(irg), proj = get_irn_link(link); proj; proj = get_irn_link(proj)) {
 247     if (get_irn_op(proj) == op_Id) { /* replaced with filter */
 248       ir_node * filter = get_Id_pred(proj);
 249       assert(get_irn_op(filter) == op_Filter);
 250       if (filter != link && get_irn_link(filter) == NULL) {
 251     set_irn_link(link, filter);
 252     link = filter;
 253       }
 254     }
 255   }
 256   /* Globle Einträge für ersetzte Operationen korrigieren. */
 257   set_irg_frame      (irg, skip_Id(get_irg_frame(irg)));
 258   set_irg_globals    (irg, skip_Id(get_irg_globals(irg)));
 259   set_irg_initial_mem(irg, skip_Id(get_irg_initial_mem(irg)));
 260
 261   /* Unbekannten Aufrufer sofort eintragen. */
 262   if (data->open) {
 263     set_Block_cg_cfgpred(start_block, 0, get_cg_Unknown(mode_X));
 264     for (proj = get_irn_link(get_irg_start(irg)); proj; proj = get_irn_link(proj)) {
 265       if (get_irn_op(proj) == op_Filter) {
 266     set_Filter_cg_pred(proj, 0, get_cg_Unknown(get_irn_mode(proj)));
 267       }
 268     }
 269     data->count = 1;
 270   } else {
 271     data->count = 0;
 272   }
 273
 274   prepare_irg_end(irg, data);
 275   prepare_irg_end_except(irg, data);
 276 }
 277
 278
 279 /* Künstlicher Steuerzusammenfluss EndReg einfügen. */
 280 static void prepare_irg_end(ir_graph * irg, irg_data_t * data) {
 281   ir_node * end_block   = get_irg_end_block(irg);
 282   ir_node * end         = get_irg_end(irg);
 283   ir_node **ret_arr     = NULL;
 284   ir_node **cfgpred_arr = get_Block_cfgpred_arr(end_block);
 285   int i, j;
 286   int n_ret = 0;
 287
 288   for (i = get_Block_n_cfgpreds(end_block) - 1; i >= 0; --i) {
 289     if (get_irn_op(cfgpred_arr[i]) == op_Return) {
 290       if (ret_arr) {
 291         ARR_APP1(ir_node *, ret_arr, cfgpred_arr[i]);
 292       } else {
 293         ret_arr = NEW_ARR_F(ir_node *, 1);
 294         ret_arr[0] = cfgpred_arr[i];
 295       }
 296       ++n_ret;
 297     }
 298   }
 299
 300   if (n_ret > 0) {
 301     int n_res = get_method_n_ress(get_entity_type(get_irg_entity(irg)));
 302     ir_node ** in = NEW_ARR_F(ir_node *, n_ret);
 303
 304     /* block */
 305     for (i = n_ret - 1; i >= 0; --i) {
 306       set_irg_current_block(irg, get_nodes_block(ret_arr[i]));
 307       in[i] = new_Jmp();
 308     }
 309     create_Block(n_ret, in);
 310
 311     /* end */
 312     data->reg = new_EndReg();
 313
 314     /* mem */
 315     for (i = n_ret - 1; i >= 0; --i) {
 316       in[i] = get_Return_mem(ret_arr[i]);
 317     }
 318     data->mem = new_Phi(n_ret, in, mode_M);
 319     /* This Phi is a merge, therefore needs not be kept alive.
 320        It might be optimized away, though.  */
 321     if (get_End_keepalive(end, get_End_n_keepalives(end)-1 ) == data->mem)
 322       set_End_keepalive(end, get_End_n_keepalives(end)-1, new_Bad());
 323
 324     /* res */
 325     data->res = NEW_ARR_F(ir_node *, n_res);
 326     for (j = n_res - 1; j >= 0; --j) {
 327       ir_mode *mode = NULL;
 328       /* In[0] could be a Bad node with wrong mode. */
 329       for (i = n_ret - 1; i >= 0; --i) {
 330         in[i] = get_Return_res(ret_arr[i], j);
 331         if (!mode && get_irn_mode(in[i]) != mode_T)
 332           mode = get_irn_mode(in[i]);
 333       }
 334       if (mode)
 335         data->res[j] = new_Phi(n_ret, in, mode);
 336       else  /* All preds are Bad */
 337         data->res[j] = new_Bad();
 338     }
 339
 340     DEL_ARR_F(in);
 341   }
 342
 343   if (ret_arr) DEL_ARR_F(ret_arr);
 344 }
 345
 346
 347 /* Künstlicher Steuerzusammenfluss EndExcept einfügen. */
 348 static void prepare_irg_end_except(ir_graph * irg, irg_data_t * data) {
 349   ir_node * end_block = get_irg_end_block(irg);
 350   ir_node * end = get_irg_end(irg);
 351   ir_node ** except_arr = NULL;
 352   int i;
 353   int n_except = 0;
 354   ir_node ** cfgpred_arr = get_Block_cfgpred_arr(end_block);
 355   for (i = get_Block_n_cfgpreds(end_block) - 1; i >= 0; --i) {
 356     if (get_irn_op(cfgpred_arr[i]) != op_Return) {
 357       if (except_arr) {
 358     ARR_APP1(ir_node *, except_arr, cfgpred_arr[i]);
 359       } else {
 360     except_arr = NEW_ARR_F(ir_node *, 1);
 361     except_arr[0] = cfgpred_arr[i];
 362       }
 363       ++n_except;
 364     }
 365   }
 366   if (n_except > 0) {
 367     ir_node ** in = NEW_ARR_F(ir_node *, n_except);
 368     /* block */
 369     create_Block(n_except, except_arr);
 370     /* end_except */
 371     data->except = new_EndExcept();
 372     /* mem */
 373     for (i = n_except - 1; i >= 0; --i) {
 374       ir_node * node = skip_Proj(skip_Tuple(except_arr[i]));
 375       if (get_irn_op(node) == op_Call) {
 376     in[i] = new_r_Proj(irg, get_nodes_block(node), node, mode_M, 3);
 377       } else if (get_irn_op(node) == op_Raise) {
 378     in[i] = new_r_Proj(irg, get_nodes_block(node), node, mode_M, 1);
 379       } else {
 380     assert(is_fragile_op(node));
 381     /* We rely that all cfops have the memory output at the same position. */
 382     in[i] = new_r_Proj(irg, get_nodes_block(node), node, mode_M, 0);
 383       }
 384     }
 385     data->except_mem = new_Phi(n_except, in, mode_M);
 386     /* This Phi is a merge, therefor needs not be kept alive.
 387        It might be optimized away, though.  */
 388     if (get_End_keepalive(end, get_End_n_keepalives(end)-1 )
 389     == data->except_mem)
 390       set_End_keepalive(end, get_End_n_keepalives(end)-1, new_Bad());
 391     DEL_ARR_F(in);
 392   }
 393   if (except_arr) DEL_ARR_F(except_arr);
 394 }
 395
 396
 397 /* Zwischengespeicherte Daten wieder freigeben. */
 398 static void cleanup_irg(ir_graph * irg) {
 399   entity * ent = get_irg_entity(irg);
 400   irg_data_t * data = get_entity_link(ent);
 401   assert(data);
 402   if (data->res) DEL_ARR_F(data->res);
 403   set_entity_link(ent, NULL);
 404   free(data);
 405 }
 406
 407
 408 /* Alle Phi-Operationen aus "from_block" nach "to_block"
 409  * verschieben. Die Phi-Operationen müssen am zugehörigen Grundblock
 410  * verlinkt sein. Danach sind sie am neuen Grundblock verlinkt. */
 411 static void move_phis(ir_node * from_block, ir_node * to_block) {
 412   ir_node * phi;
 413   for (phi = get_irn_link(from_block); phi != NULL; phi = get_irn_link(phi)) {
 414     set_nodes_block(phi, to_block);
 415   }
 416   assert(get_irn_link(to_block) == NULL);
 417   set_irn_link(to_block, get_irn_link(from_block));
 418   set_irn_link(from_block, NULL);
 419 }
 420
 421
 422 /* Rekursiv die Operation "node" und alle ihre Vorgänger aus dem Block
 423  * "from_block" nach "to_block" verschieben.
 424  * Verschiebe ebenfalls die Projs aus diesen Operationen. */
 425 static void move_nodes(ir_node * from_block, ir_node * to_block, ir_node * node) {
 426   int i,  arity = get_irn_arity(node);
 427   ir_node *proj;
 428
 429   for (i = arity - 1; i >= 0; --i) {
 430     ir_node * pred = get_irn_n(node, i);
 431     if (get_nodes_block(pred) == from_block) {
 432       move_nodes(from_block, to_block, pred);
 433     }
 434   }
 435   set_nodes_block(node, to_block);
 436
 437   /* Move projs of this node. */
 438   proj = get_irn_link(node);
 439   for (; proj; proj = skip_Id(get_irn_link(proj))) {
 440     if (get_irn_op(proj) != op_Proj && get_irn_op(proj) != op_Filter) continue;
 441     if ((get_nodes_block(proj) == from_block) && (skip_Proj(get_irn_n(proj, 0)) == node))
 442       set_nodes_block(proj, to_block);
 443   }
 444 }
 445
 446
 447 /* Abhängigkeiten vom Start-Block und den Filter-Operationen im
 448  * Start-Block auf den Aufrufer hinzufügen. */
 449 static void construct_start(entity * caller, entity * callee,
 450                             ir_node * call, ir_node * exec) {
 451   irg_data_t *data  = get_entity_link(callee);
 452   ir_graph   *irg   = get_entity_irg(callee);
 453   ir_node    *start = get_irg_start(irg);
 454   ir_node    *filter;
 455
 456   assert(irg);
 457   assert(get_entity_peculiarity(callee) == peculiarity_existent); /* Else data is not initalized. */
 458   assert((0 <= data->count) &&
 459          (data->count < get_Block_cg_n_cfgpreds(get_nodes_block(start))));
 460
 461   set_Block_cg_cfgpred(get_nodes_block(start), data->count, exec);
 462   for (filter = get_irn_link(start); filter; filter = get_irn_link(filter)) {
 463     if (get_irn_op(filter) != op_Filter) continue;
 464     if (get_Proj_pred(filter) == start) {
 465       switch ((int) get_Proj_proj(filter)) {
 466       case pn_Start_M:
 467     set_Filter_cg_pred(filter, data->count, get_Call_mem(call));
 468     break;
 469       case  pn_Start_P_frame_base:
 470     /* "frame_base" wird nur durch Unknown dargestellt. Man kann ihn aber
 471      * auch explizit darstellen, wenn sich daraus Vorteile für die
 472      * Datenflussanalyse ergeben. */
 473     set_Filter_cg_pred(filter, data->count, get_cg_Unknown(get_irn_mode(filter)));
 474     break;
 475       case pn_Start_P_globals:
 476     /* "globals" wird nur durch Unknown dargestellt. Man kann ihn aber auch
 477      * explizit darstellen, wenn sich daraus Vorteile für die
 478      * Datenflussanalyse ergeben. */
 479     set_Filter_cg_pred(filter, data->count, get_cg_Unknown(get_irn_mode(filter)));
 480     break;
 481       default:
 482     /* not reached */
 483     assert(0 && "not reached");
 484     break;
 485       }
 486     } else {
 487       set_Filter_cg_pred(filter, data->count, get_Call_param(call, get_Proj_proj(filter)));
 488     }
 489   }
 490   ++data->count;
 491 }
 492
 493
 494 /* Abhängigkeiten für den Speicherzustand über alle aufgerufenen
 495  * Methoden bestimmen. */
 496 static void fill_mem(int length, irg_data_t * data[], ir_node * in[]) {
 497   int i;
 498   for (i = 0; i < length; ++i) {
 499     if (data[i]) { /* explicit */
 500       if (data[i]->reg) {
 501         in[i] = data[i]->mem;
 502       } else {
 503         in[i] = new_Bad();
 504       }
 505     } else { /* unknown */
 506       in[i] = get_cg_Unknown(mode_M);
 507     }
 508   }
 509 }
 510
 511
 512 /* Abhängigkeiten für den Ausnahme-Speicherzustand über alle
 513  * aufgerufenen Methoden bestimmen. */
 514 static void fill_except_mem(int length, irg_data_t * data[], ir_node * in[]) {
 515   int i;
 516   for (i = 0; i < length; ++i) {
 517     if (data[i]) { /* explicit */
 518       if (data[i]->except) {
 519         in[i] = data[i]->except_mem;
 520       } else {
 521         in[i] = new_Bad();
 522       }
 523     } else { /* unknown */
 524       in[i] = get_cg_Unknown(mode_M);
 525     }
 526   }
 527 }
 528
 529
 530 /* Abhängigkeiten für ein Ergebnis über alle aufgerufenen Methoden
 531  * bestimmen. */
 532 static void fill_result(int pos, int length, irg_data_t * data[], ir_node * in[], ir_mode *m) {
 533   int i;
 534   for (i = 0; i < length; ++i) {
 535     if (data[i]) { /* explicit */
 536       if (data[i]->reg) {
 537         in[i] = data[i]->res[pos];
 538       } else {
 539         in[i] = new_Bad();
 540       }
 541     } else { /* unknown */
 542       in[i] = get_cg_Unknown(m);
 543     }
 544   }
 545 }
 546
 547
 548 /* Proj auf Except-X einer Call-Operation (aus der Link-Liste) bestimmen. */
 549 static ir_node * get_except(ir_node * call) {
 550   /* Mit CSE könnte man das effizienter machen! Die Methode wird aber für jede
 551    * Aufrufstelle nur ein einziges Mal aufgerufen. */
 552   ir_node * proj;
 553   for (proj = get_irn_link(call); proj && get_irn_op(proj) == op_Proj; proj = get_irn_link(proj)) {
 554     if (get_Proj_proj(proj) == 1 && get_irn_op(get_Proj_pred(proj)) == op_Call) {
 555       return proj;
 556     }
 557   }
 558   return NULL;
 559 }
 560
 561 /* Returns true if control flow operation exc is predecessor of end
 562    block in irg.  Works also for Return nodes, not only exceptions. */
 563 static bool exc_branches_to_end(ir_graph *irg, ir_node *exc) {
 564   int i;
 565   ir_node *end = get_irg_end_block(irg);
 566   for (i = get_Block_n_cfgpreds(end) -1; i >= 0; --i)
 567     if (get_Block_cfgpred(end, i) == exc) return true;
 568   return false;
 569 }
 570
 571 /* Returns true if only caller of irg is "Unknown". */
 572 static bool is_outermost_graph(ir_graph *irg) {
 573   irg_data_t * data = get_entity_link(get_irg_entity(irg));
 574   if (data->count) {
 575     return false;
 576   } else if (data->open) {
 577     /* Die Methode wird nur von "der" unbekannten Aufrufstelle
 578      * aufgerufen. Darstellung wird für diese Methode nicht
 579      * geändert. */
 580   } else {
 581     /* Methode kann nicht aufgerufen werden. Die Darstellung wird
 582      * für diese Methode nicht geändert. Das kann nicht vorkommen,
 583      * wenn zuvor "gc_irgs()" aufgerufen wurde. */
 584   }
 585   return true;
 586 }
 587
 588 /* Grundblock der Call-Operation aufteilen. CallBegin- und Filter-Operationen
 589  * einfügen. Die Steuer- und Datenflussabhängigkeiten von den aufgerufenen
 590  * Methoden auf die CallBegin-Operation, und von der Aufrufstelle auf die
 591  * aufgerufenen Methoden eintragen. */
 592 static void construct_call(ir_node * call) {
 593   int n_callees = get_Call_n_callees(call);
 594   ir_node * post_block = get_nodes_block(call); /* block nach dem Aufruf */
 595   ir_node * pre_block = create_Block(get_Block_n_cfgpreds(post_block),
 596                                      get_Block_cfgpred_arr(post_block)); /* block vor dem Aufruf (mit CallBegin) */
 597   ir_node * except_block = NULL, * proj;
 598   ir_node * jmp = new_Break(); /* Sprung für intraprozedurale Darstellung (in
 599                                 * pre_block) */
 600   ir_node * call_begin = new_CallBegin(call); /* (in pre_block) */
 601   /* CallBegin might be entry to endless recursion. */
 602   add_End_keepalive(get_irg_end(get_irn_irg(pre_block)), pre_block);
 603   ir_node ** in = NEW_ARR_F(ir_node *, n_callees);
 604   entity * caller = get_irg_entity(current_ir_graph); /* entity des aktuellen ir_graph */
 605   entity ** callees = NEW_ARR_F(entity *, n_callees); /* aufgerufene Methoden: entity */
 606   ir_graph ** irgs = NEW_ARR_F(ir_graph *, n_callees); /* aufgerufene Methoden: ir_graph */
 607   irg_data_t ** data = NEW_ARR_F(irg_data_t *, n_callees); /* aufgerufene Methoden: irg_data_t */
 608   int i;
 609
 610   /* post_block kann bereits interprozedurale Steuerflussvorgänger
 611    * besitzen. Diese müssen dann auch noch für den pre_block gesetzt werden. */
 612   if (get_Block_cg_cfgpred_arr(post_block)) {
 613     set_Block_cg_cfgpred_arr(pre_block, get_Block_cg_n_cfgpreds(post_block),
 614                  get_Block_cg_cfgpred_arr(post_block));
 615     remove_Block_cg_cfgpred_arr(post_block);
 616   }
 617
 618   /* Operationen verschieben */
 619   move_phis(post_block, pre_block);
 620   move_nodes(post_block, pre_block, call);
 621   set_irn_in(post_block, 1, &jmp);
 622
 623   /* Wiederverwendete Daten initialisieren. */
 624   for (i = 0; i < n_callees; ++i) {
 625     callees[i] = get_Call_callee(call, i);
 626     irgs[i] = get_entity_irg(callees[i]);
 627     data[i] = get_entity_link(callees[i]);
 628     /* Only entities that have an irg got a irg_data data structure.
 629        In others there is some arbitrary garbage in the link field. */
 630     if (!irgs[i]) { assert(!data[i]); data[i] = NULL; }
 631   }
 632
 633   /*
 634    * Set flag to suppress verifying placement on proper irg:
 635    * optimization can return block on other irg.
 636    */
 637   set_interprocedural_view(1);
 638
 639   /* Die interprozeduralen Steuerflussvorgänger des post_block
 640    * bestimmen. */
 641   for (i = 0; i < n_callees; ++i) {
 642     if (data[i]) { /* explicit */
 643       if (data[i]->reg) {
 644         in[i] = new_r_Proj(irgs[i], get_nodes_block(data[i]->reg),
 645                            data[i]->reg, mode_X, data[i]->count);
 646       } else {
 647         in[i] = new_Bad();
 648       }
 649     } else { /* unknown */
 650       in[i] = get_cg_Unknown(mode_X);
 651     }
 652   }
 653   set_interprocedural_view(0);
 654
 655   set_Block_cg_cfgpred_arr(post_block, n_callees, in);
 656
 657   /* Die interprozeduralen Steuerflussvorgänger des except_block
 658    * bestimmen. */
 659   if ((proj = get_except(call)) != NULL) {
 660     int preds = 0;
 661     bool exc_to_end = false;
 662     if (exc_branches_to_end(current_ir_graph, proj)) {
 663       /* The Call aborts the procedure if it returns with an exception.
 664          If this is an outermost procedure, the normal handling of exceptions
 665          will generate a Break that goes to the end block.  This is illegal
 666          Frim. So directly branch to the end block with all exceptions. */
 667       exc_to_end = true;
 668       if (is_outermost_graph(current_ir_graph)) {
 669         except_block = get_irg_end_block(current_ir_graph);
 670       } else {
 671         irg_data_t * tmp_data = get_entity_link(get_irg_entity(current_ir_graph));
 672         except_block = get_nodes_block(tmp_data->except);
 673       }
 674     } else {
 675       except_block = create_Block(1, &proj);
 676       set_nodes_block(proj, except_block);
 677       exchange(proj, new_Break());
 678       set_irg_current_block(current_ir_graph, pre_block);
 679       set_irn_n(except_block, 0, new_Proj(call, mode_X, 1));
 680       set_irg_current_block(current_ir_graph, post_block);
 681     }
 682
 683     /*
 684      * Set flag to suppress verifying placement on proper irg:
 685      * optimization can return block on other irg.
 686      */
 687     set_interprocedural_view(1);
 688
 689     for (i = 0; i < n_callees; ++i) {
 690       entity * callee = get_Call_callee(call, i);
 691       if (data[i]) { /* explicit */
 692         if (data[i]->except) {
 693           in[i] = new_r_Proj(get_entity_irg(callee), get_nodes_block(data[i]->except),
 694                              data[i]->except, mode_X, data[i]->count);
 695         } else {
 696           in[i] = new_Bad();
 697         }
 698       } else { /* unknown */
 699         in[i] = get_cg_Unknown(mode_X);
 700       }
 701     }
 702
 703     preds = n_callees;
 704     if (exc_to_end) {
 705       /* append all existing preds of the end block to new in array.
 706        * Normal access routine guarantees that with first visit we
 707        * get the normal preds, and from then on the _cg_ preds.
 708        * (interporcedural view is set!)
 709        * Do not add the exc pred of end we are replacing! */
 710       for (i = get_Block_n_cfgpreds(except_block)-1; i >= 0; --i) {
 711         ir_node *pred = get_Block_cfgpred(except_block, i);
 712         if (pred != proj) {
 713           ARR_APP1(ir_node *, in, pred);
 714           preds++;
 715         }
 716       }
 717     }
 718     set_Block_cg_cfgpred_arr(except_block, preds, in);
 719   }
 720   set_interprocedural_view(0);
 721
 722   /* Diesen Vorgänger in den Start-Blöcken der aufgerufenen Methoden
 723    * eintragen. */
 724   set_irg_current_block(current_ir_graph, pre_block);
 725   for (i = 0; i < n_callees; ++i) {
 726     if (irgs[i]) /* Else there is not graph to call */
 727       construct_start(caller, callees[i], call, new_Proj(call_begin, mode_X, i));
 728   }
 729
 730   /* Proj-Operationen in Filter-Operationen umwandeln und
 731    * interprozedurale Vorgänger einfügen. */
 732   set_irg_current_block(current_ir_graph, post_block);
 733   for (proj = get_irn_link(call); proj; proj = get_irn_link(proj)) {
 734     if (get_irn_op(proj) != op_Proj) continue;
 735     if (skip_Proj(get_Proj_pred(proj)) != call) continue;
 736     if (get_Proj_pred(proj) == call) {
 737       if (get_Proj_proj(proj) == pn_Call_M_regular) { /* memory */
 738         ir_node * filter;
 739
 740         set_nodes_block(proj, post_block);
 741         filter = exchange_proj(proj);
 742         /* filter in die Liste der Phis aufnehmen */
 743         if (get_irn_link(filter) == NULL) { /* note CSE */
 744           set_irn_link(filter, get_irn_link(post_block));
 745           set_irn_link(post_block, filter);
 746         }
 747         fill_mem(n_callees, data, in);
 748         set_Filter_cg_pred_arr(filter, n_callees, in);
 749       } else if (get_Proj_proj(proj) == pn_Call_X_except) { /* except */
 750         /* nothing: siehe oben */
 751       } else if (get_Proj_proj(proj) == pn_Call_T_result) { /* results */
 752         /* nothing */
 753       } else if (get_Proj_proj(proj) == pn_Call_M_except) { /* except_mem */
 754         ir_node * filter;
 755
 756         set_nodes_block(proj, post_block);
 757         assert(except_block);
 758         set_irg_current_block(current_ir_graph, except_block);
 759         filter = exchange_proj(proj);
 760         /* filter in die Liste der Phis aufnehmen */
 761         if (get_irn_link(filter) == NULL) { /* note CSE */
 762           set_irn_link(filter, get_irn_link(except_block));
 763           set_irn_link(except_block, filter);
 764         }
 765         set_irg_current_block(current_ir_graph, post_block);
 766         fill_except_mem(n_callees, data, in);
 767         set_Filter_cg_pred_arr(filter, n_callees, in);
 768       } else {
 769         assert(0 && "not reached");
 770       }
 771     } else { /* result */
 772       ir_node * filter;
 773
 774       assert(is_Proj(get_Proj_pred(proj)) && get_Proj_pred(get_Proj_pred(proj)) == call);
 775       set_nodes_block(proj, post_block);
 776       filter = exchange_proj(proj);
 777       /* filter in die Liste der Phis aufnehmen */
 778       if (get_irn_link(filter) == NULL) { /* not CSE */
 779         set_irn_link(filter, get_irn_link(post_block));
 780         set_irn_link(post_block, filter);
 781       }
 782       fill_result(get_Proj_proj(filter), n_callees, data, in, get_irn_mode(filter));
 783       set_Filter_cg_pred_arr(filter, n_callees, in);
 784     }
 785   }
 786   DEL_ARR_F(in);
 787   DEL_ARR_F(callees);
 788   DEL_ARR_F(irgs);
 789   DEL_ARR_F(data);
 790 }
 791
 792
 793 void cg_construct(int arr_len, entity ** free_methods_arr) {
 794   int i;
 795
 796   if (get_irp_ip_view_state() == ip_view_valid) return;
 797   if (get_irp_ip_view_state() == ip_view_invalid) cg_destruct();
 798   set_irp_ip_view(ip_view_valid);
 799
 800   collect_phicallproj();
 801
 802   /* count callers */
 803   caller_init(arr_len, free_methods_arr);
 804
 805   /* prepare irgs */
 806   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 807     ir_graph * irg = get_irp_irg(i);
 808     entity * ent = get_irg_entity(irg);
 809     irg_data_t * data = get_entity_link(ent);
 810     if (data->count) {
 811       prepare_irg(irg, data);
 812     } else if (data->open) {
 813       /* Die Methode wird nur von "der" unbekannten Aufrufstelle
 814        * aufgerufen. Darstellung wird für diese Methode nicht
 815        * geändert. */
 816     } else {
 817       /* Methode kann nicht aufgerufen werden. Die Darstellung wird
 818        * für diese Methode nicht geändert. Das kann nicht vorkommen,
 819        * wenn zuvor "gc_irgs()" aufgerufen wurde. */
 820     }
 821   }
 822
 823   /* construct calls */
 824   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 825     ir_node * node;
 826
 827     current_ir_graph = get_irp_irg(i);
 828     for (node = get_irn_link(get_irg_end(current_ir_graph)); node; node = get_irn_link(node)) {
 829       if (get_irn_op(node) == op_Call) {
 830         int j, n_callees = get_Call_n_callees(node);
 831         for (j = 0; j < n_callees; ++j)
 832           if (get_entity_irg(get_Call_callee(node, j)))
 833             break;
 834         if (j < n_callees)  /* There is an entity with a graph */
 835           construct_call(node);
 836       }
 837     }
 838   }
 839
 840   /* cleanup irgs: Abschlussarbeiten: Die Vorgänger der Methoden noch
 841    * explizit setzen und die zwischengespeicherten Daten wieder
 842    * freigeben. */
 843   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 844     cleanup_irg(get_irp_irg(i));
 845   }
 846 }
 847
 848
 849
 850 static void destruct_walker(ir_node * node, void * env) {
 851   if (get_irn_op(node) == op_Block) {
 852     remove_Block_cg_cfgpred_arr(node);
 853     /* Do not turn Break into Jmp.  Better: merge blocks right away. */
 854     if (get_Block_n_cfgpreds(node) == 1) {
 855       ir_node *pred = get_Block_cfgpred(node, 0);
 856       if (get_irn_op(pred) == op_Break)
 857         exchange(node, get_nodes_block(pred));
 858     }
 859   } else if (get_irn_op(node) == op_Filter) {
 860     set_irg_current_block(current_ir_graph, get_nodes_block(node));
 861     exchange(node, new_Proj(get_Filter_pred(node), get_irn_mode(node), get_Filter_proj(node)));
 862   } else if (get_irn_op(node) == op_Break) {
 863     //set_irg_current_block(current_ir_graph, get_nodes_block(node));
 864     //exchange(node, new_Jmp());
 865   } else if (get_irn_op(node) == op_Call) {
 866     remove_Call_callee_arr(node);
 867   } else if (get_irn_op(node) == op_Proj) {
 868     /*  some ProjX end up in strage blocks. */
 869     set_nodes_block(node, get_nodes_block(get_Proj_pred(node)));
 870   }
 871 }
 872
 873
 874 void cg_destruct(void) {
 875   int i;
 876   if (get_irp_ip_view_state() != ip_view_no) {
 877     for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 878       ir_graph * irg = get_irp_irg(i);
 879       irg_walk_graph(irg, destruct_walker, clear_link, NULL);
 880       set_irg_frame(irg, skip_Id(get_irg_frame(irg)));
 881       set_irg_globals(irg, skip_Id(get_irg_globals(irg)));
 882       set_irg_initial_mem(irg, skip_Id(get_irg_initial_mem(irg)));
 883       set_irg_callee_info_state(irg, irg_callee_info_none);
 884       set_irg_end_reg(irg, get_irg_end(irg));
 885       set_irg_end_except(irg, get_irg_end(irg));
 886     }
 887     set_irp_ip_view(ip_view_no);
 888   }
 889 }