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

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief   Various irnode constructors. Automatic construction of SSA
  23  *          representation.
  24  * @author  Martin Trapp, Christian Schaefer, Goetz Lindenmaier, Boris Boesler
  25  *          Michael Beck, Matthias Braun
  26  * @version $Id$
  27  */
  28 #include "config.h"
  29
  30 #include "irprog_t.h"
  31 #include "irgraph_t.h"
  32 #include "irnode_t.h"
  33 #include "irmode_t.h"
  34 #include "ircons_t.h"
  35 #include "irverify.h"
  36 #include "irop_t.h"
  37 #include "iropt_t.h"
  38 #include "irgmod.h"
  39 #include "irhooks.h"
  40 #include "array_t.h"
  41 #include "irbackedge_t.h"
  42 #include "irflag_t.h"
  43 #include "iredges_t.h"
  44 #include "irflag_t.h"
  45 #include "error.h"
  46
  47 #include "gen_ir_cons.c.inl"
  48
  49 /**
  50  * Language dependent variable initialization callback.
  51  */
  52 static uninitialized_local_variable_func_t *default_initialize_local_variable = NULL;
  53
  54 ir_node *new_rd_Start(dbg_info *db, ir_graph *irg)
  55 {
  56         ir_node  *block = get_irg_start_block(irg);
  57         ir_node  *res   = new_ir_node(db, irg, block, op_Start, mode_T, 0, NULL);
  58
  59         res = optimize_node(res);
  60         irn_verify_irg(res, irg);
  61         return res;
  62 }
  63
  64 ir_node *new_rd_End(dbg_info *db, ir_graph *irg)
  65 {
  66         ir_node  *block = get_irg_end_block(irg);
  67         ir_node  *res   = new_ir_node(db, irg, block, op_End, mode_X, -1, NULL);
  68
  69         res = optimize_node(res);
  70         irn_verify_irg(res, irg);
  71         return res;
  72 }
  73
  74 /**
  75  * Creates a Phi node with all predecessors.  Calling this constructor
  76  * is only allowed if the corresponding block is mature.
  77  */
  78 ir_node *new_rd_Phi(dbg_info *db, ir_node *block, int arity, ir_node **in,
  79                     ir_mode *mode)
  80 {
  81         ir_graph *irg = get_irn_irg(block);
  82         ir_node  *res = new_ir_node(db, irg, block, op_Phi, mode, arity, in);
  83         res->attr.phi.u.backedge = new_backedge_arr(irg->obst, arity);
  84
  85         res = optimize_node(res);
  86         irn_verify_irg(res, irg);
  87
  88         /* Memory Phis in endless loops must be kept alive.
  89            As we can't distinguish these easily we keep all of them alive. */
  90         if (is_Phi(res) && mode == mode_M)
  91                 add_End_keepalive(get_irg_end(irg), res);
  92         return res;
  93 }
  94
  95 ir_node *new_rd_Const(dbg_info *db, ir_graph *irg, ir_tarval *con)
  96 {
  97         ir_node  *block = get_irg_start_block(irg);
  98         ir_mode  *mode  = get_tarval_mode(con);
  99         ir_node  *res   = new_ir_node(db, irg, block, op_Const, mode, 0, NULL);
 100         res->attr.con.tarval = con;
 101
 102         res = optimize_node (res);
 103         irn_verify_irg(res, irg);
 104
 105         return res;
 106 }
 107
 108 ir_node *new_rd_Const_long(dbg_info *db, ir_graph *irg, ir_mode *mode,
 109                            long value)
 110 {
 111         return new_rd_Const(db, irg, new_tarval_from_long(value, mode));
 112 }
 113
 114 ir_node *new_rd_defaultProj(dbg_info *db, ir_node *arg, long max_proj)
 115 {
 116         ir_node *res;
 117
 118         assert(is_Cond(arg));
 119         arg->attr.cond.default_proj = max_proj;
 120         res = new_rd_Proj(db, arg, mode_X, max_proj);
 121         return res;
 122 }
 123
 124 ir_node *new_rd_Sync(dbg_info *db, ir_node *block, int arity, ir_node *in[])
 125 {
 126         ir_graph *irg = get_irn_irg(block);
 127         ir_node  *res = new_ir_node(db, irg, block, op_Sync, mode_M, -1, NULL);
 128         int       i;
 129
 130         for (i = 0; i < arity; ++i)
 131                 add_Sync_pred(res, in[i]);
 132
 133         res = optimize_node(res);
 134         irn_verify_irg(res, irg);
 135         return res;
 136 }
 137
 138 ir_node *new_rd_ASM(dbg_info *db, ir_node *block, int arity, ir_node *in[],
 139                     ir_asm_constraint *inputs, int n_outs,
 140                         ir_asm_constraint *outputs, int n_clobber,
 141                         ident *clobber[], ident *text)
 142 {
 143         ir_graph *irg = get_irn_irg(block);
 144         ir_node  *res = new_ir_node(db, irg, block, op_ASM, mode_T, arity, in);
 145
 146         res->attr.assem.pin_state = op_pin_state_pinned;
 147         res->attr.assem.input_constraints
 148                 = NEW_ARR_D(ir_asm_constraint, irg->obst, arity);
 149         res->attr.assem.output_constraints
 150                 = NEW_ARR_D(ir_asm_constraint, irg->obst, n_outs);
 151         res->attr.assem.clobbers = NEW_ARR_D(ident *, irg->obst, n_clobber);
 152         res->attr.assem.text     = text;
 153
 154         memcpy(res->attr.assem.input_constraints,  inputs,  sizeof(inputs[0]) * arity);
 155         memcpy(res->attr.assem.output_constraints, outputs, sizeof(outputs[0]) * n_outs);
 156         memcpy(res->attr.assem.clobbers, clobber, sizeof(clobber[0]) * n_clobber);
 157
 158         res = optimize_node(res);
 159         irn_verify_irg(res, irg);
 160         return res;
 161 }
 162
 163 ir_node *new_rd_simpleSel(dbg_info *db, ir_node *block, ir_node *store,
 164                           ir_node *objptr, ir_entity *ent)
 165 {
 166         return new_rd_Sel(db, block, store, objptr, 0, NULL, ent);
 167 }
 168
 169 ir_node *new_rd_SymConst(dbg_info *db, ir_graph *irg, ir_mode *mode,
 170                          symconst_symbol value, symconst_kind symkind)
 171 {
 172         ir_node *block = get_irg_start_block(irg);
 173         ir_node *res   = new_ir_node(db, irg, block, op_SymConst, mode, 0, NULL);
 174         res->attr.symc.kind = symkind;
 175         res->attr.symc.sym  = value;
 176
 177         res = optimize_node(res);
 178         irn_verify_irg(res, irg);
 179         return res;
 180 }
 181
 182 ir_node *new_rd_SymConst_addr_ent(dbg_info *db, ir_graph *irg, ir_mode *mode, ir_entity *symbol)
 183 {
 184         symconst_symbol sym;
 185         sym.entity_p = symbol;
 186         return new_rd_SymConst(db, irg, mode, sym, symconst_addr_ent);
 187 }
 188
 189 ir_node *new_rd_SymConst_ofs_ent(dbg_info *db, ir_graph *irg, ir_mode *mode, ir_entity *symbol)
 190 {
 191         symconst_symbol sym;
 192         sym.entity_p = symbol;
 193         return new_rd_SymConst(db, irg, mode, sym, symconst_ofs_ent);
 194 }
 195
 196 ir_node *new_rd_SymConst_type_tag(dbg_info *db, ir_graph *irg, ir_mode *mode, ir_type *symbol)
 197 {
 198         symconst_symbol sym;
 199         sym.type_p = symbol;
 200         return new_rd_SymConst(db, irg, mode, sym, symconst_type_tag);
 201 }
 202
 203 ir_node *new_rd_SymConst_size(dbg_info *db, ir_graph *irg, ir_mode *mode, ir_type *symbol)
 204 {
 205         symconst_symbol sym;
 206         sym.type_p = symbol;
 207         return new_rd_SymConst(db, irg, mode, sym, symconst_type_size);
 208 }
 209
 210 ir_node *new_rd_SymConst_align(dbg_info *db, ir_graph *irg, ir_mode *mode, ir_type *symbol)
 211 {
 212         symconst_symbol sym;
 213         sym.type_p = symbol;
 214         return new_rd_SymConst(db, irg, mode, sym, symconst_type_align);
 215 }
 216
 217 ir_node *new_r_Start(ir_graph *irg)
 218 {
 219         return new_rd_Start(NULL, irg);
 220 }
 221 ir_node *new_r_End(ir_graph *irg)
 222 {
 223         return new_rd_End(NULL, irg);
 224 }
 225 ir_node *new_r_Const(ir_graph *irg, ir_tarval *con)
 226 {
 227         return new_rd_Const(NULL, irg, con);
 228 }
 229 ir_node *new_r_Const_long(ir_graph *irg, ir_mode *mode, long value)
 230 {
 231         return new_rd_Const_long(NULL, irg, mode, value);
 232 }
 233 ir_node *new_r_SymConst(ir_graph *irg, ir_mode *mode, symconst_symbol value,
 234                         symconst_kind symkind)
 235 {
 236         return new_rd_SymConst(NULL, irg, mode, value, symkind);
 237 }
 238 ir_node *new_r_simpleSel(ir_node *block, ir_node *store, ir_node *objptr,
 239                          ir_entity *ent)
 240 {
 241         return new_rd_Sel(NULL, block, store, objptr, 0, NULL, ent);
 242 }
 243 ir_node *new_r_Phi(ir_node *block, int arity, ir_node **in, ir_mode *mode)
 244 {
 245         return new_rd_Phi(NULL, block, arity, in, mode);
 246 }
 247 ir_node *new_r_Sync(ir_node *block, int arity, ir_node *in[])
 248 {
 249         return new_rd_Sync(NULL, block, arity, in);
 250 }
 251 ir_node *new_r_defaultProj(ir_node *arg, long max_proj)
 252 {
 253         return new_rd_defaultProj(NULL, arg, max_proj);
 254 }
 255 ir_node *new_r_Bad(ir_graph *irg)
 256 {
 257         return get_irg_bad(irg);
 258 }
 259 ir_node *new_r_NoMem(ir_graph *irg)
 260 {
 261         return get_irg_no_mem(irg);
 262 }
 263 ir_node *new_r_ASM(ir_node *block,
 264                    int arity, ir_node *in[], ir_asm_constraint *inputs,
 265                    int n_outs, ir_asm_constraint *outputs,
 266                    int n_clobber, ident *clobber[], ident *text)
 267 {
 268         return new_rd_ASM(NULL, block, arity, in, inputs, n_outs, outputs, n_clobber, clobber, text);
 269 }
 270
 271 /** ********************/
 272 /** public interfaces  */
 273 /** construction tools */
 274
 275 ir_node *new_d_Start(dbg_info *db)
 276 {
 277         ir_node *res;
 278
 279         assert(get_irg_phase_state(current_ir_graph) == phase_building);
 280         res = new_ir_node(db, current_ir_graph, current_ir_graph->current_block,
 281                           op_Start, mode_T, 0, NULL);
 282
 283         res = optimize_node(res);
 284         irn_verify_irg(res, current_ir_graph);
 285         return res;
 286 }
 287
 288 ir_node *new_d_End(dbg_info *db)
 289 {
 290         ir_node *res;
 291         assert(get_irg_phase_state(current_ir_graph) == phase_building);
 292         res = new_ir_node(db, current_ir_graph,  current_ir_graph->current_block,
 293                           op_End, mode_X, -1, NULL);
 294         res = optimize_node(res);
 295         irn_verify_irg(res, current_ir_graph);
 296
 297         return res;
 298 }
 299
 300 /* ***********************************************************************/
 301 /* Methods necessary for automatic Phi node creation                     */
 302 /*
 303   ir_node *phi_merge            (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
 304   ir_node *get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
 305   ir_node *new_rd_Phi0          (ir_graph *irg, ir_node *block, ir_mode *mode)
 306   ir_node *new_rd_Phi_in        (ir_graph *irg, ir_node *block, ir_mode *mode, ir_node **in, int ins)
 307
 308   Call Graph:   ( A ---> B == A "calls" B)
 309
 310        get_value         mature_immBlock
 311           |                   |
 312           |                   |
 313           |                   |
 314           |          ---> phi_merge
 315           |         /       /   \
 316           |        /       /     \
 317          \|/      /      |/_      \
 318        get_r_value_internal        |
 319                 |                  |
 320                 |                  |
 321                \|/                \|/
 322            new_rd_Phi0          new_rd_Phi_in
 323
 324 * *************************************************************************** */
 325
 326 /** Creates a Phi node with 0 predecessors. */
 327 static inline ir_node *new_rd_Phi0(ir_node *block, ir_mode *mode)
 328 {
 329         ir_graph *irg = get_irn_irg(block);
 330         ir_node  *res = new_ir_node(NULL, irg, block, op_Phi, mode, 0, NULL);
 331         irn_verify_irg(res, irg);
 332         return res;
 333 }
 334
 335 /**
 336  * Internal constructor of a Phi node by a phi_merge operation.
 337  *
 338  * @param block  the block in which the Phi will be constructed
 339  * @param mode   the mod eof the Phi node
 340  * @param in     the input array of the phi node
 341  * @param n_in   number of elements in the input array
 342  * @param phi0   in non-NULL: the Phi0 node in the same block that represents
 343  *               the value for which the new Phi is constructed
 344  */
 345 static ir_node *new_rd_Phi_in(ir_node *block, ir_mode *mode,
 346                               int n_in, ir_node **in, ir_node *phi0)
 347 {
 348         int i;
 349         ir_node *res, *known;
 350         ir_graph *irg = get_irn_irg(block);
 351
 352         /* Allocate a new node on the obstack.  The allocation copies the in
 353            array. */
 354         res = new_ir_node(NULL, irg, block, op_Phi, mode, n_in, in);
 355         res->attr.phi.u.backedge = new_backedge_arr(irg->obst, n_in);
 356
 357         /* This loop checks whether the Phi has more than one predecessor.
 358            If so, it is a real Phi node and we break the loop.  Else the
 359            Phi node merges the same definition on several paths and therefore
 360            is not needed.
 361            Note: We MUST consider Bad nodes, else we might get data flow cycles in dead loops! */
 362         known = res;
 363         for (i = n_in - 1; i >= 0; --i) {
 364                 assert(in[i]);
 365
 366                 in[i] = skip_Id(in[i]);  /* increases the number of freed Phis. */
 367
 368                 /* Optimize self referencing Phis:  We can't detect them yet properly, as
 369                 they still refer to the Phi0 they will replace.  So replace right now. */
 370                 if (phi0 && in[i] == phi0)
 371                         in[i] = res;
 372
 373                 if (in[i] == res || in[i] == known)
 374                         continue;
 375
 376                 if (known == res)
 377                         known = in[i];
 378                 else
 379                         break;
 380         }
 381
 382         /* i < 0: there is at most one predecessor, we don't need a phi node. */
 383         if (i < 0) {
 384                 if (res != known) {
 385                         edges_node_deleted(res, current_ir_graph);
 386                         obstack_free(current_ir_graph->obst, res);
 387                         if (is_Phi(known)) {
 388                                 /* If pred is a phi node we want to optimize it: If loops are matured in a bad
 389                                    order, an enclosing Phi know may get superfluous. */
 390                                 res = optimize_in_place_2(known);
 391                                 if (res != known)
 392                                         exchange(known, res);
 393                         }
 394                         else
 395                                 res = known;
 396                 } else {
 397                         /* A undefined value, e.g., in unreachable code. */
 398                         res = new_r_Bad(irg);
 399                 }
 400         } else {
 401                 res = optimize_node(res);  /* This is necessary to add the node to the hash table for cse. */
 402                 irn_verify_irg(res, irg);
 403                 /* Memory Phis in endless loops must be kept alive.
 404                    As we can't distinguish these easily we keep all of them alive. */
 405                 if (is_Phi(res) && mode == mode_M)
 406                         add_End_keepalive(get_irg_end(irg), res);
 407         }
 408
 409         return res;
 410 }
 411
 412 static ir_node *get_r_value_internal(ir_node *block, int pos, ir_mode *mode);
 413
 414 /**
 415  * Computes the predecessors for the real phi node, and then
 416  * allocates and returns this node.  The routine called to allocate the
 417  * node might optimize it away and return a real value.
 418  * This function must be called with an in-array of proper size.
 419  */
 420 static ir_node *phi_merge(ir_node *block, int pos, ir_mode *mode,
 421                           int n_ins, ir_node **ins)
 422 {
 423         ir_graph *irg = get_irn_irg(block);
 424         ir_node *prevBlock, *res, *phi0, *phi0_all;
 425         int i;
 426
 427         /* If this block has no value at pos create a Phi0 and remember it
 428            in graph_arr to break recursions.
 429            Else we may not set graph_arr as there a later value is remembered. */
 430         phi0 = NULL;
 431         if (block->attr.block.graph_arr[pos] == NULL) {
 432
 433                 if (block == get_irg_start_block(irg)) {
 434                         /* Collapsing to Bad tarvals is no good idea.
 435                            So we call a user-supplied routine here that deals with this
 436                            case as appropriate for the given language. Sorrily the only
 437                            help we can give here is the position.
 438
 439                            Even if all variables are defined before use, it can happen that
 440                            we get to the start block, if a Cond has been replaced by a tuple
 441                            (bad, jmp).  In this case we call the function needlessly,
 442                            eventually generating an non existent error.
 443                            However, this SHOULD NOT HAPPEN, as bad control flow nodes are
 444                            intercepted before recurring.
 445                          */
 446                         if (default_initialize_local_variable != NULL) {
 447                                 ir_node *rem = get_r_cur_block(irg);
 448
 449                                 set_r_cur_block(irg, block);
 450                                 block->attr.block.graph_arr[pos] = default_initialize_local_variable(irg, mode, pos - 1);
 451                                 set_r_cur_block(irg, rem);
 452                         } else {
 453                                 block->attr.block.graph_arr[pos] = new_r_Unknown(irg, mode);
 454                         }
 455                         return block->attr.block.graph_arr[pos];
 456                 } else {
 457                         phi0 = new_rd_Phi0(block, mode);
 458                         block->attr.block.graph_arr[pos] = phi0;
 459                 }
 460         }
 461
 462         /* This loop goes to all predecessor blocks of the block the Phi node
 463            is in and there finds the operands of the Phi node by calling
 464            get_r_value_internal.  */
 465         for (i = 1; i <= n_ins; ++i) {
 466                 ir_node *cf_pred = block->in[i];
 467                 ir_node *prevCfOp = skip_Proj(cf_pred);
 468                 assert(prevCfOp);
 469                 if (is_Bad(prevCfOp)) {
 470                         /* In case a Cond has been optimized we would get right to the start block
 471                         with an invalid definition. */
 472                         ins[i-1] = new_r_Bad(irg);
 473                         continue;
 474                 }
 475                 prevBlock = prevCfOp->in[0]; /* go past control flow op to prev block */
 476                 assert(prevBlock);
 477                 if (!is_Bad(prevBlock)) {
 478                         ins[i-1] = get_r_value_internal(prevBlock, pos, mode);
 479                 } else {
 480                         ins[i-1] = new_r_Bad(irg);
 481                 }
 482         }
 483
 484         /* We want to pass the Phi0 node to the constructor: this finds additional
 485            optimization possibilities.
 486            The Phi0 node either is allocated in this function, or it comes from
 487            a former call to get_r_value_internal(). In this case we may not yet
 488            exchange phi0, as this is done in mature_immBlock(). */
 489         if (phi0 == NULL) {
 490                 phi0_all = block->attr.block.graph_arr[pos];
 491                 if (! is_Phi0(phi0_all)            ||
 492                     get_irn_arity(phi0_all) != 0   ||
 493                     get_nodes_block(phi0_all) != block)
 494                         phi0_all = NULL;
 495         } else {
 496                 phi0_all = phi0;
 497         }
 498
 499         /* After collecting all predecessors into the array ins a new Phi node
 500            with these predecessors is created.  This constructor contains an
 501            optimization: If all predecessors of the Phi node are identical it
 502            returns the only operand instead of a new Phi node.  */
 503         res = new_rd_Phi_in(block, mode, n_ins, ins, phi0_all);
 504
 505         /* In case we allocated a Phi0 node at the beginning of this procedure,
 506            we need to exchange this Phi0 with the real Phi. */
 507         if (phi0 != NULL) {
 508                 exchange(phi0, res);
 509                 block->attr.block.graph_arr[pos] = res;
 510         }
 511
 512         return res;
 513 }
 514
 515 /**
 516  * This function returns the last definition of a value.  In case
 517  * this value was last defined in a previous block, Phi nodes are
 518  * inserted.  If the part of the firm graph containing the definition
 519  * is not yet constructed, a dummy Phi node is returned.
 520  *
 521  * @param block   the current block
 522  * @param pos     the value number of the value searched
 523  * @param mode    the mode of this value (needed for Phi construction)
 524  */
 525 static ir_node *get_r_value_internal(ir_node *block, int pos, ir_mode *mode)
 526 {
 527         ir_node *res;
 528         /* There are 4 cases to treat.
 529
 530            1. The block is not mature and we visit it the first time.  We can not
 531               create a proper Phi node, therefore a Phi0, i.e., a Phi without
 532               predecessors is returned.  This node is added to the linked list (block
 533               attribute "phis") of the containing block to be completed when this block is
 534               matured. (Completion will add a new Phi and turn the Phi0 into an Id
 535               node.)
 536
 537            2. The value is already known in this block, graph_arr[pos] is set and we
 538               visit the block the first time.  We can return the value without
 539               creating any new nodes.
 540
 541            3. The block is mature and we visit it the first time.  A Phi node needs
 542               to be created (phi_merge).  If the Phi is not needed, as all it's
 543               operands are the same value reaching the block through different
 544               paths, it's optimized away and the value itself is returned.
 545
 546            4. The block is mature, and we visit it the second time.  Now two
 547               subcases are possible:
 548               * The value was computed completely the last time we were here. This
 549                 is the case if there is no loop.  We can return the proper value.
 550               * The recursion that visited this node and set the flag did not
 551                 return yet.  We are computing a value in a loop and need to
 552                 break the recursion.  This case only happens if we visited
 553             the same block with phi_merge before, which inserted a Phi0.
 554             So we return the Phi0.
 555         */
 556
 557         /* case 4 -- already visited. */
 558         if (irn_visited(block)) {
 559                 /* As phi_merge allocates a Phi0 this value is always defined. Here
 560                 is the critical difference of the two algorithms. */
 561                 assert(block->attr.block.graph_arr[pos]);
 562                 return block->attr.block.graph_arr[pos];
 563         }
 564
 565         /* visited the first time */
 566         mark_irn_visited(block);
 567
 568         /* Get the local valid value */
 569         res = block->attr.block.graph_arr[pos];
 570
 571         /* case 2 -- If the value is actually computed, return it. */
 572         if (res != NULL)
 573                 return res;
 574
 575         if (block->attr.block.is_matured) { /* case 3 */
 576
 577                 /* The Phi has the same amount of ins as the corresponding block. */
 578                 int n_in = get_irn_arity(block);
 579                 ir_node **in;
 580                 NEW_ARR_A(ir_node *, in, n_in);
 581
 582                 /* Phi merge collects the predecessors and then creates a node. */
 583                 res = phi_merge(block, pos, mode, n_in, in);
 584         } else {  /* case 1 */
 585                 /* The block is not mature, we don't know how many in's are needed.  A Phi
 586                    with zero predecessors is created.  Such a Phi node is called Phi0
 587                    node.  The Phi0 is then added to the list of Phi0 nodes in this block
 588                    to be matured by mature_immBlock later.
 589                    The Phi0 has to remember the pos of it's internal value.  If the real
 590                    Phi is computed, pos is used to update the array with the local
 591                    values. */
 592                 res = new_rd_Phi0(block, mode);
 593                 res->attr.phi.u.pos    = pos;
 594                 res->attr.phi.next     = block->attr.block.phis;
 595                 block->attr.block.phis = res;
 596         }
 597
 598         assert(is_ir_node(res) && "phi_merge() failed to construct a definition");
 599
 600         /* The local valid value is available now. */
 601         block->attr.block.graph_arr[pos] = res;
 602
 603         return res;
 604 }
 605
 606 /* ************************************************************************** */
 607
 608 /*
 609  * Finalize a Block node, when all control flows are known.
 610  * Acceptable parameters are only Block nodes.
 611  */
 612 void mature_immBlock(ir_node *block)
 613 {
 614         int ins;
 615         ir_node *n, **nin;
 616         ir_node *next;
 617
 618         assert(is_Block(block));
 619         if (!get_Block_matured(block)) {
 620                 ir_graph *irg = current_ir_graph;
 621
 622                 ins = ARR_LEN(block->in) - 1;
 623                 /* Fix block parameters */
 624                 block->attr.block.backedge = new_backedge_arr(irg->obst, ins);
 625
 626                 /* An array for building the Phi nodes. */
 627                 NEW_ARR_A(ir_node *, nin, ins);
 628
 629                 /* Traverse a chain of Phi nodes attached to this block and mature
 630                 these, too. **/
 631                 for (n = block->attr.block.phis; n; n = next) {
 632                         inc_irg_visited(irg);
 633                         next = n->attr.phi.next;
 634                         exchange(n, phi_merge(block, n->attr.phi.u.pos, n->mode, ins, nin));
 635                 }
 636
 637                 block->attr.block.is_matured = 1;
 638
 639                 /* Now, as the block is a finished Firm node, we can optimize it.
 640                    Since other nodes have been allocated since the block was created
 641                    we can not free the node on the obstack.  Therefore we have to call
 642                    optimize_in_place().
 643                    Unfortunately the optimization does not change a lot, as all allocated
 644                    nodes refer to the unoptimized node.
 645                    We can call optimize_in_place_2(), as global cse has no effect on blocks. */
 646                 block = optimize_in_place_2(block);
 647                 irn_verify_irg(block, irg);
 648         }
 649 }
 650
 651 ir_node *new_d_Phi(dbg_info *db, int arity, ir_node **in, ir_mode *mode)
 652 {
 653         assert(get_irg_phase_state(current_ir_graph) == phase_building);
 654         return new_rd_Phi(db, current_ir_graph->current_block, arity, in, mode);
 655 }
 656
 657 ir_node *new_d_Const(dbg_info *db, ir_tarval *con)
 658 {
 659         assert(get_irg_phase_state(current_ir_graph) == phase_building);
 660         return new_rd_Const(db, current_ir_graph, con);
 661 }
 662
 663 ir_node *new_d_Const_long(dbg_info *db, ir_mode *mode, long value)
 664 {
 665         assert(get_irg_phase_state(current_ir_graph) == phase_building);
 666         return new_rd_Const_long(db, current_ir_graph, mode, value);
 667 }
 668
 669 ir_node *new_d_defaultProj(dbg_info *db, ir_node *arg, long max_proj)
 670 {
 671         ir_node *res;
 672         assert(is_Cond(arg));
 673         assert(get_irg_phase_state(current_ir_graph) == phase_building);
 674         arg->attr.cond.default_proj = max_proj;
 675         res = new_d_Proj(db, arg, mode_X, max_proj);
 676         return res;
 677 }
 678
 679 ir_node *new_d_simpleSel(dbg_info *db, ir_node *store, ir_node *objptr,
 680                          ir_entity *ent)
 681 {
 682         assert(get_irg_phase_state(current_ir_graph) == phase_building);
 683         return new_rd_Sel(db, current_ir_graph->current_block,
 684                           store, objptr, 0, NULL, ent);
 685 }
 686
 687 ir_node *new_d_SymConst(dbg_info *db, ir_mode *mode, symconst_symbol value,
 688                         symconst_kind kind)
 689 {
 690         assert(get_irg_phase_state(current_ir_graph) == phase_building);
 691         return new_rd_SymConst(db, current_ir_graph, mode, value, kind);
 692 }
 693
 694 ir_node *new_d_Sync(dbg_info *db, int arity, ir_node *in[])
 695 {
 696         assert(get_irg_phase_state(current_ir_graph) == phase_building);
 697         return new_rd_Sync(db, current_ir_graph->current_block, arity, in);
 698 }
 699
 700 ir_node *new_d_ASM(dbg_info *db, int arity, ir_node *in[],
 701                    ir_asm_constraint *inputs,
 702                    int n_outs, ir_asm_constraint *outputs, int n_clobber,
 703                    ident *clobber[], ident *text)
 704 {
 705         assert(get_irg_phase_state(current_ir_graph) == phase_building);
 706         return new_rd_ASM(db, current_ir_graph->current_block, arity, in, inputs,
 707                           n_outs, outputs, n_clobber, clobber, text);
 708 }
 709
 710 ir_node *new_rd_immBlock(dbg_info *dbgi, ir_graph *irg)
 711 {
 712         ir_node *res;
 713
 714         assert(get_irg_phase_state(irg) == phase_building);
 715         /* creates a new dynamic in-array as length of in is -1 */
 716         res = new_ir_node(dbgi, irg, NULL, op_Block, mode_BB, -1, NULL);
 717
 718         res->attr.block.is_matured  = 0;
 719         res->attr.block.is_dead     = 0;
 720         res->attr.block.irg.irg     = irg;
 721         res->attr.block.backedge    = NULL;
 722         res->attr.block.in_cg       = NULL;
 723         res->attr.block.cg_backedge = NULL;
 724         res->attr.block.extblk      = NULL;
 725         res->attr.block.region      = NULL;
 726         res->attr.block.entity      = NULL;
 727
 728         set_Block_block_visited(res, 0);
 729
 730         /* Create and initialize array for Phi-node construction. */
 731         res->attr.block.graph_arr = NEW_ARR_D(ir_node *, irg->obst, irg->n_loc);
 732         memset(res->attr.block.graph_arr, 0, sizeof(ir_node*) * irg->n_loc);
 733
 734         /* Immature block may not be optimized! */
 735         irn_verify_irg(res, irg);
 736
 737         return res;
 738 }
 739
 740 ir_node *new_r_immBlock(ir_graph *irg)
 741 {
 742         return new_rd_immBlock(NULL, irg);
 743 }
 744
 745 ir_node *new_d_immBlock(dbg_info *dbgi)
 746 {
 747         return new_rd_immBlock(dbgi, current_ir_graph);
 748 }
 749
 750 ir_node *new_immBlock(void)
 751 {
 752         return new_rd_immBlock(NULL, current_ir_graph);
 753 }
 754
 755 void add_immBlock_pred(ir_node *block, ir_node *jmp)
 756 {
 757         int n = ARR_LEN(block->in) - 1;
 758
 759         assert(is_Block(block) && "Error: Must be a Block");
 760         assert(!block->attr.block.is_matured && "Error: Block already matured!\n");
 761         assert(is_ir_node(jmp));
 762
 763         ARR_APP1(ir_node *, block->in, jmp);
 764         /* Call the hook */
 765         hook_set_irn_n(block, n, jmp, NULL);
 766 }
 767
 768 void set_cur_block(ir_node *target)
 769 {
 770         current_ir_graph->current_block = target;
 771 }
 772
 773 void set_r_cur_block(ir_graph *irg, ir_node *target)
 774 {
 775         irg->current_block = target;
 776 }
 777
 778 ir_node *get_r_cur_block(ir_graph *irg)
 779 {
 780         return irg->current_block;
 781 }
 782
 783 ir_node *get_cur_block(void)
 784 {
 785         return get_r_cur_block(current_ir_graph);
 786 }
 787
 788 ir_node *get_r_value(ir_graph *irg, int pos, ir_mode *mode)
 789 {
 790         assert(get_irg_phase_state(irg) == phase_building);
 791         inc_irg_visited(irg);
 792
 793         assert(pos >= 0);
 794
 795         return get_r_value_internal(irg->current_block, pos + 1, mode);
 796 }
 797
 798 ir_node *get_value(int pos, ir_mode *mode)
 799 {
 800         return get_r_value(current_ir_graph, pos, mode);
 801 }
 802
 803 /**
 804  * helper function for guess_mode: recursively look for a definition for
 805  * local variable @p pos, returns its mode if found.
 806  */
 807 static ir_mode *guess_recursively(ir_node *block, int pos)
 808 {
 809         ir_node *value;
 810         int      n_preds;
 811         int      i;
 812
 813         if (irn_visited(block))
 814                 return NULL;
 815         mark_irn_visited(block);
 816
 817         /* already have a defintion -> we can simply look at its mode */
 818         value = block->attr.block.graph_arr[pos];
 819         if (value != NULL)
 820                 return get_irn_mode(value);
 821
 822         /* now we try to guess, by looking at the predecessor blocks */
 823         n_preds = get_irn_arity(block);
 824         for (i = 0; i < n_preds; ++i) {
 825                 ir_node *pred_block = get_Block_cfgpred_block(block, i);
 826                 ir_mode *mode       = guess_recursively(pred_block, pos);
 827                 if (mode != NULL)
 828                         return mode;
 829         }
 830
 831         /* no way to guess */
 832         return NULL;
 833 }
 834
 835 ir_mode *ir_guess_mode(int pos)
 836 {
 837         ir_graph *irg   = current_ir_graph;
 838         ir_node  *block = irg->current_block;
 839         ir_node  *value = block->attr.block.graph_arr[pos+1];
 840         ir_mode  *mode;
 841
 842         /* already have a defintion -> we can simply look at its mode */
 843         if (value != NULL)
 844                 return get_irn_mode(value);
 845
 846         ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
 847         inc_irg_visited(current_ir_graph);
 848         mode = guess_recursively(block, pos+1);
 849         ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
 850
 851         return mode;
 852 }
 853
 854 void set_r_value(ir_graph *irg, int pos, ir_node *value)
 855 {
 856         assert(get_irg_phase_state(irg) == phase_building);
 857         assert(pos >= 0);
 858         assert(pos+1 < irg->n_loc);
 859         assert(is_ir_node(value));
 860         irg->current_block->attr.block.graph_arr[pos + 1] = value;
 861 }
 862
 863 void set_value(int pos, ir_node *value)
 864 {
 865         set_r_value(current_ir_graph, pos, value);
 866 }
 867
 868 int find_value(ir_node *value)
 869 {
 870         int i;
 871         ir_node *bl = current_ir_graph->current_block;
 872
 873         for (i = ARR_LEN(bl->attr.block.graph_arr) - 1; i >= 1; --i)
 874                 if (bl->attr.block.graph_arr[i] == value)
 875                         return i - 1;
 876         return -1;
 877 }
 878
 879 ir_node *get_r_store(ir_graph *irg)
 880 {
 881         assert(get_irg_phase_state(irg) == phase_building);
 882         inc_irg_visited(irg);
 883         return get_r_value_internal(irg->current_block, 0, mode_M);
 884 }
 885
 886 ir_node *get_store(void)
 887 {
 888         return get_r_store(current_ir_graph);
 889 }
 890
 891 void set_r_store(ir_graph *irg, ir_node *store)
 892 {
 893         ir_node *load, *pload, *pred, *in[2];
 894
 895         assert(get_irg_phase_state(irg) == phase_building);
 896         /* Beware: due to dead code elimination, a store might become a Bad node even in
 897            the construction phase. */
 898         assert((get_irn_mode(store) == mode_M || is_Bad(store)) && "storing non-memory node");
 899
 900         if (get_opt_auto_create_sync()) {
 901                 /* handle non-volatile Load nodes by automatically creating Sync's */
 902                 load = skip_Proj(store);
 903                 if (is_Load(load) && get_Load_volatility(load) == volatility_non_volatile) {
 904                         pred = get_Load_mem(load);
 905
 906                         if (is_Sync(pred)) {
 907                                 /* a Load after a Sync: move it up */
 908                                 ir_node *mem = skip_Proj(get_Sync_pred(pred, 0));
 909
 910                                 set_Load_mem(load, get_memop_mem(mem));
 911                                 add_Sync_pred(pred, store);
 912                                 store = pred;
 913                         } else {
 914                                 pload = skip_Proj(pred);
 915                                 if (is_Load(pload) && get_Load_volatility(pload) == volatility_non_volatile) {
 916                                         /* a Load after a Load: create a new Sync */
 917                                         set_Load_mem(load, get_Load_mem(pload));
 918
 919                                         in[0] = pred;
 920                                         in[1] = store;
 921                                         store = new_r_Sync(irg->current_block, 2, in);
 922                                 }
 923                         }
 924                 }
 925         }
 926         irg->current_block->attr.block.graph_arr[0] = store;
 927 }
 928
 929 void set_store(ir_node *store)
 930 {
 931         set_r_store(current_ir_graph, store);
 932 }
 933
 934 void keep_alive(ir_node *ka)
 935 {
 936         add_End_keepalive(get_irg_end(current_ir_graph), ka);
 937 }
 938
 939 void ir_set_uninitialized_local_variable_func(
 940                 uninitialized_local_variable_func_t *func)
 941 {
 942         default_initialize_local_variable = func;
 943 }
 944
 945 void irg_finalize_cons(ir_graph *irg)
 946 {
 947         set_irg_phase_state(irg, phase_high);
 948 }
 949
 950 void irp_finalize_cons(void)
 951 {
 952         int i;
 953         for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 954                 irg_finalize_cons(get_irp_irg(i));
 955         }
 956         irp->phase_state = phase_high;
 957 }
 958
 959 ir_node *new_Start(void)
 960 {
 961         return new_d_Start(NULL);
 962 }
 963 ir_node *new_End(void)
 964 {
 965         return new_d_End(NULL);
 966 }
 967 ir_node *new_Const(ir_tarval *con)
 968 {
 969         return new_d_Const(NULL, con);
 970 }
 971
 972 ir_node *new_Const_long(ir_mode *mode, long value)
 973 {
 974         return new_d_Const_long(NULL, mode, value);
 975 }
 976
 977 ir_node *new_SymConst(ir_mode *mode, symconst_symbol value, symconst_kind kind)
 978 {
 979         return new_d_SymConst(NULL, mode, value, kind);
 980 }
 981 ir_node *new_simpleSel(ir_node *store, ir_node *objptr, ir_entity *ent)
 982 {
 983         return new_d_simpleSel(NULL, store, objptr, ent);
 984 }
 985 ir_node *new_Phi(int arity, ir_node **in, ir_mode *mode)
 986 {
 987         return new_d_Phi(NULL, arity, in, mode);
 988 }
 989 ir_node *new_Sync(int arity, ir_node *in[])
 990 {
 991         return new_d_Sync(NULL, arity, in);
 992 }
 993 ir_node *new_defaultProj(ir_node *arg, long max_proj)
 994 {
 995         return new_d_defaultProj(NULL, arg, max_proj);
 996 }
 997 ir_node *new_Bad(void)
 998 {
 999         assert(get_irg_phase_state(current_ir_graph) == phase_building);
1000         return get_irg_bad(current_ir_graph);
1001 }
1002 ir_node *new_NoMem(void)
1003 {
1004         assert(get_irg_phase_state(current_ir_graph) == phase_building);
1005         return get_irg_no_mem(current_ir_graph);
1006 }
1007 ir_node *new_ASM(int arity, ir_node *in[], ir_asm_constraint *inputs,
1008                  int n_outs, ir_asm_constraint *outputs,
1009                  int n_clobber, ident *clobber[], ident *text)
1010 {
1011         return new_d_ASM(NULL, arity, in, inputs, n_outs, outputs, n_clobber, clobber, text);
1012 }
1013
1014 ir_node *new_r_Anchor(ir_graph *irg)
1015 {
1016         ir_node *in[anchor_last];
1017         ir_node *res;
1018         memset(in, 0, sizeof(in));
1019         res = new_ir_node(NULL, irg, NULL, op_Anchor, mode_ANY, anchor_last, in);
1020
1021         /* hack to get get_irn_irg working: set block to ourself and allow
1022          * get_Block_irg for anchor */
1023         res->attr.irg.irg = irg;
1024         res->in[0] = res;
1025
1026         return res;
1027 }