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

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