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 ir_node **
1092 new_frag_arr (ir_node *n) {
1093   ir_node **arr;
1094   int opt;
1095   arr = NEW_ARR_D (ir_node *, current_ir_graph->obst, current_ir_graph->n_loc);
1096   memcpy(arr, current_ir_graph->current_block->attr.block.graph_arr,
1097          sizeof(ir_node *)*current_ir_graph->n_loc);
1098   /* turn off optimization before allocating Proj nodes, as res isn't
1099      finished yet. */
1100   opt = get_optimize(); set_optimize(0);
1101   /* Here we rely on the fact that all frag ops have Memory as first result! */
1102   if (get_irn_op(n) == op_Call)
1103     arr[0] = new_Proj(n, mode_M, 3);
1104   else
1105     arr[0] = new_Proj(n, mode_M, 0);
1106   set_optimize(opt);
1107   current_ir_graph->current_block->attr.block.graph_arr[current_ir_graph->n_loc-1] = n;
1108   return arr;
1109 }
1110
1111 inline ir_node **
1112 get_frag_arr (ir_node *n) {
1113   if (get_irn_op(n) == op_Call) {
1114     return n->attr.call.frag_arr;
1115   } else if (get_irn_op(n) == op_Alloc) {
1116     return n->attr.a.frag_arr;
1117   } else {
1118     return n->attr.frag_arr;
1119   }
1120 }
1121
1122 inline ir_node *
1123 set_frag_value(ir_node **frag_arr, int pos, ir_node *val) {
1124   if (!frag_arr[pos]) frag_arr[pos] = val;
1125   if (frag_arr[current_ir_graph->n_loc - 1])
1126     set_frag_value (get_frag_arr(frag_arr[current_ir_graph->n_loc - 1]), pos, val);
1127 }
1128
1129 inline ir_node *
1130 get_r_frag_value_internal (ir_node *block, ir_node *cfOp, int pos, ir_mode *mode) {
1131   ir_node *res;
1132   ir_node **rem;
1133   ir_node **frag_arr;
1134
1135   assert(is_fragile_op(cfOp) && (get_irn_op(cfOp) != op_Bad));
1136
1137   frag_arr = get_frag_arr(cfOp);
1138   res = frag_arr[pos];
1139   if (!res) {
1140     if (block->attr.block.graph_arr[pos]) {
1141       /* There was a set_value after the cfOp and no get_value before that
1142          set_value.  We must build a Phi node now. */
1143       if (block->attr.block.matured) {
1144         int ins = get_irn_arity(block);
1145         ir_node **nin;
1146         NEW_ARR_A (ir_node *, nin, ins);
1147         res = phi_merge(block, pos, mode, nin, ins);
1148       } else {
1149         res = new_r_Phi0 (current_ir_graph, block, mode);
1150         res->attr.phi0_pos = pos;
1151         res->link = block->link;
1152         block->link = res;
1153       }
1154       assert(res);
1155       /* @@@ tested by Flo: set_frag_value(frag_arr, pos, res);
1156          but this should be better: (remove comment if this works) */
1157       /* It's a Phi, we can write this into all graph_arrs with NULL */
1158       set_frag_value(block->attr.block.graph_arr, pos, res);
1159     } else {
1160       res = get_r_value_internal(block, pos, mode);
1161       set_frag_value(block->attr.block.graph_arr, pos, res);
1162     }
1163   }
1164   return res;
1165 }
1166 #endif
1167
1168 /** This function allocates a dummy Phi node to break recursions,
1169     computes the predecessors for the real phi node, and then
1170     allocates and returns this node.  The routine called to allocate the
1171     node might optimize it away and return a real value.
1172     This function is called with an in-array of proper size. **/
1173 static inline ir_node *
1174 phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
1175 {
1176   ir_node *prevBlock, *prevCfOp, *res, *phi0;
1177   int i;
1178
1179   /* If this block has no value at pos create a Phi0 and remember it
1180      in graph_arr to break recursions.
1181      Else we may not set graph_arr as there a later value is remembered. */
1182   phi0 = NULL;
1183   if (!block->attr.block.graph_arr[pos]) {
1184     /* This is commented out as collapsing to Bads is no good idea.
1185        Either we need an assert here, or we need to call a routine
1186        that deals with this case as appropriate for the given language.
1187        Right now a self referencing Id is created which will crash irg_vrfy().
1188
1189        Even if all variables are defined before use, it can happen that
1190        we get to the start block, if a cond has been replaced by a tuple
1191        (bad, jmp).  As the start has a self referencing control flow edge,
1192        we get a self referencing Id, which is hard to optimize away.  We avoid
1193        this by defining the value as a Bad node.
1194        Returning a const with tarval_bad is a preliminary solution.  In some
1195        situations we might want a Warning or an Error. */
1196
1197     if (block == get_irg_start_block(current_ir_graph)) {
1198       block->attr.block.graph_arr[pos] = new_Const(mode, tarval_bad);
1199       /* We don't need to care about exception ops in the start block.
1200          There are none by definition. */
1201       return block->attr.block.graph_arr[pos];
1202     } else {
1203       phi0 = new_r_Phi0(current_ir_graph, block, mode);
1204       block->attr.block.graph_arr[pos] = phi0;
1205 #if PRECISE_EXC_CONTEXT
1206       /* Set graph_arr for fragile ops.  Also here we should break recursion.
1207          We could choose a cyclic path through an cfop.  But the recursion would
1208          break at some point. */
1209       set_frag_value(block->attr.block.graph_arr, pos, phi0);
1210 #endif
1211     }
1212   }
1213
1214   /* This loop goes to all predecessor blocks of the block the Phi node
1215      is in and there finds the operands of the Phi node by calling
1216      get_r_value_internal.  */
1217   for (i = 1;  i <= ins;  ++i) {
1218     prevCfOp = skip_Proj(block->in[i]);
1219     assert (prevCfOp);
1220     if (is_Bad(prevCfOp)) {
1221       /* In case a Cond has been optimized we would get right to the start block
1222          with an invalid definition. */
1223       nin[i-1] = new_Bad();
1224       continue;
1225     }
1226     prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */
1227     assert (prevBlock);
1228     if (!is_Bad(prevBlock)) {
1229 #if PRECISE_EXC_CONTEXT
1230       if (is_fragile_op(prevCfOp) && (get_irn_op (prevCfOp) != op_Bad)) {
1231         assert(get_r_frag_value_internal (prevBlock, prevCfOp, pos, mode));
1232         nin[i-1] = get_r_frag_value_internal (prevBlock, prevCfOp, pos, mode);
1233       } else
1234 #endif
1235         nin[i-1] = get_r_value_internal (prevBlock, pos, mode);
1236     } else {
1237       nin[i-1] = new_Bad();
1238     }
1239   }
1240
1241   /* After collecting all predecessors into the array nin a new Phi node
1242      with these predecessors is created.  This constructor contains an
1243      optimization: If all predecessors of the Phi node are identical it
1244      returns the only operand instead of a new Phi node.  */
1245   res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins);
1246
1247   /* In case we allocated a Phi0 node at the beginning of this procedure,
1248      we need to exchange this Phi0 with the real Phi. */
1249   if (phi0) {
1250     exchange(phi0, res);
1251     block->attr.block.graph_arr[pos] = res;
1252     /* Don't set_frag_value as it does not overwrite.  Doesn't matter, is
1253        only an optimization. */
1254   }
1255
1256   return res;
1257 }
1258
1259 /* This function returns the last definition of a variable.  In case
1260    this variable was last defined in a previous block, Phi nodes are
1261    inserted.  If the part of the firm graph containing the definition
1262    is not yet constructed, a dummy Phi node is returned. */
1263 inline ir_node *
1264 get_r_value_internal (ir_node *block, int pos, ir_mode *mode)
1265 {
1266   ir_node *res;
1267   /* There are 4 cases to treat.
1268
1269      1. The block is not mature and we visit it the first time.  We can not
1270         create a proper Phi node, therefore a Phi0, i.e., a Phi without
1271         predecessors is returned.  This node is added to the linked list (field
1272         "link") of the containing block to be completed when this block is
1273         matured. (Comlpletion will add a new Phi and turn the Phi0 into an Id
1274         node.)
1275
1276      2. The value is already known in this block, graph_arr[pos] is set and we
1277         visit the block the first time.  We can return the value without
1278         creating any new nodes.
1279
1280      3. The block is mature and we visit it the first time.  A Phi node needs
1281         to be created (phi_merge).  If the Phi is not needed, as all it's
1282         operands are the same value reaching the block through different
1283         paths, it's optimized away and the value itself is returned.
1284
1285      4. The block is mature, and we visit it the second time.  Now two
1286         subcases are possible:
1287         * The value was computed completely the last time we were here. This
1288           is the case if there is no loop.  We can return the proper value.
1289         * The recursion that visited this node and set the flag did not
1290           return yet.  We are computing a value in a loop and need to
1291           break the recursion.  This case only happens if we visited
1292           the same block with phi_merge before, which inserted a Phi0.
1293           So we return the Phi0.
1294   */
1295
1296   /* case 4 -- already visited. */
1297   if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) {
1298     /* As phi_merge allocates a Phi0 this value is always defined. Here
1299      is the critical difference of the two algorithms. */
1300     assert(block->attr.block.graph_arr[pos]);
1301     return block->attr.block.graph_arr[pos];
1302   }
1303
1304   /* visited the first time */
1305   set_irn_visited(block, get_irg_visited(current_ir_graph));
1306
1307   /* Get the local valid value */
1308   res = block->attr.block.graph_arr[pos];
1309
1310   /* case 2 -- If the value is actually computed, return it. */
1311   if (res) { return res; };
1312
1313   if (block->attr.block.matured) { /* case 3 */
1314
1315     /* The Phi has the same amount of ins as the corresponding block. */
1316     int ins = get_irn_arity(block);
1317     ir_node **nin;
1318     NEW_ARR_A (ir_node *, nin, ins);
1319
1320     /* Phi merge collects the predecessors and then creates a node. */
1321     res = phi_merge (block, pos, mode, nin, ins);
1322
1323   } else {  /* case 1 */
1324     /* The block is not mature, we don't know how many in's are needed.  A Phi
1325        with zero predecessors is created.  Such a Phi node is called Phi0
1326        node.  The Phi0 is then added to the list of Phi0 nodes in this block
1327        to be matured by mature_block later.
1328        The Phi0 has to remember the pos of it's internal value.  If the real
1329        Phi is computed, pos is used to update the array with the local
1330        values. */
1331     res = new_r_Phi0 (current_ir_graph, block, mode);
1332     res->attr.phi0_pos = pos;
1333     res->link = block->link;
1334     block->link = res;
1335   }
1336
1337   /* If we get here, the frontend missed a use-before-definition error */
1338   if (!res) {
1339     /* Error Message */
1340     printf("Error: no value set.  Use of undefined variable.  Initializing
1341             to zero.\n");
1342     assert (mode->code >= irm_f && mode->code <= irm_p);
1343     res = new_r_Const (current_ir_graph, block, mode,
1344                        tarval_mode_null[mode->code]);
1345   }
1346
1347   /* The local valid value is available now. */
1348   block->attr.block.graph_arr[pos] = res;
1349
1350   return res;
1351 }
1352
1353 #endif /* USE_FAST_PHI_CONSTRUCTION */
1354
1355 /* ************************************************************************** */
1356
1357 /** Finalize a Block node, when all control flows are known.  */
1358 /** Acceptable parameters are only Block nodes.               */
1359 void
1360 mature_block (ir_node *block)
1361 {
1362
1363   int ins;
1364   ir_node *n, **nin;
1365   ir_node *next;
1366
1367   assert (get_irn_opcode(block) == iro_Block);
1368   // assert (!get_Block_matured(block) && "Block already matured");
1369
1370   if (!get_Block_matured(block)) {
1371
1372     /* An array for building the Phi nodes. */
1373     ins = ARR_LEN (block->in)-1;
1374     NEW_ARR_A (ir_node *, nin, ins);
1375     /* shouldn't we delete this array at the end of the procedure? @@@ memory leak? */
1376
1377     /* Traverse a chain of Phi nodes attached to this block and mature
1378        these, too. **/
1379     for (n = block->link;  n;  n=next) {
1380       inc_irg_visited(current_ir_graph);
1381       next = n->link;
1382       exchange (n, phi_merge (block, n->attr.phi0_pos, n->mode, nin, ins));
1383     }
1384
1385     block->attr.block.matured = 1;
1386
1387     /* Now, as the block is a finished firm node, we can optimize it.
1388        Since other nodes have been allocated since the block was created
1389        we can not free the node on the obstack.  Therefore we have to call
1390        optimize_in_place.
1391        Unfortunately the optimization does not change a lot, as all allocated
1392        nodes refer to the unoptimized node.
1393        We can call _2, as global cse has no effect on blocks. */
1394     block = optimize_in_place_2(block);
1395     irn_vrfy(block);
1396   }
1397 }
1398
1399 ir_node *
1400 new_Phi (int arity, ir_node **in, ir_mode *mode)
1401 {
1402   return new_r_Phi (current_ir_graph, current_ir_graph->current_block,
1403                     arity, in, mode);
1404 }
1405
1406 ir_node *
1407 new_Const (ir_mode *mode, tarval *con)
1408 {
1409   return new_r_Const (current_ir_graph, current_ir_graph->start_block,
1410                       mode, con);
1411 }
1412
1413 ir_node *
1414 new_Id (ir_node *val, ir_mode *mode)
1415 {
1416   return new_r_Id (current_ir_graph, current_ir_graph->current_block,
1417                    val, mode);
1418 }
1419
1420 ir_node *
1421 new_Proj (ir_node *arg, ir_mode *mode, long proj)
1422 {
1423   return new_r_Proj (current_ir_graph, current_ir_graph->current_block,
1424                      arg, mode, proj);
1425 }
1426
1427 ir_node *
1428 new_defaultProj (ir_node *arg, long max_proj)
1429 {
1430   ir_node *res;
1431   assert((arg->op==op_Cond) && (get_irn_mode(arg->in[1]) == mode_I));
1432   arg->attr.c.kind = fragmentary;
1433   arg->attr.c.default_proj = max_proj;
1434   res = new_Proj (arg, mode_X, max_proj);
1435   return res;
1436 }
1437
1438 ir_node *
1439 new_Conv (ir_node *op, ir_mode *mode)
1440 {
1441   return new_r_Conv (current_ir_graph, current_ir_graph->current_block,
1442                      op, mode);
1443 }
1444
1445 ir_node *
1446 new_Tuple (int arity, ir_node **in)
1447 {
1448   return new_r_Tuple (current_ir_graph, current_ir_graph->current_block,
1449                       arity, in);
1450 }
1451
1452 ir_node *
1453 new_Add (ir_node *op1, ir_node *op2, ir_mode *mode)
1454 {
1455   return new_r_Add (current_ir_graph, current_ir_graph->current_block,
1456                     op1, op2, mode);
1457 }
1458
1459 ir_node *
1460 new_Sub (ir_node *op1, ir_node *op2, ir_mode *mode)
1461 {
1462   return new_r_Sub (current_ir_graph, current_ir_graph->current_block,
1463                     op1, op2, mode);
1464 }
1465
1466
1467 ir_node *
1468 new_Minus  (ir_node *op,  ir_mode *mode)
1469 {
1470   return new_r_Minus (current_ir_graph, current_ir_graph->current_block,
1471                       op, mode);
1472 }
1473
1474 ir_node *
1475 new_Mul (ir_node *op1, ir_node *op2, ir_mode *mode)
1476 {
1477   return new_r_Mul (current_ir_graph, current_ir_graph->current_block,
1478                     op1, op2, mode);
1479 }
1480
1481 ir_node *
1482 new_Quot (ir_node *memop, ir_node *op1, ir_node *op2)
1483 {
1484   ir_node *res;
1485   res = new_r_Quot (current_ir_graph, current_ir_graph->current_block,
1486                      memop, op1, op2);
1487 #if PRECISE_EXC_CONTEXT
1488   if ((current_ir_graph->phase_state == phase_building) &&
1489       (get_irn_op(res) == op_Quot))  /* Could be optimized away. */
1490     res->attr.frag_arr = new_frag_arr(res);
1491 #endif
1492
1493   return res;
1494 }
1495
1496 ir_node *
1497 new_DivMod (ir_node *memop, ir_node *op1, ir_node *op2)
1498 {
1499   ir_node *res;
1500   res = new_r_DivMod (current_ir_graph, current_ir_graph->current_block,
1501                        memop, op1, op2);
1502 #if PRECISE_EXC_CONTEXT
1503   if ((current_ir_graph->phase_state == phase_building) &&
1504       (get_irn_op(res) == op_DivMod))   /* Could be optimized away. */
1505     res->attr.frag_arr = new_frag_arr(res);
1506 #endif
1507
1508   return res;
1509 }
1510
1511 ir_node *
1512 new_Div (ir_node *memop, ir_node *op1, ir_node *op2)
1513 {
1514   ir_node *res;
1515   res = new_r_Div (current_ir_graph, current_ir_graph->current_block,
1516                     memop, op1, op2);
1517 #if PRECISE_EXC_CONTEXT
1518   if ((current_ir_graph->phase_state == phase_building) &&
1519       (get_irn_op(res) == op_Div))  /* Could be optimized away. */
1520     res->attr.frag_arr = new_frag_arr(res);
1521 #endif
1522
1523   return res;
1524 }
1525
1526 ir_node *
1527 new_Mod (ir_node *memop, ir_node *op1, ir_node *op2)
1528 {
1529   ir_node *res;
1530   res = new_r_Mod (current_ir_graph, current_ir_graph->current_block,
1531                     memop, op1, op2);
1532 #if PRECISE_EXC_CONTEXT
1533   if ((current_ir_graph->phase_state == phase_building) &&
1534       (get_irn_op(res) == op_Mod))  /* Could be optimized away. */
1535     res->attr.frag_arr = new_frag_arr(res);
1536 #endif
1537
1538   return res;
1539 }
1540
1541 ir_node *
1542 new_And (ir_node *op1, ir_node *op2, ir_mode *mode)
1543 {
1544   return new_r_And (current_ir_graph, current_ir_graph->current_block,
1545                     op1, op2, mode);
1546 }
1547
1548 ir_node *
1549 new_Or (ir_node *op1, ir_node *op2, ir_mode *mode)
1550 {
1551   return new_r_Or (current_ir_graph, current_ir_graph->current_block,
1552                    op1, op2, mode);
1553 }
1554
1555 ir_node *
1556 new_Eor (ir_node *op1, ir_node *op2, ir_mode *mode)
1557 {
1558   return new_r_Eor (current_ir_graph, current_ir_graph->current_block,
1559                     op1, op2, mode);
1560 }
1561
1562 ir_node *
1563 new_Not (ir_node *op, ir_mode *mode)
1564 {
1565   return new_r_Not (current_ir_graph, current_ir_graph->current_block,
1566                     op, mode);
1567 }
1568
1569 ir_node *
1570 new_Shl (ir_node *op, ir_node *k, ir_mode *mode)
1571 {
1572   return new_r_Shl (current_ir_graph, current_ir_graph->current_block,
1573                     op, k, mode);
1574 }
1575
1576 ir_node *
1577 new_Shr (ir_node *op, ir_node *k, ir_mode *mode)
1578 {
1579   return new_r_Shr (current_ir_graph, current_ir_graph->current_block,
1580                     op, k, mode);
1581 }
1582
1583 ir_node *
1584 new_Shrs (ir_node *op, ir_node *k, ir_mode *mode)
1585 {
1586   return new_r_Shrs (current_ir_graph, current_ir_graph->current_block,
1587                      op, k, mode);
1588 }
1589
1590 ir_node *
1591 new_Rotate (ir_node *op, ir_node *k, ir_mode *mode)
1592 {
1593   return new_r_Rot (current_ir_graph, current_ir_graph->current_block,
1594                      op, k, mode);
1595 }
1596
1597 ir_node *
1598 new_Abs (ir_node *op, ir_mode *mode)
1599 {
1600   return new_r_Abs (current_ir_graph, current_ir_graph->current_block,
1601                     op, mode);
1602 }
1603
1604 ir_node *
1605 new_Cmp (ir_node *op1, ir_node *op2)
1606 {
1607   return new_r_Cmp (current_ir_graph, current_ir_graph->current_block,
1608                     op1, op2);
1609 }
1610
1611 ir_node *
1612 new_Jmp (void)
1613 {
1614   return new_r_Jmp (current_ir_graph, current_ir_graph->current_block);
1615 }
1616
1617 ir_node *
1618 new_Cond (ir_node *c)
1619 {
1620   return new_r_Cond (current_ir_graph, current_ir_graph->current_block, c);
1621 }
1622
1623 ir_node *
1624 new_Call (ir_node *store, ir_node *callee, int arity, ir_node **in,
1625           type *type)
1626 {
1627   ir_node *res;
1628   res = new_r_Call (current_ir_graph, current_ir_graph->current_block,
1629                      store, callee, arity, in, type);
1630 #if PRECISE_EXC_CONTEXT
1631   if ((current_ir_graph->phase_state == phase_building) &&
1632       (get_irn_op(res) == op_Call))  /* Could be optimized away. */
1633     res->attr.call.frag_arr = new_frag_arr(res);
1634 #endif
1635
1636   return res;
1637 }
1638
1639 ir_node *
1640 new_Return (ir_node* store, int arity, ir_node **in)
1641 {
1642   return new_r_Return (current_ir_graph, current_ir_graph->current_block,
1643                        store, arity, in);
1644 }
1645
1646 ir_node *
1647 new_Raise (ir_node *store, ir_node *obj)
1648 {
1649   return new_r_Raise (current_ir_graph, current_ir_graph->current_block,
1650                       store, obj);
1651 }
1652
1653 ir_node *
1654 new_Load (ir_node *store, ir_node *addr)
1655 {
1656   ir_node *res;
1657   res = new_r_Load (current_ir_graph, current_ir_graph->current_block,
1658                      store, addr);
1659 #if PRECISE_EXC_CONTEXT
1660   if ((current_ir_graph->phase_state == phase_building) &&
1661       (get_irn_op(res) == op_Load))  /* Could be optimized away. */
1662     res->attr.frag_arr = new_frag_arr(res);
1663 #endif
1664
1665   return res;
1666 }
1667
1668 ir_node *
1669 new_Store (ir_node *store, ir_node *addr, ir_node *val)
1670 {
1671   ir_node *res;
1672   res = new_r_Store (current_ir_graph, current_ir_graph->current_block,
1673                       store, addr, val);
1674 #if PRECISE_EXC_CONTEXT
1675   if ((current_ir_graph->phase_state == phase_building) &&
1676       (get_irn_op(res) == op_Store))  /* Could be optimized away. */
1677     res->attr.frag_arr = new_frag_arr(res);
1678 #endif
1679
1680   return res;
1681 }
1682
1683 ir_node *
1684 new_Alloc (ir_node *store, ir_node *size, type *alloc_type,
1685            where_alloc where)
1686 {
1687   ir_node *res;
1688   res = new_r_Alloc (current_ir_graph, current_ir_graph->current_block,
1689                       store, size, alloc_type, where);
1690 #if PRECISE_EXC_CONTEXT
1691   if ((current_ir_graph->phase_state == phase_building) &&
1692       (get_irn_op(res) == op_Alloc))  /* Could be optimized away. */
1693     res->attr.a.frag_arr = new_frag_arr(res);
1694 #endif
1695
1696   return res;
1697 }
1698
1699 ir_node *
1700 new_Free (ir_node *store, ir_node *ptr, ir_node *size, type *free_type)
1701 {
1702   return new_r_Free (current_ir_graph, current_ir_graph->current_block,
1703                      store, ptr, size, free_type);
1704 }
1705
1706 ir_node *
1707 new_simpleSel (ir_node *store, ir_node *objptr, entity *ent)
1708 /* GL: objptr was called frame before.  Frame was a bad choice for the name
1709    as the operand could as well be a pointer to a dynamic object. */
1710 {
1711   return new_r_Sel (current_ir_graph, current_ir_graph->current_block,
1712                     store, objptr, 0, NULL, ent);
1713 }
1714
1715 ir_node *
1716 new_Sel (ir_node *store, ir_node *objptr, int n_index, ir_node **index, entity *sel)
1717 {
1718   return new_r_Sel (current_ir_graph, current_ir_graph->current_block,
1719                     store, objptr, n_index, index, sel);
1720 }
1721
1722 ir_node *
1723 new_SymConst (type_or_id_p value, symconst_kind kind)
1724 {
1725   return new_r_SymConst (current_ir_graph, current_ir_graph->current_block,
1726                          value, kind);
1727 }
1728
1729 ir_node *
1730 new_Sync (int arity, ir_node** in)
1731 {
1732   return new_r_Sync (current_ir_graph, current_ir_graph->current_block,
1733                      arity, in);
1734 }
1735
1736
1737 ir_node *
1738 new_Bad (void)
1739 {
1740   return current_ir_graph->bad;
1741 }
1742
1743 /* ********************************************************************* */
1744 /* Comfortable interface with automatic Phi node construction.           */
1745 /* (Uses also constructors of ?? interface, except new_Block.            */
1746 /* ********************************************************************* */
1747
1748 /** Block construction **/
1749 /* immature Block without predecessors */
1750 ir_node *new_immBlock (void) {
1751   ir_node *res;
1752
1753   assert(get_irg_phase_state (current_ir_graph) == phase_building);
1754   /* creates a new dynamic in-array as length of in is -1 */
1755   res = new_ir_node (current_ir_graph, NULL, op_Block, mode_R, -1, NULL);
1756   current_ir_graph->current_block = res;
1757   res->attr.block.matured = 0;
1758   set_Block_block_visited(res, 0);
1759
1760   /* Create and initialize array for Phi-node construction. */
1761   res->attr.block.graph_arr = NEW_ARR_D (ir_node *, current_ir_graph->obst,
1762                                          current_ir_graph->n_loc);
1763   memset(res->attr.block.graph_arr, 0, sizeof(ir_node *)*current_ir_graph->n_loc);
1764
1765   /* Immature block may not be optimized! */
1766   irn_vrfy (res);
1767
1768   return res;
1769 }
1770
1771 /* add an adge to a jmp/control flow node */
1772 void
1773 add_in_edge (ir_node *block, ir_node *jmp)
1774 {
1775   if (block->attr.block.matured) {
1776     assert(0 && "Error: Block already matured!\n");
1777   }
1778   else {
1779     assert (jmp != NULL);
1780     ARR_APP1 (ir_node *, block->in, jmp);
1781   }
1782 }
1783
1784 /* changing the current block */
1785 void
1786 switch_block (ir_node *target)
1787 {
1788   current_ir_graph->current_block = target;
1789 }
1790
1791 /* ************************ */
1792 /* parameter administration */
1793
1794 /* get a value from the parameter array from the current block by its index */
1795 ir_node *
1796 get_value (int pos, ir_mode *mode)
1797 {
1798   assert(get_irg_phase_state (current_ir_graph) == phase_building);
1799   inc_irg_visited(current_ir_graph);
1800   return get_r_value_internal (current_ir_graph->current_block, pos + 1, mode);
1801 }
1802
1803
1804 /* set a value at position pos in the parameter array from the current block */
1805 inline void
1806 set_value (int pos, ir_node *value)
1807 {
1808   assert(get_irg_phase_state (current_ir_graph) == phase_building);
1809   current_ir_graph->current_block->attr.block.graph_arr[pos + 1] = value;
1810 }
1811
1812 /* get the current store */
1813 inline ir_node *
1814 get_store (void)
1815 {
1816   assert(get_irg_phase_state (current_ir_graph) == phase_building);
1817   /* GL: one could call get_value instead */
1818   inc_irg_visited(current_ir_graph);
1819   return get_r_value_internal (current_ir_graph->current_block, 0, mode_M);
1820 }
1821
1822 /* set the current store */
1823 inline void
1824 set_store (ir_node *store)
1825 {
1826   assert(get_irg_phase_state (current_ir_graph) == phase_building);
1827   /* GL: one could call set_value instead */
1828   current_ir_graph->current_block->attr.block.graph_arr[0] = store;
1829 }
1830
1831 inline void
1832 keep_alive (ir_node *ka)
1833 {
1834   add_End_keepalive(current_ir_graph->end, ka);
1835 }
1836
1837 /** Useful access routines **/
1838 /* Returns the current block of the current graph.  To set the current
1839    block use switch_block(). */
1840 ir_node *get_cur_block() {
1841   return get_irg_current_block(current_ir_graph);
1842 }
1843
1844 /* Returns the frame type of the current graph */
1845 type *get_cur_frame_type() {
1846   return get_irg_frame_type(current_ir_graph);
1847 }
1848
1849
1850 /* ********************************************************************* */
1851 /* initialize */
1852
1853 /* call once for each run of the library */
1854 void
1855 init_cons (void)
1856 {
1857 }
1858
1859 /* call for each graph */
1860 void
1861 finalize_cons (ir_graph *irg) {
1862   irg->phase_state = phase_high;
1863 }