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

   1 /* Copyright (C) 1998 - 2000 by Universitaet Karlsruhe
   2 ** All rights reserved.
   3 **
   4 ** Authors: Martin Trapp, Christian Schaefer
   5 **
   6 ** ircons.c: basic and more detailed irnode constructors
   7 **           store, block and parameter administration.
   8 ** Adapted to extended FIRM nodes (exceptions...) and commented
   9 **   by Goetz Lindenmaier
  10 */
  11
  12 /* $Id$ */
  13
  14 #ifdef HAVE_CONFIG_H
  15 # include <config.h>
  16 #endif
  17
  18 # include "irgraph_t.h"
  19 # include "irnode_t.h"
  20 # include "irmode_t.h"
  21 # include "ircons.h"
  22 # include "common.h"
  23 # include "irvrfy.h"
  24 # include "irop.h"
  25 # include "iropt_t.h"
  26 # include "irgmod.h"
  27 # include "array.h"
  28 /* memset belongs to string.h */
  29 # include "string.h"
  30
  31 #if USE_EXPICIT_PHI_IN_STACK
  32 /* A stack needed for the automatic Phi node construction in constructor
  33    Phi_in. Redefinition in irgraph.c!! */
  34 struct Phi_in_stack {
  35   ir_node **stack;
  36   int       pos;
  37 };
  38 typedef struct Phi_in_stack Phi_in_stack;
  39 #endif
  40
  41 /*** ******************************************** */
  42 /** privat interfaces, for professional use only */
  43
  44 /* Constructs a Block with a fixed number of predecessors.
  45    Does not set current_block.  Can not be used with automatic
  46    Phi node construction. */
  47 inline ir_node *
  48 new_r_Block (ir_graph *irg,  int arity, ir_node **in)
  49 {
  50   ir_node *res;
  51
  52   res = new_ir_node (irg, NULL, op_Block, mode_R, arity, in);
  53   set_Block_matured(res, 1);
  54   set_Block_block_visited(res, 0);
  55
  56   irn_vrfy (res);
  57   return res;
  58 }
  59
  60 ir_node *
  61 new_r_Start (ir_graph *irg, ir_node *block)
  62 {
  63   ir_node *res;
  64
  65   res = new_ir_node (irg, block, op_Start, mode_T, 0, NULL);
  66
  67   irn_vrfy (res);
  68   return res;
  69 }
  70
  71 ir_node *
  72 new_r_End (ir_graph *irg, ir_node *block)
  73 {
  74   ir_node *res;
  75
  76   res = new_ir_node (irg, block, op_End, mode_X, -1, NULL);
  77
  78   irn_vrfy (res);
  79   return res;
  80 }
  81
  82 /* Creates a Phi node with all predecessors.  Calling this constructor
  83    is only allowed if the corresponding block is mature.  */
  84 ir_node *
  85 new_r_Phi (ir_graph *irg, ir_node *block, int arity, ir_node **in, ir_mode *mode)
  86 {
  87   ir_node *res;
  88
  89   assert( get_Block_matured(block) );
  90   assert( get_irn_arity(block) == arity );
  91
  92   res = new_ir_node (irg, block, op_Phi, mode, arity, in);
  93
  94   res = optimize (res);
  95   irn_vrfy (res);
  96
  97   /* Memory Phis in endless loops must be kept alive.
  98      As we can't distinguish these easily we keep all of them alive. */
  99   if ((res->op == op_Phi) && (mode == mode_M))
 100     add_End_keepalive(irg->end, res);
 101   return res;
 102 }
 103
 104 ir_node *
 105 new_r_Const (ir_graph *irg, ir_node *block, ir_mode *mode, tarval *con)
 106 {
 107   ir_node *res;
 108   res = new_ir_node (irg, block, op_Const, mode, 0, NULL);
 109   res->attr.con = con;
 110   res = optimize (res);
 111   irn_vrfy (res);
 112
 113 #if 0
 114   res = local_optimize_newby (res);
 115 # endif
 116
 117   return res;
 118 }
 119
 120 ir_node *
 121 new_r_Id (ir_graph *irg, ir_node *block, ir_node *val, ir_mode *mode)
 122 {
 123   ir_node *in[1] = {val};
 124   ir_node *res;
 125   res = new_ir_node (irg, block, op_Id, mode, 1, in);
 126   res = optimize (res);
 127   irn_vrfy (res);
 128   return res;
 129 }
 130
 131 ir_node *
 132 new_r_Proj (ir_graph *irg, ir_node *block, ir_node *arg, ir_mode *mode,
 133             long proj)
 134 {
 135   ir_node *in[1] = {arg};
 136   ir_node *res;
 137   res = new_ir_node (irg, block, op_Proj, mode, 1, in);
 138   res->attr.proj = proj;
 139
 140   assert(res);
 141   assert(get_Proj_pred(res));
 142   assert(get_nodes_Block(get_Proj_pred(res)));
 143
 144   res = optimize (res);
 145
 146   irn_vrfy (res);
 147   return res;
 148
 149 }
 150
 151 ir_node *
 152 new_r_defaultProj (ir_graph *irg, ir_node *block, ir_node *arg,
 153                    long max_proj)
 154 {
 155   ir_node *res;
 156   assert((arg->op==op_Cond) && (get_irn_mode(arg->in[1]) == mode_I));
 157   arg->attr.c.kind = fragmentary;
 158   arg->attr.c.default_proj = max_proj;
 159   res = new_r_Proj (irg, block, arg, mode_X, max_proj);
 160   return res;
 161 }
 162
 163 ir_node *
 164 new_r_Conv (ir_graph *irg, ir_node *block, ir_node *op, ir_mode *mode)
 165 {
 166   ir_node *in[1] = {op};
 167   ir_node *res;
 168   res = new_ir_node (irg, block, op_Conv, mode, 1, in);
 169   res = optimize (res);
 170   irn_vrfy (res);
 171   return res;
 172
 173 }
 174
 175 ir_node *
 176 new_r_Tuple (ir_graph *irg, ir_node *block, int arity, ir_node **in)
 177 {
 178   ir_node *res;
 179
 180   res = new_ir_node (irg, block, op_Tuple, mode_T, arity, in);
 181   res = optimize (res);
 182   irn_vrfy (res);
 183   return res;
 184 }
 185
 186 inline ir_node *
 187 new_r_Add (ir_graph *irg, ir_node *block,
 188            ir_node *op1, ir_node *op2, ir_mode *mode)
 189 {
 190   ir_node *in[2] = {op1, op2};
 191   ir_node *res;
 192   res = new_ir_node (irg, block, op_Add, mode, 2, in);
 193   res = optimize (res);
 194   irn_vrfy (res);
 195   return res;
 196 }
 197
 198 inline ir_node *
 199 new_r_Sub (ir_graph *irg, ir_node *block,
 200            ir_node *op1, ir_node *op2, ir_mode *mode)
 201 {
 202   ir_node *in[2] = {op1, op2};
 203   ir_node *res;
 204   res = new_ir_node (irg, block, op_Sub, mode, 2, in);
 205   res = optimize (res);
 206   irn_vrfy (res);
 207   return res;
 208 }
 209
 210 inline ir_node *
 211 new_r_Minus (ir_graph *irg, ir_node *block,
 212              ir_node *op,  ir_mode *mode)
 213 {
 214   ir_node *in[1] = {op};
 215   ir_node *res;
 216   res = new_ir_node (irg, block, op_Minus, mode, 1, in);
 217   res = optimize (res);
 218   irn_vrfy (res);
 219   return res;
 220 }
 221
 222 inline ir_node *
 223 new_r_Mul (ir_graph *irg, ir_node *block,
 224            ir_node *op1, ir_node *op2, ir_mode *mode)
 225 {
 226   ir_node *in[2] = {op1, op2};
 227   ir_node *res;
 228   res = new_ir_node (irg, block, op_Mul, mode, 2, in);
 229   res = optimize (res);
 230   irn_vrfy (res);
 231   return res;
 232 }
 233
 234 inline ir_node *
 235 new_r_Quot (ir_graph *irg, ir_node *block,
 236             ir_node *memop, ir_node *op1, ir_node *op2)
 237 {
 238   ir_node *in[3] = {memop, op1, op2};
 239   ir_node *res;
 240   res = new_ir_node (irg, block, op_Quot, mode_T, 3, in);
 241   res = optimize (res);
 242   irn_vrfy (res);
 243   return res;
 244 }
 245
 246 inline ir_node *
 247 new_r_DivMod (ir_graph *irg, ir_node *block,
 248               ir_node *memop, ir_node *op1, ir_node *op2)
 249 {
 250   ir_node *in[3] = {memop, op1, op2};
 251   ir_node *res;
 252   res = new_ir_node (irg, block, op_DivMod, mode_T, 3, in);
 253   res = optimize (res);
 254   irn_vrfy (res);
 255   return res;
 256 }
 257
 258 inline ir_node *
 259 new_r_Div (ir_graph *irg, ir_node *block,
 260            ir_node *memop, ir_node *op1, ir_node *op2)
 261 {
 262   ir_node *in[3] = {memop, op1, op2};
 263   ir_node *res;
 264   res = new_ir_node (irg, block, op_Div, mode_T, 3, in);
 265   res = optimize (res);
 266   irn_vrfy (res);
 267   return res;
 268 }
 269
 270 inline ir_node *
 271 new_r_Mod (ir_graph *irg, ir_node *block,
 272            ir_node *memop, ir_node *op1, ir_node *op2)
 273 {
 274   ir_node *in[3] = {memop, op1, op2};
 275   ir_node *res;
 276   res = new_ir_node (irg, block, op_Mod, mode_T, 3, in);
 277   res = optimize (res);
 278   irn_vrfy (res);
 279   return res;
 280 }
 281
 282 inline ir_node *
 283 new_r_And (ir_graph *irg, ir_node *block,
 284            ir_node *op1, ir_node *op2, ir_mode *mode)
 285 {
 286   ir_node *in[2] = {op1, op2};
 287   ir_node *res;
 288   res = new_ir_node (irg, block, op_And, mode, 2, in);
 289   res = optimize (res);
 290   irn_vrfy (res);
 291   return res;
 292 }
 293
 294 inline ir_node *
 295 new_r_Or (ir_graph *irg, ir_node *block,
 296           ir_node *op1, ir_node *op2, ir_mode *mode)
 297 {
 298   ir_node *in[2] = {op1, op2};
 299   ir_node *res;
 300   res = new_ir_node (irg, block, op_Or, mode, 2, in);
 301   res = optimize (res);
 302   irn_vrfy (res);
 303   return res;
 304 }
 305
 306 inline ir_node *
 307 new_r_Eor (ir_graph *irg, ir_node *block,
 308           ir_node *op1, ir_node *op2, ir_mode *mode)
 309 {
 310   ir_node *in[2] = {op1, op2};
 311   ir_node *res;
 312   res = new_ir_node (irg, block, op_Eor, mode, 2, in);
 313   res = optimize (res);
 314   irn_vrfy (res);
 315   return res;
 316 }
 317
 318 inline ir_node *
 319 new_r_Not    (ir_graph *irg, ir_node *block,
 320               ir_node *op, ir_mode *mode)
 321 {
 322   ir_node *in[1] = {op};
 323   ir_node *res;
 324   res = new_ir_node (irg, block, op_Not, mode, 1, in);
 325   res = optimize (res);
 326   irn_vrfy (res);
 327   return res;
 328 }
 329
 330 inline ir_node *
 331 new_r_Shl (ir_graph *irg, ir_node *block,
 332           ir_node *op, ir_node *k, ir_mode *mode)
 333 {
 334   ir_node *in[2] = {op, k};
 335   ir_node *res;
 336   res = new_ir_node (irg, block, op_Shl, mode, 2, in);
 337   res = optimize (res);
 338   irn_vrfy (res);
 339   return res;
 340 }
 341
 342 inline ir_node *
 343 new_r_Shr (ir_graph *irg, ir_node *block,
 344            ir_node *op, ir_node *k, ir_mode *mode)
 345 {
 346   ir_node *in[2] = {op, k};
 347   ir_node *res;
 348   res = new_ir_node (irg, block, op_Shr, mode, 2, in);
 349   res = optimize (res);
 350   irn_vrfy (res);
 351   return res;
 352 }
 353
 354 inline ir_node *
 355 new_r_Shrs (ir_graph *irg, ir_node *block,
 356            ir_node *op, ir_node *k, ir_mode *mode)
 357 {
 358   ir_node *in[2] = {op, k};
 359   ir_node *res;
 360   res = new_ir_node (irg, block, op_Shrs, mode, 2, in);
 361   res = optimize (res);
 362   irn_vrfy (res);
 363   return res;
 364 }
 365
 366 inline ir_node *
 367 new_r_Rot (ir_graph *irg, ir_node *block,
 368            ir_node *op, ir_node *k, ir_mode *mode)
 369 {
 370   ir_node *in[2] = {op, k};
 371   ir_node *res;
 372   res = new_ir_node (irg, block, op_Rot, mode, 2, in);
 373   res = optimize (res);
 374   irn_vrfy (res);
 375   return res;
 376 }
 377
 378 inline ir_node *
 379 new_r_Abs (ir_graph *irg, ir_node *block,
 380            ir_node *op, ir_mode *mode)
 381 {
 382   ir_node *in[1] = {op};
 383   ir_node *res;
 384   res = new_ir_node (irg, block, op_Abs, mode, 1, in);
 385   res = optimize (res);
 386   irn_vrfy (res);
 387   return res;
 388 }
 389
 390 inline ir_node *
 391 new_r_Cmp (ir_graph *irg, ir_node *block,
 392            ir_node *op1, ir_node *op2)
 393 {
 394   ir_node *in[2] = {op1, op2};
 395   ir_node *res;
 396   res = new_ir_node (irg, block, op_Cmp, mode_T, 2, in);
 397   res = optimize (res);
 398   irn_vrfy (res);
 399   return res;
 400 }
 401
 402 inline ir_node *
 403 new_r_Jmp (ir_graph *irg, ir_node *block)
 404 {
 405   ir_node *in[0] = {};
 406   ir_node *res;
 407   res = new_ir_node (irg, block, op_Jmp, mode_X, 0, in);
 408   res = optimize (res);
 409   irn_vrfy (res);
 410   return res;
 411 }
 412
 413 inline ir_node *
 414 new_r_Cond (ir_graph *irg, ir_node *block, ir_node *c)
 415 {
 416   ir_node *in[1] = {c};
 417   ir_node *res;
 418   res = new_ir_node (irg, block, op_Cond, mode_T, 1, in);
 419   res->attr.c.kind = dense;
 420   res->attr.c.default_proj = 0;
 421   res = optimize (res);
 422   irn_vrfy (res);
 423   return res;
 424 }
 425
 426 ir_node *
 427 new_r_Call (ir_graph *irg, ir_node *block, ir_node *store,
 428             ir_node *callee, int arity, ir_node **in, type *type)
 429 {
 430   ir_node **r_in;
 431   ir_node *res;
 432   int r_arity;
 433
 434   r_arity = arity+2;
 435   NEW_ARR_A (ir_node *, r_in, r_arity);
 436   r_in[0] = store;
 437   r_in[1] = callee;
 438   memcpy (&r_in[2], in, sizeof (ir_node *) * arity);
 439
 440   res = new_ir_node (irg, block, op_Call, mode_T, r_arity, r_in);
 441
 442   assert(is_method_type(type));
 443   set_Call_type(res, type);
 444   res = optimize (res);
 445   irn_vrfy (res);
 446   return res;
 447 }
 448
 449 ir_node *
 450 new_r_Return (ir_graph *irg, ir_node *block,
 451               ir_node *store, int arity, ir_node **in)
 452 {
 453   ir_node **r_in;
 454   ir_node *res;
 455   int r_arity;
 456
 457   r_arity = arity+1;
 458   NEW_ARR_A (ir_node *, r_in, r_arity);
 459   r_in[0] = store;
 460   memcpy (&r_in[1], in, sizeof (ir_node *) * arity);
 461   res = new_ir_node (irg, block, op_Return, mode_X, r_arity, r_in);
 462   res = optimize (res);
 463   irn_vrfy (res);
 464   return res;
 465 }
 466
 467 inline ir_node *
 468 new_r_Raise (ir_graph *irg, ir_node *block, ir_node *store, ir_node *obj)
 469 {
 470   ir_node *in[2] = {store, obj};
 471   ir_node *res;
 472   res = new_ir_node (irg, block, op_Raise, mode_T, 2, in);
 473
 474   // DEBUG
 475   fprintf (stdout, "%s: res = %p\n", __PRETTY_FUNCTION__, res);
 476
 477   res = optimize (res);
 478   irn_vrfy (res);
 479   return res;
 480 }
 481
 482 inline ir_node *
 483 new_r_Load (ir_graph *irg, ir_node *block,
 484             ir_node *store, ir_node *adr)
 485 {
 486   ir_node *in[2] = {store, adr};
 487   ir_node *res;
 488   res = new_ir_node (irg, block, op_Load, mode_T, 2, in);
 489
 490   res = optimize (res);
 491   irn_vrfy (res);
 492   return res;
 493 }
 494
 495 inline ir_node *
 496 new_r_Store (ir_graph *irg, ir_node *block,
 497              ir_node *store, ir_node *adr, ir_node *val)
 498 {
 499   ir_node *in[3] = {store, adr, val};
 500   ir_node *res;
 501   res = new_ir_node (irg, block, op_Store, mode_T, 3, in);
 502
 503   res = optimize (res);
 504   irn_vrfy (res);
 505   return res;
 506 }
 507
 508 inline ir_node *
 509 new_r_Alloc (ir_graph *irg, ir_node *block, ir_node *store,
 510             ir_node *size, type *alloc_type, where_alloc where)
 511 {
 512   ir_node *in[2] = {store, size};
 513   ir_node *res;
 514   res = new_ir_node (irg, block, op_Alloc, mode_T, 2, in);
 515
 516   res->attr.a.where = where;
 517   res->attr.a.type = alloc_type;
 518
 519   res = optimize (res);
 520   irn_vrfy (res);
 521   return res;
 522 }
 523
 524 inline ir_node *
 525 new_r_Free (ir_graph *irg, ir_node *block, ir_node *store,
 526             ir_node *ptr, ir_node *size, type *free_type)
 527 {
 528   ir_node *in[3] = {store, ptr, size};
 529   ir_node *res;
 530   res = new_ir_node (irg, block, op_Free, mode_T, 3, in);
 531
 532   res->attr.f = free_type;
 533
 534   res = optimize (res);
 535   irn_vrfy (res);
 536   return res;
 537 }
 538
 539 inline ir_node *
 540 new_r_Sel (ir_graph *irg, ir_node *block, ir_node *store, ir_node *objptr,
 541            int arity, ir_node **in, entity *ent)
 542 {
 543   ir_node **r_in;
 544   ir_node *res;
 545   int r_arity;
 546
 547   r_arity = arity + 2;
 548   NEW_ARR_A (ir_node *, r_in, r_arity);
 549   r_in[0] = store;
 550   r_in[1] = objptr;
 551   memcpy (&r_in[2], in, sizeof (ir_node *) * arity);
 552   res = new_ir_node (irg, block, op_Sel, mode_p, r_arity, r_in);
 553
 554   res->attr.s.ltyp = static_linkage;
 555   res->attr.s.ent = ent;
 556
 557   res = optimize (res);
 558   irn_vrfy (res);
 559   return res;
 560 }
 561
 562 inline ir_node *
 563 new_r_SymConst (ir_graph *irg, ir_node *block, type_or_id_p value,
 564                 symconst_kind symkind)
 565 {
 566   ir_node *in[0] = {};
 567   ir_node *res;
 568   ir_mode *mode;
 569   if (symkind == linkage_ptr_info)
 570     mode = mode_p;
 571   else
 572     mode = mode_I;
 573   res = new_ir_node (irg, block, op_SymConst, mode, 0, in);
 574
 575   res->attr.i.num = symkind;
 576   if (symkind == linkage_ptr_info) {
 577     res->attr.i.tori.ptrinfo = (ident *)value;
 578   } else {
 579     assert (   (   (symkind == type_tag)
 580                 || (symkind == size))
 581             && (is_type(value)));
 582     res->attr.i.tori.typ = (type *)value;
 583   }
 584   res = optimize (res);
 585   irn_vrfy (res);
 586   return res;
 587 }
 588
 589 ir_node *
 590 new_r_Sync (ir_graph *irg, ir_node *block, int arity, ir_node **in)
 591 {
 592   ir_node *res;
 593
 594   res = new_ir_node (irg, block, op_Sync, mode_M, arity, in);
 595
 596   res = optimize (res);
 597   irn_vrfy (res);
 598   return res;
 599 }
 600
 601 ir_node *
 602 new_r_Bad ()
 603 {
 604   return current_ir_graph->bad;
 605 }
 606
 607 /** ********************/
 608 /** public interfaces  */
 609 /** construction tools */
 610
 611 /****f* ircons/new_Start
 612  *
 613  * NAME
 614  *   new_Start -- create a new Start node in the current block
 615  *
 616  * SYNOPSIS
 617  *   s = new_Start(void);
 618  *   ir_node* new_Start(void);
 619  *
 620  * RESULT
 621  *   s - pointer to the created Start node
 622  *
 623  ****
 624  */
 625 ir_node *
 626 new_Start (void)
 627 {
 628   ir_node *res;
 629
 630   res = new_ir_node (current_ir_graph, current_ir_graph->current_block,
 631                      op_Start, mode_T, 0, NULL);
 632
 633   res = optimize (res);
 634   irn_vrfy (res);
 635   return res;
 636 }
 637
 638 ir_node *
 639 new_End (void)
 640 {
 641   ir_node *res;
 642   res = new_ir_node (current_ir_graph,  current_ir_graph->current_block,
 643                      op_End, mode_X, -1, NULL);
 644   res = optimize (res);
 645   irn_vrfy (res);
 646
 647   return res;
 648 }
 649
 650 /* Constructs a Block with a fixed number of predecessors.
 651    Does set current_block.  Can be used with automatic Phi
 652    node construction. */
 653 ir_node *
 654 new_Block (int arity, ir_node **in)
 655 {
 656   ir_node *res;
 657
 658   res = new_r_Block (current_ir_graph, arity, in);
 659
 660   /* Create and initialize array for Phi-node construction. */
 661   res->attr.block.graph_arr = NEW_ARR_D (ir_node *, current_ir_graph->obst,
 662                                          current_ir_graph->n_loc);
 663   memset(res->attr.block.graph_arr, 0, sizeof(ir_node *)*current_ir_graph->n_loc);
 664
 665   res = optimize (res);
 666   current_ir_graph->current_block = res;
 667
 668   irn_vrfy (res);
 669
 670   return res;
 671 }
 672
 673 /* ***********************************************************************/
 674 /* Methods necessary for automatic Phi node creation                     */
 675 /*
 676   ir_node *phi_merge            (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
 677   ir_node *get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
 678   ir_node *new_r_Phi0           (ir_graph *irg, ir_node *block, ir_mode *mode)
 679   ir_node *new_r_Phi_in         (ir_graph *irg, ir_node *block, ir_mode *mode,  ir_node **in, int ins)
 680
 681   Call Graph:   ( A ---> B == A "calls" B)
 682
 683        get_value         mature_block
 684           |                   |
 685           |                   |
 686           |                   |
 687           |          ---> phi_merge
 688           |         /       /   \
 689           |        /       /     \
 690          \|/      /      |/_      \
 691        get_r_value_internal        |
 692                 |                  |
 693                 |                  |
 694                \|/                \|/
 695             new_r_Phi0          new_r_Phi_in
 696
 697 * *************************************************************************** */
 698
 699 /* Creates a Phi node with 0 predecessors */
 700 inline ir_node *
 701 new_r_Phi0 (ir_graph *irg, ir_node *block, ir_mode *mode)
 702 {
 703   ir_node *res;
 704   res = new_ir_node (irg, block, op_Phi, mode, 0, NULL);
 705   irn_vrfy (res);
 706   return res;
 707 }
 708
 709 /* There are two implementations of the Phi node construction.  The first
 710    is faster, but does not work for blocks with more than 2 predecessors.
 711    The second works always but is slower and causes more unnecessary Phi
 712    nodes.
 713    Select the implementations by the following preprocessor flag set in
 714    common/common.h: */
 715 #if USE_FAST_PHI_CONSTRUCTION
 716
 717 /* This is a stack used for allocating and deallocating nodes in
 718    new_r_Phi_in.  The original implementation used the obstack
 719    to model this stack, now it is explicit.  This reduces side effects.
 720 */
 721 #if USE_EXPICIT_PHI_IN_STACK
 722 Phi_in_stack *
 723 new_Phi_in_stack() {
 724   Phi_in_stack *res;
 725
 726   res = (Phi_in_stack *) malloc ( sizeof (Phi_in_stack));
 727
 728   res->stack = NEW_ARR_F (ir_node *, 1);
 729   res->pos = 0;
 730
 731   return res;
 732 }
 733
 734 void
 735 free_Phi_in_stack(Phi_in_stack *s) {
 736   DEL_ARR_F(s->stack);
 737   free(s);
 738 }
 739
 740 void free_to_Phi_in_stack(ir_node *phi) {
 741   assert(get_irn_opcode(phi) == iro_Phi);
 742
 743   if (ARR_LEN(current_ir_graph->Phi_in_stack->stack) ==
 744       current_ir_graph->Phi_in_stack->pos)
 745     ARR_APP1 (ir_node *, current_ir_graph->Phi_in_stack->stack, phi);
 746   else
 747     current_ir_graph->Phi_in_stack->stack[current_ir_graph->Phi_in_stack->pos] = phi;
 748
 749   (current_ir_graph->Phi_in_stack->pos)++;
 750 }
 751
 752 ir_node *
 753 alloc_or_pop_from_Phi_in_stack(ir_graph *irg, ir_node *block, ir_mode *mode,
 754              int arity, ir_node **in) {
 755   ir_node *res;
 756   ir_node **stack = current_ir_graph->Phi_in_stack->stack;
 757   int pos = current_ir_graph->Phi_in_stack->pos;
 758
 759
 760   if (pos == 0) {
 761     /* We need to allocate a new node */
 762     res = new_ir_node (irg, block, op_Phi, mode, arity, in);
 763   } else {
 764     /* reuse the old node and initialize it again. */
 765     res = stack[pos-1];
 766
 767     assert (res->kind == k_ir_node);
 768     assert (res->op == op_Phi);
 769     res->mode = mode;
 770     res->visited = 0;
 771     res->link = NULL;
 772     assert (arity >= 0);
 773     /* ???!!! How to free the old in array??  */
 774     res->in = NEW_ARR_D (ir_node *, irg->obst, (arity+1));
 775     res->in[0] = block;
 776     memcpy (&res->in[1], in, sizeof (ir_node *) * arity);
 777
 778     (current_ir_graph->Phi_in_stack->pos)--;
 779   }
 780   return res;
 781 }
 782 #endif /* USE_EXPICIT_PHI_IN_STACK */
 783
 784 /* Creates a Phi node with a given, fixed array **in of predecessors.
 785    If the Phi node is unnecessary, as the same value reaches the block
 786    through all control flow paths, it is eliminated and the value
 787    returned directly.  This constructor is only intended for use in
 788    the automatic Phi node generation triggered by get_value or mature.
 789    The implementation is quite tricky and depends on the fact, that
 790    the nodes are allocated on a stack:
 791    The in array contains predecessors and NULLs.  The NULLs appear,
 792    if get_r_value_internal, that computed the predecessors, reached
 793    the same block on two paths.  In this case the same value reaches
 794    this block on both paths, there is no definition in between.  We need
 795    not allocate a Phi where these path's merge, but we have to communicate
 796    this fact to the caller.  This happens by returning a pointer to the
 797    node the caller _will_ allocate.  (Yes, we predict the address. We can
 798    do so because the nodes are allocated on the obstack.)  The caller then
 799    finds a pointer to itself and, when this routine is called again,
 800    eliminates itself.
 801    */
 802 inline ir_node *
 803 new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode,
 804               ir_node **in, int ins)
 805 {
 806   int i;
 807   ir_node *res, *known;
 808
 809   /* allocate a new node on the obstack.
 810      This can return a node to which some of the pointers in the in-array
 811      already point.
 812      Attention: the constructor copies the in array, i.e., the later changes
 813      to the array in this routine do not affect the constructed node!  If
 814      the in array contains NULLs, there will be missing predecessors in the
 815      returned node.
 816      Is this a possible internal state of the Phi node generation? */
 817 #if USE_EXPICIT_PHI_IN_STACK
 818   res = known = alloc_or_pop_from_Phi_in_stack(irg, block, mode, ins, in);
 819 #else
 820   res = known = new_ir_node (irg, block, op_Phi, mode, ins, in);
 821 #endif
 822   /* The in-array can contain NULLs.  These were returned by
 823      get_r_value_internal if it reached the same block/definition on a
 824      second path.
 825      The NULLs are replaced by the node itself to simplify the test in the
 826      next loop. */
 827   for (i=0;  i < ins;  ++i)
 828     if (in[i] == NULL) in[i] = res;
 829
 830   /* This loop checks whether the Phi has more than one predecessor.
 831      If so, it is a real Phi node and we break the loop.  Else the
 832      Phi node merges the same definition on several paths and therefore
 833      is not needed. */
 834   for (i=0;  i < ins;  ++i)
 835   {
 836     if (in[i]==res || in[i]==known) continue;
 837
 838     if (known==res)
 839       known = in[i];
 840     else
 841       break;
 842   }
 843
 844   /* i==ins: there is at most one predecessor, we don't need a phi node. */
 845   if (i==ins) {
 846 #if USE_EXPICIT_PHI_IN_STACK
 847     free_to_Phi_in_stack(res);
 848 #else
 849     obstack_free (current_ir_graph->obst, res);
 850 #endif
 851     res = known;
 852   } else {
 853     res = optimize (res);
 854     irn_vrfy (res);
 855   }
 856
 857   /* return the pointer to the Phi node.  This node might be deallocated! */
 858   return res;
 859 }
 860
 861 inline ir_node *
 862 get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
 863
 864 /** This function computes the predecessors for a real Phi node, and then
 865     allocates and returns this node.  The routine called to allocate the
 866     node might optimize it away and return a real value, or even a pointer
 867     to a deallocated Phi node on top of the obstack!
 868     This function is called with an in-array of proper size. **/
 869 static inline ir_node *
 870 phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
 871 {
 872   ir_node *prevBlock, *res;
 873   int i;
 874
 875   /* This loop goes to all predecessor blocks of the block the Phi node is in
 876      and there finds the operands of the Phi node by calling
 877      get_r_value_internal. */
 878   for (i = 1;  i <= ins;  ++i) {
 879     assert (block->in[i]);
 880     prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */
 881     assert (prevBlock);
 882     nin[i-1] = get_r_value_internal (prevBlock, pos, mode);
 883   }
 884
 885   /* After collecting all predecessors into the array nin a new Phi node
 886      with these predecessors is created.  This constructor contains an
 887      optimization: If all predecessors of the Phi node are identical it
 888      returns the only operand instead of a new Phi node.  If the value
 889      passes two different control flow edges without being defined, and
 890      this is the second path treated, a pointer to the node that will be
 891      allocated for the first path (recursion) is returned.  We already
 892      know the address of this node, as it is the next node to be allocated
 893      and will be placed on top of the obstack. (The obstack is a _stack_!) */
 894   res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins);
 895
 896   /* Now we now the value for "pos" and can enter it in the array with
 897      all known local variables.  Attention: this might be a pointer to
 898      a node, that later will be allocated!!! See new_r_Phi_in.
 899      If this is called in mature, after some set_value in the same block,
 900      the proper value must not be overwritten:
 901      The call order
 902        get_value    (makes Phi0, put's it into graph_arr)
 903        set_value    (overwrites Phi0 in graph_arr)
 904        mature_block (upgrades Phi0, puts it again into graph_arr, overwriting
 905                      the proper value.)
 906      fails. */
 907   if (!block->attr.block.graph_arr[pos]) {
 908     block->attr.block.graph_arr[pos] = res;
 909   } else {
 910     /*  printf(" value already computed by %s\n",
 911         id_to_str(block->attr.block.graph_arr[pos]->op->name));  */
 912   }
 913
 914   return res;
 915 }
 916
 917 /* This function returns the last definition of a variable.  In case
 918    this variable was last defined in a previous block, Phi nodes are
 919    inserted.  If the part of the firm graph containing the definition
 920    is not yet constructed, a dummy Phi node is returned. */
 921 inline ir_node *
 922 get_r_value_internal (ir_node *block, int pos, ir_mode *mode)
 923 {
 924   ir_node *res;
 925   /* There are 4 cases to treat.
 926
 927      1. The block is not mature and we visit it the first time.  We can not
 928         create a proper Phi node, therefore a Phi0, i.e., a Phi without
 929         predecessors is returned.  This node is added to the linked list (field
 930         "link") of the containing block to be completed when this block is
 931         matured. (Completion will add a new Phi and turn the Phi0 into an Id
 932         node.)
 933
 934      2. The value is already known in this block, graph_arr[pos] is set and we
 935         visit the block the first time.  We can return the value without
 936         creating any new nodes.
 937
 938      3. The block is mature and we visit it the first time.  A Phi node needs
 939         to be created (phi_merge).  If the Phi is not needed, as all it's
 940         operands are the same value reaching the block through different
 941         paths, it's optimized away and the value itself is returned.
 942
 943      4. The block is mature, and we visit it the second time.  Now two
 944         subcases are possible:
 945         * The value was computed completely the last time we were here. This
 946           is the case if there is no loop.  We can return the proper value.
 947         * The recursion that visited this node and set the flag did not
 948           return yet.  We are computing a value in a loop and need to
 949           break the recursion without knowing the result yet.
 950           @@@ strange case.  Straight forward we would create a Phi before
 951           starting the computation of it's predecessors.  In this case we will
 952           find a Phi here in any case.  The problem is that this implementation
 953           only creates a Phi after computing the predecessors, so that it is
 954           hard to compute self references of this Phi.  @@@
 955         There is no simple check for the second subcase.  Therefore we check
 956         for a second visit and treat all such cases as the second subcase.
 957         Anyways, the basic situation is the same:  we reached a block
 958         on two paths without finding a definition of the value:  No Phi
 959         nodes are needed on both paths.
 960         We return this information "Two paths, no Phi needed" by a very tricky
 961         implementation that relies on the fact that an obstack is a stack and
 962         will return a node with the same address on different allocations.
 963         Look also at phi_merge and new_r_phi_in to understand this.
 964         @@@ Unfortunately this does not work, see testprogram
 965         three_cfpred_example.
 966
 967   */
 968
 969   /* case 4 -- already visited. */
 970   if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) return NULL;
 971
 972   /* visited the first time */
 973   set_irn_visited(block, get_irg_visited(current_ir_graph));
 974
 975   /* Get the local valid value */
 976   res = block->attr.block.graph_arr[pos];
 977
 978   /* case 2 -- If the value is actually computed, return it. */
 979   if (res) { return res;};
 980
 981   if (block->attr.block.matured) { /* case 3 */
 982
 983     /* The Phi has the same amount of ins as the corresponding block. */
 984     int ins = get_irn_arity(block);
 985     ir_node **nin;
 986     NEW_ARR_A (ir_node *, nin, ins);
 987
 988     /* Phi merge collects the predecessors and then creates a node. */
 989     res = phi_merge (block, pos, mode, nin, ins);
 990
 991   } else {  /* case 1 */
 992     /* The block is not mature, we don't know how many in's are needed.  A Phi
 993        with zero predecessors is created.  Such a Phi node is called Phi0
 994        node.  (There is also an obsolete Phi0 opcode.) The Phi0 is then added
 995        to the list of Phi0 nodes in this block to be matured by mature_block
 996        later.
 997        The Phi0 has to remember the pos of it's internal value.  If the real
 998        Phi is computed, pos is used to update the array with the local
 999        values. */
1000
1001     res = new_r_Phi0 (current_ir_graph, block, mode);
1002     res->attr.phi0_pos = pos;
1003     res->link = block->link;
1004     block->link = res;
1005   }
1006
1007   /* If we get here, the frontend missed a use-before-definition error */
1008   if (!res) {
1009     /* Error Message */
1010     printf("Error: no value set.  Use of undefined variable.  Initializing
1011             to zero.\n");
1012     assert (mode->code >= irm_f && mode->code <= irm_p);
1013     res = new_r_Const (current_ir_graph, block, mode,
1014                        tarval_mode_null[mode->code]);
1015   }
1016
1017   /* The local valid value is available now. */
1018   block->attr.block.graph_arr[pos] = res;
1019
1020   return res;
1021 }
1022
1023 #else /* if 0 */
1024
1025 /** This is the simple algorithm.  If first generates a Phi0, then
1026     it starts the recursion.  This causes an Id at the entry of
1027     every block that has no definition of the value! **/
1028
1029 #if USE_EXPICIT_PHI_IN_STACK
1030 /* Just dummies */
1031 Phi_in_stack * new_Phi_in_stack() {  return NULL; }
1032 void free_Phi_in_stack(Phi_in_stack *s) { }
1033 #endif
1034
1035 inline ir_node *
1036 new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode,
1037               ir_node **in, int ins)
1038 {
1039   int i;
1040   ir_node *res, *known;
1041
1042   /* Allocate a new node on the obstack.  The allocation copies the in
1043      array. */
1044   res = new_ir_node (irg, block, op_Phi, mode, ins, in);
1045
1046   /* This loop checks whether the Phi has more than one predecessor.
1047      If so, it is a real Phi node and we break the loop.  Else the
1048      Phi node merges the same definition on several paths and therefore
1049      is not needed. Don't consider Bad nodes! */
1050   known = res;
1051   for (i=0;  i < ins;  ++i)
1052   {
1053         assert(in[i]);
1054
1055     if (in[i]==res || in[i]==known || is_Bad(in[i])) continue;
1056
1057     if (known==res)
1058       known = in[i];
1059     else
1060       break;
1061   }
1062
1063   /* i==ins: there is at most one predecessor, we don't need a phi node. */
1064   if (i==ins) {
1065     if (res != known) {
1066       obstack_free (current_ir_graph->obst, res);
1067       res = known;
1068     } else {
1069       /* A undefined value, e.g., in unreachable code. */
1070       res = new_Bad();
1071     }
1072   } else {
1073     res = optimize (res);
1074     irn_vrfy (res);
1075     /* Memory Phis in endless loops must be kept alive.
1076        As we can't distinguish these easily we keep all of the alive. */
1077     if ((res->op == op_Phi) && (mode == mode_M))
1078       add_End_keepalive(irg->end, res);
1079   }
1080
1081   return res;
1082 }
1083
1084 inline ir_node *
1085 get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
1086
1087 #if PRECISE_EXC_CONTEXT
1088 static inline ir_node *
1089 phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins);
1090
1091 inline ir_node **
1092 new_frag_arr (ir_node *n) {
1093   ir_node **arr;
1094   arr = NEW_ARR_D (ir_node *, current_ir_graph->obst, current_ir_graph->n_loc);
1095   memcpy(arr, current_ir_graph->current_block->attr.block.graph_arr,
1096          sizeof(ir_node *)*current_ir_graph->n_loc);
1097   /* Here we rely on the fact that all frag ops have Memory as first result! */
1098   if (get_irn_op(n) == op_Call)
1099     arr[0] = new_Proj(n, mode_M, 3);
1100   else
1101     arr[0] = new_Proj(n, mode_M, 0);
1102   current_ir_graph->current_block->attr.block.graph_arr[current_ir_graph->n_loc-1] = n;
1103   return arr;
1104 }
1105
1106 inline ir_node **
1107 get_frag_arr (ir_node *n) {
1108   if (get_irn_op(n) == op_Call) {
1109     return n->attr.call.frag_arr;
1110   } else if (get_irn_op(n) == op_Alloc) {
1111     return n->attr.a.frag_arr;
1112   } else {
1113     return n->attr.frag_arr;
1114   }
1115 }
1116
1117 inline ir_node *
1118 set_frag_value(ir_node **frag_arr, int pos, ir_node *val) {
1119   if (!frag_arr[pos]) frag_arr[pos] = val;
1120   if (frag_arr[current_ir_graph->n_loc - 1])
1121     set_frag_value (get_frag_arr(frag_arr[current_ir_graph->n_loc - 1]), pos, val);
1122 }
1123
1124 inline ir_node *
1125 get_r_frag_value_internal (ir_node *block, ir_node *cfOp, int pos, ir_mode *mode) {
1126   ir_node *res;
1127   ir_node **rem;
1128   ir_node **frag_arr;
1129
1130   assert(is_fragile_op(cfOp) && (get_irn_op(cfOp) != op_Bad));
1131
1132   frag_arr = get_frag_arr(cfOp);
1133   res = frag_arr[pos];
1134   if (!res) {
1135     if (block->attr.block.graph_arr[pos]) {
1136       /* There was a set_value after the cfOp and no get_value before that
1137          set_value.  We must build a Phi node now. */
1138       if (block->attr.block.matured) {
1139         int ins = get_irn_arity(block);
1140         ir_node **nin;
1141         NEW_ARR_A (ir_node *, nin, ins);
1142         res = phi_merge(block, pos, mode, nin, ins);
1143       } else {
1144         res = new_r_Phi0 (current_ir_graph, block, mode);
1145         res->attr.phi0_pos = pos;
1146         res->link = block->link;
1147         block->link = res;
1148       }
1149       assert(res);
1150       /* @@@ tested by Flo: set_frag_value(frag_arr, pos, res);
1151          but this should be better: (remove comment if this works) */
1152       /* It's a Phi, we can write this into all graph_arrs with NULL */
1153       set_frag_value(block->attr.block.graph_arr, pos, res);
1154     } else {
1155       res = get_r_value_internal(block, pos, mode);
1156       set_frag_value(block->attr.block.graph_arr, pos, res);
1157     }
1158   }
1159   return res;
1160 }
1161 #endif
1162
1163 /** This function allocates a dummy Phi node to break recursions,
1164     computes the predecessors for the real phi node, and then
1165     allocates and returns this node.  The routine called to allocate the
1166     node might optimize it away and return a real value.
1167     This function is called with an in-array of proper size. **/
1168 static inline ir_node *
1169 phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
1170 {
1171   ir_node *prevBlock, *prevCfOp, *res, *phi0;
1172   int i;
1173
1174   /* If this block has no value at pos create a Phi0 and remember it
1175      in graph_arr to break recursions.
1176      Else we may not set graph_arr as there a later value is remembered. */
1177   phi0 = NULL;
1178   if (!block->attr.block.graph_arr[pos]) {
1179     /* This is commented out as collapsing to Bads is no good idea.
1180        Either we need an assert here, or we need to call a routine
1181        that deals with this case as appropriate for the given language.
1182        Right now a self referencing Id is created which will crash irg_vrfy().
1183
1184        Even if all variables are defined before use, it can happen that
1185        we get to the start block, if a cond has been replaced by a tuple
1186        (bad, jmp).  As the start has a self referencing control flow edge,
1187        we get a self referencing Id, which is hard to optimize away.  We avoid
1188        this by defining the value as a Bad node.
1189        Returning a const with tarval_bad is a preliminary solution.  In some
1190        situations we might want a Warning or an Error. */
1191
1192     if (block == get_irg_start_block(current_ir_graph)) {
1193       block->attr.block.graph_arr[pos] = new_Const(mode, tarval_bad);
1194       /* We don't need to care about exception ops in the start block.
1195          There are none by definition. */
1196       return block->attr.block.graph_arr[pos];
1197     } else {
1198       phi0 = new_r_Phi0(current_ir_graph, block, mode);
1199       block->attr.block.graph_arr[pos] = phi0;
1200 #if PRECISE_EXC_CONTEXT
1201       /* Set graph_arr for fragile ops.  Also here we should break recursion.
1202          We could choose a cyclic path through an cfop.  But the recursion would
1203          break at some point. */
1204       set_frag_value(block->attr.block.graph_arr, pos, phi0);
1205 #endif
1206     }
1207   }
1208
1209   /* This loop goes to all predecessor blocks of the block the Phi node
1210      is in and there finds the operands of the Phi node by calling
1211      get_r_value_internal.  */
1212   for (i = 1;  i <= ins;  ++i) {
1213     prevCfOp = skip_Proj(block->in[i]);
1214     assert (prevCfOp);
1215     if (is_Bad(prevCfOp)) {
1216       /* In case a Cond has been optimized we would get right to the start block
1217          with an invalid definition. */
1218       nin[i-1] = new_Bad();
1219       continue;
1220     }
1221     prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */
1222     assert (prevBlock);
1223     if (!is_Bad(prevBlock)) {
1224 #if PRECISE_EXC_CONTEXT
1225       if (is_fragile_op(prevCfOp) && (get_irn_op (prevCfOp) != op_Bad)) {
1226         assert(get_r_frag_value_internal (prevBlock, prevCfOp, pos, mode));
1227         nin[i-1] = get_r_frag_value_internal (prevBlock, prevCfOp, pos, mode);
1228       } else
1229 #endif
1230         nin[i-1] = get_r_value_internal (prevBlock, pos, mode);
1231     } else {
1232       nin[i-1] = new_Bad();
1233     }
1234   }
1235
1236   /* After collecting all predecessors into the array nin a new Phi node
1237      with these predecessors is created.  This constructor contains an
1238      optimization: If all predecessors of the Phi node are identical it
1239      returns the only operand instead of a new Phi node.  */
1240   res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins);
1241
1242   /* In case we allocated a Phi0 node at the beginning of this procedure,
1243      we need to exchange this Phi0 with the real Phi. */
1244   if (phi0) {
1245     exchange(phi0, res);
1246     block->attr.block.graph_arr[pos] = res;
1247     /* Don't set_frag_value as it does not overwrite.  Doesn't matter, is
1248        only an optimization. */
1249   }
1250
1251   return res;
1252 }
1253
1254 /* This function returns the last definition of a variable.  In case
1255    this variable was last defined in a previous block, Phi nodes are
1256    inserted.  If the part of the firm graph containing the definition
1257    is not yet constructed, a dummy Phi node is returned. */
1258 inline ir_node *
1259 get_r_value_internal (ir_node *block, int pos, ir_mode *mode)
1260 {
1261   ir_node *res;
1262   /* There are 4 cases to treat.
1263
1264      1. The block is not mature and we visit it the first time.  We can not
1265         create a proper Phi node, therefore a Phi0, i.e., a Phi without
1266         predecessors is returned.  This node is added to the linked list (field
1267         "link") of the containing block to be completed when this block is
1268         matured. (Comlpletion will add a new Phi and turn the Phi0 into an Id
1269         node.)
1270
1271      2. The value is already known in this block, graph_arr[pos] is set and we
1272         visit the block the first time.  We can return the value without
1273         creating any new nodes.
1274
1275      3. The block is mature and we visit it the first time.  A Phi node needs
1276         to be created (phi_merge).  If the Phi is not needed, as all it's
1277         operands are the same value reaching the block through different
1278         paths, it's optimized away and the value itself is returned.
1279
1280      4. The block is mature, and we visit it the second time.  Now two
1281         subcases are possible:
1282         * The value was computed completely the last time we were here. This
1283           is the case if there is no loop.  We can return the proper value.
1284         * The recursion that visited this node and set the flag did not
1285           return yet.  We are computing a value in a loop and need to
1286           break the recursion.  This case only happens if we visited
1287           the same block with phi_merge before, which inserted a Phi0.
1288           So we return the Phi0.
1289   */
1290
1291   /* case 4 -- already visited. */
1292   if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) {
1293     /* As phi_merge allocates a Phi0 this value is always defined. Here
1294      is the critical difference of the two algorithms. */
1295     assert(block->attr.block.graph_arr[pos]);
1296     return block->attr.block.graph_arr[pos];
1297   }
1298
1299   /* visited the first time */
1300   set_irn_visited(block, get_irg_visited(current_ir_graph));
1301
1302   /* Get the local valid value */
1303   res = block->attr.block.graph_arr[pos];
1304
1305   /* case 2 -- If the value is actually computed, return it. */
1306   if (res) { return res; };
1307
1308   if (block->attr.block.matured) { /* case 3 */
1309
1310     /* The Phi has the same amount of ins as the corresponding block. */
1311     int ins = get_irn_arity(block);
1312     ir_node **nin;
1313     NEW_ARR_A (ir_node *, nin, ins);
1314
1315     /* Phi merge collects the predecessors and then creates a node. */
1316     res = phi_merge (block, pos, mode, nin, ins);
1317
1318   } else {  /* case 1 */
1319     /* The block is not mature, we don't know how many in's are needed.  A Phi
1320        with zero predecessors is created.  Such a Phi node is called Phi0
1321        node.  The Phi0 is then added to the list of Phi0 nodes in this block
1322        to be matured by mature_block later.
1323        The Phi0 has to remember the pos of it's internal value.  If the real
1324        Phi is computed, pos is used to update the array with the local
1325        values. */
1326     res = new_r_Phi0 (current_ir_graph, block, mode);
1327     res->attr.phi0_pos = pos;
1328     res->link = block->link;
1329     block->link = res;
1330   }
1331
1332   /* If we get here, the frontend missed a use-before-definition error */
1333   if (!res) {
1334     /* Error Message */
1335     printf("Error: no value set.  Use of undefined variable.  Initializing
1336             to zero.\n");
1337     assert (mode->code >= irm_f && mode->code <= irm_p);
1338     res = new_r_Const (current_ir_graph, block, mode,
1339                        tarval_mode_null[mode->code]);
1340   }
1341
1342   /* The local valid value is available now. */
1343   block->attr.block.graph_arr[pos] = res;
1344
1345   return res;
1346 }
1347
1348 #endif /* USE_FAST_PHI_CONSTRUCTION */
1349
1350 /* ************************************************************************** */
1351
1352 /** Finalize a Block node, when all control flows are known.  */
1353 /** Acceptable parameters are only Block nodes.               */
1354 void
1355 mature_block (ir_node *block)
1356 {
1357
1358   int ins;
1359   ir_node *n, **nin;
1360   ir_node *next;
1361
1362   assert (get_irn_opcode(block) == iro_Block);
1363   // assert (!get_Block_matured(block) && "Block already matured");
1364
1365   if (!get_Block_matured(block)) {
1366
1367     /* An array for building the Phi nodes. */
1368     ins = ARR_LEN (block->in)-1;
1369     NEW_ARR_A (ir_node *, nin, ins);
1370     /* shouldn't we delete this array at the end of the procedure? @@@ memory leak? */
1371
1372     /* Traverse a chain of Phi nodes attached to this block and mature
1373        these, too. **/
1374     for (n = block->link;  n;  n=next) {
1375       inc_irg_visited(current_ir_graph);
1376       next = n->link;
1377       exchange (n, phi_merge (block, n->attr.phi0_pos, n->mode, nin, ins));
1378     }
1379
1380     block->attr.block.matured = 1;
1381
1382     /* Now, as the block is a finished firm node, we can optimize it.
1383        Since other nodes have been allocated since the block was created
1384        we can not free the node on the obstack.  Therefore we have to call
1385        optimize_in_place.
1386        Unfortunately the optimization does not change a lot, as all allocated
1387        nodes refer to the unoptimized node.
1388        We can call _2, as global cse has no effect on blocks. */
1389     block = optimize_in_place_2(block);
1390     irn_vrfy(block);
1391   }
1392 }
1393
1394 ir_node *
1395 new_Phi (int arity, ir_node **in, ir_mode *mode)
1396 {
1397   return new_r_Phi (current_ir_graph, current_ir_graph->current_block,
1398                     arity, in, mode);
1399 }
1400
1401 ir_node *
1402 new_Const (ir_mode *mode, tarval *con)
1403 {
1404   return new_r_Const (current_ir_graph, current_ir_graph->start_block,
1405                       mode, con);
1406 }
1407
1408 ir_node *
1409 new_Id (ir_node *val, ir_mode *mode)
1410 {
1411   return new_r_Id (current_ir_graph, current_ir_graph->current_block,
1412                    val, mode);
1413 }
1414
1415 ir_node *
1416 new_Proj (ir_node *arg, ir_mode *mode, long proj)
1417 {
1418   return new_r_Proj (current_ir_graph, current_ir_graph->current_block,
1419                      arg, mode, proj);
1420 }
1421
1422 ir_node *
1423 new_defaultProj (ir_node *arg, long max_proj)
1424 {
1425   ir_node *res;
1426   assert((arg->op==op_Cond) && (get_irn_mode(arg->in[1]) == mode_I));
1427   arg->attr.c.kind = fragmentary;
1428   arg->attr.c.default_proj = max_proj;
1429   res = new_Proj (arg, mode_X, max_proj);
1430   return res;
1431 }
1432
1433 ir_node *
1434 new_Conv (ir_node *op, ir_mode *mode)
1435 {
1436   return new_r_Conv (current_ir_graph, current_ir_graph->current_block,
1437                      op, mode);
1438 }
1439
1440 ir_node *
1441 new_Tuple (int arity, ir_node **in)
1442 {
1443   return new_r_Tuple (current_ir_graph, current_ir_graph->current_block,
1444                       arity, in);
1445 }
1446
1447 ir_node *
1448 new_Add (ir_node *op1, ir_node *op2, ir_mode *mode)
1449 {
1450   return new_r_Add (current_ir_graph, current_ir_graph->current_block,
1451                     op1, op2, mode);
1452 }
1453
1454 ir_node *
1455 new_Sub (ir_node *op1, ir_node *op2, ir_mode *mode)
1456 {
1457   return new_r_Sub (current_ir_graph, current_ir_graph->current_block,
1458                     op1, op2, mode);
1459 }
1460
1461
1462 ir_node *
1463 new_Minus  (ir_node *op,  ir_mode *mode)
1464 {
1465   return new_r_Minus (current_ir_graph, current_ir_graph->current_block,
1466                       op, mode);
1467 }
1468
1469 ir_node *
1470 new_Mul (ir_node *op1, ir_node *op2, ir_mode *mode)
1471 {
1472   return new_r_Mul (current_ir_graph, current_ir_graph->current_block,
1473                     op1, op2, mode);
1474 }
1475
1476 ir_node *
1477 new_Quot (ir_node *memop, ir_node *op1, ir_node *op2)
1478 {
1479   ir_node *res;
1480   res = new_r_Quot (current_ir_graph, current_ir_graph->current_block,
1481                      memop, op1, op2);
1482 #if PRECISE_EXC_CONTEXT
1483   if (current_ir_graph->phase_state == phase_building)
1484     res->attr.frag_arr = new_frag_arr(res);
1485 #endif
1486
1487   return res;
1488 }
1489
1490 ir_node *
1491 new_DivMod (ir_node *memop, ir_node *op1, ir_node *op2)
1492 {
1493   ir_node *res;
1494   res = new_r_DivMod (current_ir_graph, current_ir_graph->current_block,
1495                        memop, op1, op2);
1496 #if PRECISE_EXC_CONTEXT
1497   if (current_ir_graph->phase_state == phase_building)
1498     res->attr.frag_arr = new_frag_arr(res);
1499 #endif
1500
1501   return res;
1502 }
1503
1504 ir_node *
1505 new_Div (ir_node *memop, ir_node *op1, ir_node *op2)
1506 {
1507   ir_node *res;
1508   res = new_r_Div (current_ir_graph, current_ir_graph->current_block,
1509                     memop, op1, op2);
1510 #if PRECISE_EXC_CONTEXT
1511   if (current_ir_graph->phase_state == phase_building)
1512     res->attr.frag_arr = new_frag_arr(res);
1513 #endif
1514
1515   return res;
1516 }
1517
1518 ir_node *
1519 new_Mod (ir_node *memop, ir_node *op1, ir_node *op2)
1520 {
1521   ir_node *res;
1522   res = new_r_Mod (current_ir_graph, current_ir_graph->current_block,
1523                     memop, op1, op2);
1524 #if PRECISE_EXC_CONTEXT
1525   if (current_ir_graph->phase_state == phase_building)
1526     res->attr.frag_arr = new_frag_arr(res);
1527 #endif
1528
1529   return res;
1530 }
1531
1532 ir_node *
1533 new_And (ir_node *op1, ir_node *op2, ir_mode *mode)
1534 {
1535   return new_r_And (current_ir_graph, current_ir_graph->current_block,
1536                     op1, op2, mode);
1537 }
1538
1539 ir_node *
1540 new_Or (ir_node *op1, ir_node *op2, ir_mode *mode)
1541 {
1542   return new_r_Or (current_ir_graph, current_ir_graph->current_block,
1543                    op1, op2, mode);
1544 }
1545
1546 ir_node *
1547 new_Eor (ir_node *op1, ir_node *op2, ir_mode *mode)
1548 {
1549   return new_r_Eor (current_ir_graph, current_ir_graph->current_block,
1550                     op1, op2, mode);
1551 }
1552
1553 ir_node *
1554 new_Not (ir_node *op, ir_mode *mode)
1555 {
1556   return new_r_Not (current_ir_graph, current_ir_graph->current_block,
1557                     op, mode);
1558 }
1559
1560 ir_node *
1561 new_Shl (ir_node *op, ir_node *k, ir_mode *mode)
1562 {
1563   return new_r_Shl (current_ir_graph, current_ir_graph->current_block,
1564                     op, k, mode);
1565 }
1566
1567 ir_node *
1568 new_Shr (ir_node *op, ir_node *k, ir_mode *mode)
1569 {
1570   return new_r_Shr (current_ir_graph, current_ir_graph->current_block,
1571                     op, k, mode);
1572 }
1573
1574 ir_node *
1575 new_Shrs (ir_node *op, ir_node *k, ir_mode *mode)
1576 {
1577   return new_r_Shrs (current_ir_graph, current_ir_graph->current_block,
1578                      op, k, mode);
1579 }
1580
1581 ir_node *
1582 new_Rotate (ir_node *op, ir_node *k, ir_mode *mode)
1583 {
1584   return new_r_Rot (current_ir_graph, current_ir_graph->current_block,
1585                      op, k, mode);
1586 }
1587
1588 ir_node *
1589 new_Abs (ir_node *op, ir_mode *mode)
1590 {
1591   return new_r_Abs (current_ir_graph, current_ir_graph->current_block,
1592                     op, mode);
1593 }
1594
1595 ir_node *
1596 new_Cmp (ir_node *op1, ir_node *op2)
1597 {
1598   return new_r_Cmp (current_ir_graph, current_ir_graph->current_block,
1599                     op1, op2);
1600 }
1601
1602 ir_node *
1603 new_Jmp (void)
1604 {
1605   return new_r_Jmp (current_ir_graph, current_ir_graph->current_block);
1606 }
1607
1608 ir_node *
1609 new_Cond (ir_node *c)
1610 {
1611   return new_r_Cond (current_ir_graph, current_ir_graph->current_block, c);
1612 }
1613
1614 ir_node *
1615 new_Call (ir_node *store, ir_node *callee, int arity, ir_node **in,
1616           type *type)
1617 {
1618   ir_node *res;
1619   res = new_r_Call (current_ir_graph, current_ir_graph->current_block,
1620                      store, callee, arity, in, type);
1621 #if PRECISE_EXC_CONTEXT
1622   if (current_ir_graph->phase_state == phase_building)
1623     res->attr.call.frag_arr = new_frag_arr(res);
1624 #endif
1625
1626   return res;
1627 }
1628
1629 ir_node *
1630 new_Return (ir_node* store, int arity, ir_node **in)
1631 {
1632   return new_r_Return (current_ir_graph, current_ir_graph->current_block,
1633                        store, arity, in);
1634 }
1635
1636 ir_node *
1637 new_Raise (ir_node *store, ir_node *obj)
1638 {
1639   return new_r_Raise (current_ir_graph, current_ir_graph->current_block,
1640                       store, obj);
1641 }
1642
1643 ir_node *
1644 new_Load (ir_node *store, ir_node *addr)
1645 {
1646   ir_node *res;
1647   res = new_r_Load (current_ir_graph, current_ir_graph->current_block,
1648                      store, addr);
1649 #if PRECISE_EXC_CONTEXT
1650   if (current_ir_graph->phase_state == phase_building)
1651     res->attr.frag_arr = new_frag_arr(res);
1652 #endif
1653
1654   return res;
1655 }
1656
1657 ir_node *
1658 new_Store (ir_node *store, ir_node *addr, ir_node *val)
1659 {
1660   ir_node *res;
1661   res = new_r_Store (current_ir_graph, current_ir_graph->current_block,
1662                       store, addr, val);
1663 #if PRECISE_EXC_CONTEXT
1664   if (current_ir_graph->phase_state == phase_building)
1665     res->attr.frag_arr = new_frag_arr(res);
1666 #endif
1667
1668   return res;
1669 }
1670
1671 ir_node *
1672 new_Alloc (ir_node *store, ir_node *size, type *alloc_type,
1673            where_alloc where)
1674 {
1675   ir_node *res;
1676   res = new_r_Alloc (current_ir_graph, current_ir_graph->current_block,
1677                       store, size, alloc_type, where);
1678 #if PRECISE_EXC_CONTEXT
1679   if (current_ir_graph->phase_state == phase_building)
1680     res->attr.a.frag_arr = new_frag_arr(res);
1681 #endif
1682
1683   return res;
1684 }
1685
1686 ir_node *
1687 new_Free (ir_node *store, ir_node *ptr, ir_node *size, type *free_type)
1688 {
1689   return new_r_Free (current_ir_graph, current_ir_graph->current_block,
1690                      store, ptr, size, free_type);
1691 }
1692
1693 ir_node *
1694 new_simpleSel (ir_node *store, ir_node *objptr, entity *ent)
1695 /* GL: objptr was called frame before.  Frame was a bad choice for the name
1696    as the operand could as well be a pointer to a dynamic object. */
1697 {
1698   return new_r_Sel (current_ir_graph, current_ir_graph->current_block,
1699                     store, objptr, 0, NULL, ent);
1700 }
1701
1702 ir_node *
1703 new_Sel (ir_node *store, ir_node *objptr, int n_index, ir_node **index, entity *sel)
1704 {
1705   return new_r_Sel (current_ir_graph, current_ir_graph->current_block,
1706                     store, objptr, n_index, index, sel);
1707 }
1708
1709 ir_node *
1710 new_SymConst (type_or_id_p value, symconst_kind kind)
1711 {
1712   return new_r_SymConst (current_ir_graph, current_ir_graph->current_block,
1713                          value, kind);
1714 }
1715
1716 ir_node *
1717 new_Sync (int arity, ir_node** in)
1718 {
1719   return new_r_Sync (current_ir_graph, current_ir_graph->current_block,
1720                      arity, in);
1721 }
1722
1723
1724 ir_node *
1725 new_Bad (void)
1726 {
1727   return current_ir_graph->bad;
1728 }
1729
1730 /* ********************************************************************* */
1731 /* Comfortable interface with automatic Phi node construction.           */
1732 /* (Uses also constructors of ?? interface, except new_Block.            */
1733 /* ********************************************************************* */
1734
1735 /** Block construction **/
1736 /* immature Block without predecessors */
1737 ir_node *new_immBlock (void) {
1738   ir_node *res;
1739
1740   assert(get_irg_phase_state (current_ir_graph) == phase_building);
1741   /* creates a new dynamic in-array as length of in is -1 */
1742   res = new_ir_node (current_ir_graph, NULL, op_Block, mode_R, -1, NULL);
1743   current_ir_graph->current_block = res;
1744   res->attr.block.matured = 0;
1745   set_Block_block_visited(res, 0);
1746
1747   /* Create and initialize array for Phi-node construction. */
1748   res->attr.block.graph_arr = NEW_ARR_D (ir_node *, current_ir_graph->obst,
1749                                          current_ir_graph->n_loc);
1750   memset(res->attr.block.graph_arr, 0, sizeof(ir_node *)*current_ir_graph->n_loc);
1751
1752   /* Immature block may not be optimized! */
1753   irn_vrfy (res);
1754
1755   return res;
1756 }
1757
1758 /* add an adge to a jmp/control flow node */
1759 void
1760 add_in_edge (ir_node *block, ir_node *jmp)
1761 {
1762   if (block->attr.block.matured) {
1763     assert(0 && "Error: Block already matured!\n");
1764   }
1765   else {
1766     assert (jmp != NULL);
1767     ARR_APP1 (ir_node *, block->in, jmp);
1768   }
1769 }
1770
1771 /* changing the current block */
1772 void
1773 switch_block (ir_node *target)
1774 {
1775   current_ir_graph->current_block = target;
1776 }
1777
1778 /* ************************ */
1779 /* parameter administration */
1780
1781 /* get a value from the parameter array from the current block by its index */
1782 ir_node *
1783 get_value (int pos, ir_mode *mode)
1784 {
1785   assert(get_irg_phase_state (current_ir_graph) == phase_building);
1786   inc_irg_visited(current_ir_graph);
1787   return get_r_value_internal (current_ir_graph->current_block, pos + 1, mode);
1788 }
1789
1790
1791 /* set a value at position pos in the parameter array from the current block */
1792 inline void
1793 set_value (int pos, ir_node *value)
1794 {
1795   assert(get_irg_phase_state (current_ir_graph) == phase_building);
1796   current_ir_graph->current_block->attr.block.graph_arr[pos + 1] = value;
1797 }
1798
1799 /* get the current store */
1800 inline ir_node *
1801 get_store (void)
1802 {
1803   assert(get_irg_phase_state (current_ir_graph) == phase_building);
1804   /* GL: one could call get_value instead */
1805   inc_irg_visited(current_ir_graph);
1806   return get_r_value_internal (current_ir_graph->current_block, 0, mode_M);
1807 }
1808
1809 /* set the current store */
1810 inline void
1811 set_store (ir_node *store)
1812 {
1813   assert(get_irg_phase_state (current_ir_graph) == phase_building);
1814   /* GL: one could call set_value instead */
1815   current_ir_graph->current_block->attr.block.graph_arr[0] = store;
1816 }
1817
1818 inline void
1819 keep_alive (ir_node *ka)
1820 {
1821   add_End_keepalive(current_ir_graph->end, ka);
1822 }
1823
1824 /** Useful access routines **/
1825 /* Returns the current block of the current graph.  To set the current
1826    block use switch_block(). */
1827 ir_node *get_cur_block() {
1828   return get_irg_current_block(current_ir_graph);
1829 }
1830
1831 /* Returns the frame type of the current graph */
1832 type *get_cur_frame_type() {
1833   return get_irg_frame_type(current_ir_graph);
1834 }
1835
1836
1837 /* ********************************************************************* */
1838 /* initialize */
1839
1840 /* call once for each run of the library */
1841 void
1842 init_cons (void)
1843 {
1844 }
1845
1846 /* call for each graph */
1847 void
1848 finalize_cons (ir_graph *irg) {
1849   irg->phase_state = phase_high;
1850 }