2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
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.
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.
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
22 * @brief Various irnode constructors. Automatic construction of SSA
24 * @author Martin Trapp, Christian Schaefer, Goetz Lindenmaier, Boris Boesler
31 #include "irgraph_t.h"
41 #include "irbackedge_t.h"
43 #include "iredges_t.h"
47 /* when we need verifying */
49 # define IRN_VERIFY_IRG(res, irg)
51 # define IRN_VERIFY_IRG(res, irg) irn_verify_irg(res, irg)
55 * Language dependent variable initialization callback.
57 static uninitialized_local_variable_func_t *default_initialize_local_variable = NULL;
59 #include "gen_ir_cons.c.inl"
61 static ir_node *new_bd_Start(dbg_info *db, ir_node *block)
64 ir_graph *irg = get_irn_irg(block);
66 res = new_ir_node(db, irg, block, op_Start, mode_T, 0, NULL);
68 IRN_VERIFY_IRG(res, irg);
72 static ir_node *new_bd_End(dbg_info *db, ir_node *block)
75 ir_graph *irg = get_irn_irg(block);
77 res = new_ir_node(db, irg, block, op_End, mode_X, -1, NULL);
79 IRN_VERIFY_IRG(res, irg);
84 * Creates a Phi node with all predecessors. Calling this constructor
85 * is only allowed if the corresponding block is mature.
87 static ir_node *new_bd_Phi(dbg_info *db, ir_node *block, int arity, ir_node **in, ir_mode *mode)
90 ir_graph *irg = get_irn_irg(block);
94 /* Don't assert that block matured: the use of this constructor is strongly
96 if (get_Block_matured(block))
97 assert(get_irn_arity(block) == arity);
99 res = new_ir_node(db, irg, block, op_Phi, mode, arity, in);
101 res->attr.phi.u.backedge = new_backedge_arr(irg->obst, arity);
103 for (i = arity - 1; i >= 0; --i)
104 if (is_Unknown(in[i])) {
109 if (!has_unknown) res = optimize_node(res);
110 IRN_VERIFY_IRG(res, irg);
112 /* Memory Phis in endless loops must be kept alive.
113 As we can't distinguish these easily we keep all of them alive. */
114 if (is_Phi(res) && mode == mode_M)
115 add_End_keepalive(get_irg_end(irg), res);
119 static ir_node *new_bd_Const_type(dbg_info *db, tarval *con, ir_type *tp)
122 ir_graph *irg = current_ir_graph;
124 res = new_ir_node(db, irg, get_irg_start_block(irg), op_Const, get_tarval_mode(con), 0, NULL);
125 res->attr.con.tarval = con;
126 set_Const_type(res, tp); /* Call method because of complex assertion. */
127 res = optimize_node (res);
128 assert(get_Const_type(res) == tp);
129 IRN_VERIFY_IRG(res, irg);
132 } /* new_bd_Const_type */
134 static ir_node *new_bd_Const(dbg_info *db, tarval *con)
136 ir_graph *irg = current_ir_graph;
138 return new_rd_Const_type(db, irg, con, firm_unknown_type);
141 static ir_node *new_bd_Const_long(dbg_info *db, ir_mode *mode, long value)
143 ir_graph *irg = current_ir_graph;
145 return new_rd_Const(db, irg, new_tarval_from_long(value, mode));
146 } /* new_bd_Const_long */
148 static ir_node *new_bd_defaultProj(dbg_info *db, ir_node *arg, long max_proj)
152 assert(arg->op == op_Cond);
153 arg->attr.cond.default_proj = max_proj;
154 res = new_rd_Proj(db, arg, mode_X, max_proj);
156 } /* new_bd_defaultProj */
158 static ir_node *new_bd_Sel(dbg_info *db, ir_node *block, ir_node *store,
159 ir_node *objptr, int arity, ir_node **in,
165 ir_graph *irg = get_irn_irg(block);
166 ir_mode *mode = is_Method_type(get_entity_type(ent)) ? mode_P_code : mode_P_data;
168 assert(ent != NULL && is_entity(ent) && "entity expected in Sel construction");
171 NEW_ARR_A(ir_node *, r_in, r_arity); /* uses alloca */
174 memcpy(&r_in[2], in, sizeof(ir_node *) * arity);
176 * Sel's can select functions which should be of mode mode_P_code.
178 res = new_ir_node(db, irg, block, op_Sel, mode, r_arity, r_in);
179 res->attr.sel.entity = ent;
180 res = optimize_node(res);
181 IRN_VERIFY_IRG(res, irg);
185 static ir_node *new_bd_SymConst_type(dbg_info *db, ir_node *block,
186 ir_mode *mode, symconst_symbol value,
187 symconst_kind symkind, ir_type *tp)
189 ir_graph *irg = get_irn_irg(block);
190 ir_node *res = new_ir_node(db, irg, block, op_SymConst, mode, 0, NULL);
192 res->attr.symc.kind = symkind;
193 res->attr.symc.sym = value;
194 res->attr.symc.tp = tp;
196 res = optimize_node(res);
197 IRN_VERIFY_IRG(res, irg);
199 } /* new_bd_SymConst_type */
201 static ir_node *new_bd_Sync(dbg_info *db, ir_node *block)
204 ir_graph *irg = get_irn_irg(block);
206 res = new_ir_node(db, irg, block, op_Sync, mode_M, -1, NULL);
207 /* no need to call optimize node here, Sync are always created with no predecessors */
208 IRN_VERIFY_IRG(res, irg);
212 static ir_node *new_bd_ASM(dbg_info *db, ir_node *block, int arity,
213 ir_node *in[], ir_asm_constraint *inputs, int n_outs,
214 ir_asm_constraint *outputs, int n_clobber,
215 ident *clobber[], ident *text)
218 ir_graph *irg = get_irn_irg(block);
220 res = new_ir_node(db, irg, block, op_ASM, mode_T, arity, in);
221 res->attr.assem.pin_state = op_pin_state_pinned;
222 res->attr.assem.input_constraints
223 = NEW_ARR_D(ir_asm_constraint, irg->obst, arity);
224 res->attr.assem.output_constraints
225 = NEW_ARR_D(ir_asm_constraint, irg->obst, n_outs);
226 res->attr.assem.clobbers = NEW_ARR_D(ident *, irg->obst, n_clobber);
227 res->attr.assem.text = text;
229 memcpy(res->attr.assem.input_constraints, inputs, sizeof(inputs[0]) * arity);
230 memcpy(res->attr.assem.output_constraints, outputs, sizeof(outputs[0]) * n_outs);
231 memcpy(res->attr.assem.clobbers, clobber, sizeof(clobber[0]) * n_clobber);
233 res = optimize_node(res);
234 IRN_VERIFY_IRG(res, irg);
238 /* --------------------------------------------- */
239 /* private interfaces, for professional use only */
240 /* --------------------------------------------- */
242 ir_node *new_rd_Start(dbg_info *db, ir_graph *irg, ir_node *block)
244 ir_graph *rem = current_ir_graph;
247 current_ir_graph = irg;
248 res = new_bd_Start(db, block);
249 current_ir_graph = rem;
254 ir_node *new_rd_End(dbg_info *db, ir_graph *irg, ir_node *block)
257 ir_graph *rem = current_ir_graph;
259 current_ir_graph = irg;
260 res = new_bd_End(db, block);
261 current_ir_graph = rem;
266 /* Creates a Phi node with all predecessors. Calling this constructor
267 is only allowed if the corresponding block is mature. */
268 ir_node *new_rd_Phi(dbg_info *db, ir_node *block, int arity, ir_node **in, ir_mode *mode)
271 ir_graph *rem = current_ir_graph;
273 current_ir_graph = get_Block_irg(block);
274 res = new_bd_Phi(db, block,arity, in, mode);
275 current_ir_graph = rem;
280 ir_node *new_rd_Const_type(dbg_info *db, ir_graph *irg, tarval *con, ir_type *tp)
283 ir_graph *rem = current_ir_graph;
285 current_ir_graph = irg;
286 res = new_bd_Const_type(db, con, tp);
287 current_ir_graph = rem;
290 } /* new_rd_Const_type */
292 ir_node *new_rd_Const(dbg_info *db, ir_graph *irg, tarval *con)
295 //#ifdef USE_ORIGINAL
296 ir_graph *rem = current_ir_graph;
298 current_ir_graph = irg;
299 res = new_bd_Const_type(db, con, firm_unknown_type);
300 current_ir_graph = rem;
302 // res = new_rd_Const_type(db, irg, con, firm_unknown_type);
308 ir_node *new_rd_Const_long(dbg_info *db, ir_graph *irg, ir_mode *mode, long value)
310 return new_rd_Const(db, irg, new_tarval_from_long(value, mode));
311 } /* new_rd_Const_long */
313 ir_node *new_rd_defaultProj(dbg_info *db, ir_node *arg, long max_proj)
315 return new_bd_defaultProj(db, arg, max_proj);
316 } /* new_rd_defaultProj */
318 ir_node *new_rd_simpleSel(dbg_info *db, ir_node *block, ir_node *store,
319 ir_node *objptr, ir_entity *ent)
322 ir_graph *rem = current_ir_graph;
324 current_ir_graph = get_Block_irg(block);
325 res = new_bd_Sel(db, block, store, objptr, 0, NULL, ent);
326 current_ir_graph = rem;
329 } /* new_rd_simpleSel */
331 ir_node *new_rd_SymConst_type(dbg_info *db, ir_graph *irg, ir_mode *mode,
332 symconst_symbol value, symconst_kind symkind,
336 ir_graph *rem = current_ir_graph;
337 ir_node *block = get_irg_start_block(irg);
339 current_ir_graph = irg;
340 res = new_bd_SymConst_type(db, block, mode, value, symkind, tp);
341 current_ir_graph = rem;
344 } /* new_rd_SymConst_type */
346 ir_node *new_rd_SymConst(dbg_info *db, ir_graph *irg, ir_mode *mode,
347 symconst_symbol value, symconst_kind symkind)
349 return new_rd_SymConst_type(db, irg, mode, value, symkind, firm_unknown_type);
350 } /* new_rd_SymConst */
352 ir_node *new_rd_SymConst_addr_ent(dbg_info *db, ir_graph *irg, ir_mode *mode, ir_entity *symbol, ir_type *tp)
355 sym.entity_p = symbol;
356 return new_rd_SymConst_type(db, irg, mode, sym, symconst_addr_ent, tp);
357 } /* new_rd_SymConst_addr_ent */
359 ir_node *new_rd_SymConst_ofs_ent(dbg_info *db, ir_graph *irg, ir_mode *mode, ir_entity *symbol, ir_type *tp)
362 sym.entity_p = symbol;
363 return new_rd_SymConst_type(db, irg, mode, sym, symconst_ofs_ent, tp);
364 } /* new_rd_SymConst_ofs_ent */
366 ir_node *new_rd_SymConst_type_tag(dbg_info *db, ir_graph *irg, ir_mode *mode, ir_type *symbol, ir_type *tp)
370 return new_rd_SymConst_type(db, irg, mode, sym, symconst_type_tag, tp);
371 } /* new_rd_SymConst_type_tag */
373 ir_node *new_rd_SymConst_size(dbg_info *db, ir_graph *irg, ir_mode *mode, ir_type *symbol, ir_type *tp)
377 return new_rd_SymConst_type(db, irg, mode, sym, symconst_type_size, tp);
378 } /* new_rd_SymConst_size */
380 ir_node *new_rd_SymConst_align(dbg_info *db, ir_graph *irg, ir_mode *mode, ir_type *symbol, ir_type *tp)
384 return new_rd_SymConst_type(db, irg, mode, sym, symconst_type_align, tp);
385 } /* new_rd_SymConst_align */
387 ir_node *new_rd_Sync(dbg_info *db, ir_node *block, int arity, ir_node *in[])
390 ir_graph *rem = current_ir_graph;
393 current_ir_graph = get_Block_irg(block);
394 res = new_bd_Sync(db, block);
395 current_ir_graph = rem;
397 for (i = 0; i < arity; ++i)
398 add_Sync_pred(res, in[i]);
403 ir_node *new_rd_ASM(dbg_info *db, ir_node *block,
404 int arity, ir_node *in[], ir_asm_constraint *inputs,
405 int n_outs, ir_asm_constraint *outputs,
406 int n_clobber, ident *clobber[], ident *text)
409 ir_graph *rem = current_ir_graph;
411 current_ir_graph = get_Block_irg(block);
412 res = new_bd_ASM(db, block, arity, in, inputs, n_outs, outputs, n_clobber, clobber, text);
413 current_ir_graph = rem;
418 ir_node *new_r_Start(ir_graph *irg, ir_node *block)
420 return new_rd_Start(NULL, irg, block);
422 ir_node *new_r_End(ir_graph *irg, ir_node *block)
424 return new_rd_End(NULL, irg, block);
426 ir_node *new_r_Const(ir_graph *irg, tarval *con)
428 return new_rd_Const(NULL, irg, con);
430 ir_node *new_r_Const_long(ir_graph *irg, ir_mode *mode, long value)
432 return new_rd_Const_long(NULL, irg, mode, value);
434 ir_node *new_r_Const_type(ir_graph *irg, tarval *con, ir_type *tp)
436 return new_rd_Const_type(NULL, irg, con, tp);
438 ir_node *new_r_SymConst(ir_graph *irg, ir_mode *mode, symconst_symbol value,
439 symconst_kind symkind)
441 return new_rd_SymConst(NULL, irg, mode, value, symkind);
443 ir_node *new_r_simpleSel(ir_node *block, ir_node *store, ir_node *objptr,
446 return new_rd_Sel(NULL, block, store, objptr, 0, NULL, ent);
448 ir_node *new_r_Phi(ir_node *block, int arity, ir_node **in, ir_mode *mode)
450 return new_rd_Phi(NULL, block, arity, in, mode);
452 ir_node *new_r_Sync(ir_node *block, int arity, ir_node *in[])
454 return new_rd_Sync(NULL, block, arity, in);
456 ir_node *new_r_defaultProj(ir_node *arg, long max_proj)
458 return new_rd_defaultProj(NULL, arg, max_proj);
460 ir_node *new_r_Bad(ir_graph *irg)
462 return get_irg_bad(irg);
464 ir_node *new_r_NoMem(ir_graph *irg)
466 return get_irg_no_mem(irg);
468 ir_node *new_r_ASM(ir_node *block,
469 int arity, ir_node *in[], ir_asm_constraint *inputs,
470 int n_outs, ir_asm_constraint *outputs,
471 int n_clobber, ident *clobber[], ident *text)
473 return new_rd_ASM(NULL, block, arity, in, inputs, n_outs, outputs, n_clobber, clobber, text);
476 /** ********************/
477 /** public interfaces */
478 /** construction tools */
480 ir_node *new_d_Start(dbg_info *db)
484 res = new_ir_node(db, current_ir_graph, current_ir_graph->current_block,
485 op_Start, mode_T, 0, NULL);
487 res = optimize_node(res);
488 IRN_VERIFY_IRG(res, current_ir_graph);
492 ir_node *new_d_End(dbg_info *db)
495 res = new_ir_node(db, current_ir_graph, current_ir_graph->current_block,
496 op_End, mode_X, -1, NULL);
497 res = optimize_node(res);
498 IRN_VERIFY_IRG(res, current_ir_graph);
503 /* ***********************************************************************/
504 /* Methods necessary for automatic Phi node creation */
506 ir_node *phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
507 ir_node *get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
508 ir_node *new_rd_Phi0 (ir_graph *irg, ir_node *block, ir_mode *mode)
509 ir_node *new_rd_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode, ir_node **in, int ins)
511 Call Graph: ( A ---> B == A "calls" B)
513 get_value mature_immBlock
521 get_r_value_internal |
525 new_rd_Phi0 new_rd_Phi_in
527 * *************************************************************************** */
529 /** Creates a Phi node with 0 predecessors. */
530 static inline ir_node *new_rd_Phi0(ir_graph *irg, ir_node *block, ir_mode *mode)
534 res = new_ir_node(NULL, irg, block, op_Phi, mode, 0, NULL);
535 IRN_VERIFY_IRG(res, irg);
541 * Internal constructor of a Phi node by a phi_merge operation.
543 * @param irg the graph on which the Phi will be constructed
544 * @param block the block in which the Phi will be constructed
545 * @param mode the mod eof the Phi node
546 * @param in the input array of the phi node
547 * @param ins number of elements in the input array
548 * @param phi0 in non-NULL: the Phi0 node in the same block that represents
549 * the value for which the new Phi is constructed
551 static inline ir_node *new_rd_Phi_in(ir_graph *irg, ir_node *block,
552 ir_mode *mode, ir_node **in, int ins,
556 ir_node *res, *known;
558 /* Allocate a new node on the obstack. The allocation copies the in
560 res = new_ir_node(NULL, irg, block, op_Phi, mode, ins, in);
561 res->attr.phi.u.backedge = new_backedge_arr(irg->obst, ins);
563 /* This loop checks whether the Phi has more than one predecessor.
564 If so, it is a real Phi node and we break the loop. Else the
565 Phi node merges the same definition on several paths and therefore
567 Note: We MUST consider Bad nodes, else we might get data flow cycles in dead loops! */
569 for (i = ins - 1; i >= 0; --i) {
572 in[i] = skip_Id(in[i]); /* increases the number of freed Phis. */
574 /* Optimize self referencing Phis: We can't detect them yet properly, as
575 they still refer to the Phi0 they will replace. So replace right now. */
576 if (phi0 && in[i] == phi0)
579 if (in[i] == res || in[i] == known)
588 /* i < 0: there is at most one predecessor, we don't need a phi node. */
591 edges_node_deleted(res, current_ir_graph);
592 obstack_free(current_ir_graph->obst, res);
594 /* If pred is a phi node we want to optimize it: If loops are matured in a bad
595 order, an enclosing Phi know may get superfluous. */
596 res = optimize_in_place_2(known);
598 exchange(known, res);
603 /* A undefined value, e.g., in unreachable code. */
607 res = optimize_node(res); /* This is necessary to add the node to the hash table for cse. */
608 IRN_VERIFY_IRG(res, irg);
609 /* Memory Phis in endless loops must be kept alive.
610 As we can't distinguish these easily we keep all of them alive. */
611 if (is_Phi(res) && mode == mode_M)
612 add_End_keepalive(get_irg_end(irg), res);
616 } /* new_rd_Phi_in */
618 static ir_node *get_r_value_internal(ir_node *block, int pos, ir_mode *mode);
620 static ir_node *phi_merge(ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins);
623 * Computes the predecessors for the real phi node, and then
624 * allocates and returns this node. The routine called to allocate the
625 * node might optimize it away and return a real value.
626 * This function must be called with an in-array of proper size.
628 static ir_node *phi_merge(ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
630 ir_node *prevBlock, *res, *phi0, *phi0_all;
633 /* If this block has no value at pos create a Phi0 and remember it
634 in graph_arr to break recursions.
635 Else we may not set graph_arr as there a later value is remembered. */
637 if (block->attr.block.graph_arr[pos] == NULL) {
638 ir_graph *irg = current_ir_graph;
640 if (block == get_irg_start_block(irg)) {
641 /* Collapsing to Bad tarvals is no good idea.
642 So we call a user-supplied routine here that deals with this
643 case as appropriate for the given language. Sorrily the only
644 help we can give here is the position.
646 Even if all variables are defined before use, it can happen that
647 we get to the start block, if a Cond has been replaced by a tuple
648 (bad, jmp). In this case we call the function needlessly,
649 eventually generating an non existent error.
650 However, this SHOULD NOT HAPPEN, as bad control flow nodes are
651 intercepted before recurring.
653 if (default_initialize_local_variable != NULL) {
654 ir_node *rem = get_cur_block();
656 set_cur_block(block);
657 block->attr.block.graph_arr[pos] = default_initialize_local_variable(irg, mode, pos - 1);
660 block->attr.block.graph_arr[pos] = new_Unknown(mode);
662 return block->attr.block.graph_arr[pos];
664 phi0 = new_rd_Phi0(irg, block, mode);
665 block->attr.block.graph_arr[pos] = phi0;
669 /* This loop goes to all predecessor blocks of the block the Phi node
670 is in and there finds the operands of the Phi node by calling
671 get_r_value_internal. */
672 for (i = 1; i <= ins; ++i) {
673 ir_node *cf_pred = block->in[i];
674 ir_node *prevCfOp = skip_Proj(cf_pred);
676 if (is_Bad(prevCfOp)) {
677 /* In case a Cond has been optimized we would get right to the start block
678 with an invalid definition. */
679 nin[i-1] = new_Bad();
682 prevBlock = prevCfOp->in[0]; /* go past control flow op to prev block */
684 if (!is_Bad(prevBlock)) {
685 nin[i-1] = get_r_value_internal(prevBlock, pos, mode);
687 nin[i-1] = new_Bad();
691 /* We want to pass the Phi0 node to the constructor: this finds additional
692 optimization possibilities.
693 The Phi0 node either is allocated in this function, or it comes from
694 a former call to get_r_value_internal(). In this case we may not yet
695 exchange phi0, as this is done in mature_immBlock(). */
697 phi0_all = block->attr.block.graph_arr[pos];
698 if (! is_Phi0(phi0_all) ||
699 get_irn_arity(phi0_all) != 0 ||
700 get_nodes_block(phi0_all) != block)
706 /* After collecting all predecessors into the array nin a new Phi node
707 with these predecessors is created. This constructor contains an
708 optimization: If all predecessors of the Phi node are identical it
709 returns the only operand instead of a new Phi node. */
710 res = new_rd_Phi_in(current_ir_graph, block, mode, nin, ins, phi0_all);
712 /* In case we allocated a Phi0 node at the beginning of this procedure,
713 we need to exchange this Phi0 with the real Phi. */
716 block->attr.block.graph_arr[pos] = res;
723 * This function returns the last definition of a value. In case
724 * this value was last defined in a previous block, Phi nodes are
725 * inserted. If the part of the firm graph containing the definition
726 * is not yet constructed, a dummy Phi node is returned.
728 * @param block the current block
729 * @param pos the value number of the value searched
730 * @param mode the mode of this value (needed for Phi construction)
732 static ir_node *get_r_value_internal(ir_node *block, int pos, ir_mode *mode)
735 /* There are 4 cases to treat.
737 1. The block is not mature and we visit it the first time. We can not
738 create a proper Phi node, therefore a Phi0, i.e., a Phi without
739 predecessors is returned. This node is added to the linked list (block
740 attribute "phis") of the containing block to be completed when this block is
741 matured. (Completion will add a new Phi and turn the Phi0 into an Id
744 2. The value is already known in this block, graph_arr[pos] is set and we
745 visit the block the first time. We can return the value without
746 creating any new nodes.
748 3. The block is mature and we visit it the first time. A Phi node needs
749 to be created (phi_merge). If the Phi is not needed, as all it's
750 operands are the same value reaching the block through different
751 paths, it's optimized away and the value itself is returned.
753 4. The block is mature, and we visit it the second time. Now two
754 subcases are possible:
755 * The value was computed completely the last time we were here. This
756 is the case if there is no loop. We can return the proper value.
757 * The recursion that visited this node and set the flag did not
758 return yet. We are computing a value in a loop and need to
759 break the recursion. This case only happens if we visited
760 the same block with phi_merge before, which inserted a Phi0.
761 So we return the Phi0.
764 /* case 4 -- already visited. */
765 if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) {
766 /* As phi_merge allocates a Phi0 this value is always defined. Here
767 is the critical difference of the two algorithms. */
768 assert(block->attr.block.graph_arr[pos]);
769 return block->attr.block.graph_arr[pos];
772 /* visited the first time */
773 set_irn_visited(block, get_irg_visited(current_ir_graph));
775 /* Get the local valid value */
776 res = block->attr.block.graph_arr[pos];
778 /* case 2 -- If the value is actually computed, return it. */
782 if (block->attr.block.is_matured) { /* case 3 */
784 /* The Phi has the same amount of ins as the corresponding block. */
785 int ins = get_irn_arity(block);
787 NEW_ARR_A(ir_node *, nin, ins);
789 /* Phi merge collects the predecessors and then creates a node. */
790 res = phi_merge(block, pos, mode, nin, ins);
792 } else { /* case 1 */
793 /* The block is not mature, we don't know how many in's are needed. A Phi
794 with zero predecessors is created. Such a Phi node is called Phi0
795 node. The Phi0 is then added to the list of Phi0 nodes in this block
796 to be matured by mature_immBlock later.
797 The Phi0 has to remember the pos of it's internal value. If the real
798 Phi is computed, pos is used to update the array with the local
800 res = new_rd_Phi0(current_ir_graph, block, mode);
801 res->attr.phi.u.pos = pos;
802 res->attr.phi.next = block->attr.block.phis;
803 block->attr.block.phis = res;
806 assert(is_ir_node(res) && "phi_merge() failed to construct a definition");
808 /* The local valid value is available now. */
809 block->attr.block.graph_arr[pos] = res;
812 } /* get_r_value_internal */
814 /* ************************************************************************** */
817 * Finalize a Block node, when all control flows are known.
818 * Acceptable parameters are only Block nodes.
820 void mature_immBlock(ir_node *block)
826 assert(is_Block(block));
827 if (!get_Block_matured(block)) {
828 ir_graph *irg = current_ir_graph;
830 ins = ARR_LEN(block->in) - 1;
831 /* Fix block parameters */
832 block->attr.block.backedge = new_backedge_arr(irg->obst, ins);
834 /* An array for building the Phi nodes. */
835 NEW_ARR_A(ir_node *, nin, ins);
837 /* Traverse a chain of Phi nodes attached to this block and mature
839 for (n = block->attr.block.phis; n; n = next) {
840 inc_irg_visited(irg);
841 next = n->attr.phi.next;
842 exchange(n, phi_merge(block, n->attr.phi.u.pos, n->mode, nin, ins));
845 block->attr.block.is_matured = 1;
847 /* Now, as the block is a finished Firm node, we can optimize it.
848 Since other nodes have been allocated since the block was created
849 we can not free the node on the obstack. Therefore we have to call
851 Unfortunately the optimization does not change a lot, as all allocated
852 nodes refer to the unoptimized node.
853 We can call optimize_in_place_2(), as global cse has no effect on blocks. */
854 block = optimize_in_place_2(block);
855 IRN_VERIFY_IRG(block, irg);
857 } /* mature_immBlock */
859 ir_node *new_d_Phi(dbg_info *db, int arity, ir_node **in, ir_mode *mode)
861 return new_bd_Phi(db, current_ir_graph->current_block, arity, in, mode);
864 ir_node *new_d_Const(dbg_info *db, tarval *con)
866 return new_bd_Const(db, con);
869 ir_node *new_d_Const_long(dbg_info *db, ir_mode *mode, long value)
871 return new_bd_Const_long(db, mode, value);
872 } /* new_d_Const_long */
874 ir_node *new_d_Const_type(dbg_info *db, tarval *con, ir_type *tp)
876 return new_bd_Const_type(db, con, tp);
877 } /* new_d_Const_type */
880 ir_node *new_d_defaultProj(dbg_info *db, ir_node *arg, long max_proj)
883 assert(arg->op == op_Cond);
884 arg->attr.cond.default_proj = max_proj;
885 res = new_d_Proj(db, arg, mode_X, max_proj);
887 } /* new_d_defaultProj */
889 ir_node *new_d_simpleSel(dbg_info *db, ir_node *store, ir_node *objptr, ir_entity *ent)
890 /* GL: objptr was called frame before. Frame was a bad choice for the name
891 as the operand could as well be a pointer to a dynamic object. */
893 return new_bd_Sel(db, current_ir_graph->current_block,
894 store, objptr, 0, NULL, ent);
895 } /* new_d_simpleSel */
897 ir_node *new_d_SymConst_type(dbg_info *db, ir_mode *mode, symconst_symbol value, symconst_kind kind, ir_type *tp)
899 return new_bd_SymConst_type(db, get_irg_start_block(current_ir_graph), mode,
901 } /* new_d_SymConst_type */
903 ir_node *new_d_SymConst(dbg_info *db, ir_mode *mode, symconst_symbol value, symconst_kind kind)
905 return new_bd_SymConst_type(db, get_irg_start_block(current_ir_graph), mode,
906 value, kind, firm_unknown_type);
907 } /* new_d_SymConst */
909 ir_node *new_d_Sync(dbg_info *db, int arity, ir_node *in[])
911 return new_rd_Sync(db, current_ir_graph->current_block, arity, in);
914 ir_node *new_d_ASM(dbg_info *db, int arity, ir_node *in[], ir_asm_constraint *inputs,
915 int n_outs, ir_asm_constraint *outputs, int n_clobber,
916 ident *clobber[], ident *text)
918 return new_bd_ASM(db, current_ir_graph->current_block, arity, in, inputs, n_outs, outputs, n_clobber, clobber, text);
921 /* ********************************************************************* */
922 /* Comfortable interface with automatic Phi node construction. */
923 /* (Uses also constructors of ?? interface, except new_Block. */
924 /* ********************************************************************* */
926 /* Block construction */
927 /* immature Block without predecessors */
928 ir_node *new_d_immBlock(dbg_info *db)
932 assert(get_irg_phase_state(current_ir_graph) == phase_building);
933 /* creates a new dynamic in-array as length of in is -1 */
934 res = new_ir_node(db, current_ir_graph, NULL, op_Block, mode_BB, -1, NULL);
936 /* macroblock head */
939 res->attr.block.is_matured = 0;
940 res->attr.block.is_dead = 0;
941 res->attr.block.is_mb_head = 1;
942 res->attr.block.irg.irg = current_ir_graph;
943 res->attr.block.backedge = NULL;
944 res->attr.block.in_cg = NULL;
945 res->attr.block.cg_backedge = NULL;
946 res->attr.block.extblk = NULL;
947 res->attr.block.region = NULL;
948 res->attr.block.mb_depth = 0;
949 res->attr.block.entity = NULL;
951 set_Block_block_visited(res, 0);
953 /* Create and initialize array for Phi-node construction. */
954 res->attr.block.graph_arr = NEW_ARR_D(ir_node *, current_ir_graph->obst,
955 current_ir_graph->n_loc);
956 memset(res->attr.block.graph_arr, 0, sizeof(ir_node *)*current_ir_graph->n_loc);
958 /* Immature block may not be optimized! */
959 IRN_VERIFY_IRG(res, current_ir_graph);
962 } /* new_d_immBlock */
964 ir_node *new_immBlock(void)
966 return new_d_immBlock(NULL);
969 /* immature PartBlock with its predecessors */
970 ir_node *new_d_immPartBlock(dbg_info *db, ir_node *pred_jmp)
972 ir_node *res = new_d_immBlock(db);
973 ir_node *blk = get_nodes_block(pred_jmp);
975 res->in[0] = blk->in[0];
976 assert(res->in[0] != NULL);
977 add_immBlock_pred(res, pred_jmp);
979 res->attr.block.is_mb_head = 0;
980 res->attr.block.mb_depth = blk->attr.block.mb_depth + 1;
983 } /* new_d_immPartBlock */
985 ir_node *new_immPartBlock(ir_node *pred_jmp)
987 return new_d_immPartBlock(NULL, pred_jmp);
988 } /* new_immPartBlock */
990 /* add an edge to a jmp/control flow node */
991 void add_immBlock_pred(ir_node *block, ir_node *jmp)
993 int n = ARR_LEN(block->in) - 1;
995 assert(is_Block(block) && "Error: Must be a Block");
996 assert(!block->attr.block.is_matured && "Error: Block already matured!\n");
997 assert(block->attr.block.is_mb_head && "Error: Cannot add a predecessor to a PartBlock");
998 assert(is_ir_node(jmp));
1000 ARR_APP1(ir_node *, block->in, jmp);
1002 hook_set_irn_n(block, n, jmp, NULL);
1003 } /* add_immBlock_pred */
1005 /* changing the current block */
1006 void set_cur_block(ir_node *target)
1008 current_ir_graph->current_block = target;
1009 } /* set_cur_block */
1011 /* ************************ */
1012 /* parameter administration */
1014 /* get a value from the parameter array from the current block by its index */
1015 ir_node *get_d_value(dbg_info *db, int pos, ir_mode *mode)
1017 ir_graph *irg = current_ir_graph;
1018 assert(get_irg_phase_state(irg) == phase_building);
1019 inc_irg_visited(irg);
1024 return get_r_value_internal(irg->current_block, pos + 1, mode);
1027 /* get a value from the parameter array from the current block by its index */
1028 ir_node *get_value(int pos, ir_mode *mode)
1030 return get_d_value(NULL, pos, mode);
1034 * helper function for guess_mode: recursively look for a definition for
1035 * local variable @p pos, returns its mode if found.
1037 static ir_mode *guess_recursively(ir_node *block, int pos)
1043 if (irn_visited(block))
1045 mark_irn_visited(block);
1047 /* already have a defintion -> we can simply look at its mode */
1048 value = block->attr.block.graph_arr[pos];
1050 return get_irn_mode(value);
1052 /* now we try to guess, by looking at the predecessor blocks */
1053 n_preds = get_irn_arity(block);
1054 for (i = 0; i < n_preds; ++i) {
1055 ir_node *pred_block = get_Block_cfgpred_block(block, i);
1056 ir_mode *mode = guess_recursively(pred_block, pos);
1061 /* no way to guess */
1065 ir_mode *ir_guess_mode(int pos)
1067 ir_graph *irg = current_ir_graph;
1068 ir_node *block = irg->current_block;
1069 ir_node *value = block->attr.block.graph_arr[pos+1];
1072 /* already have a defintion -> we can simply look at its mode */
1074 return get_irn_mode(value);
1076 ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
1077 inc_irg_visited(current_ir_graph);
1078 mode = guess_recursively(block, pos+1);
1079 ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
1084 /* set a value at position pos in the parameter array from the current block */
1085 void set_value(int pos, ir_node *value)
1087 ir_graph *irg = current_ir_graph;
1088 assert(get_irg_phase_state(irg) == phase_building);
1090 assert(pos+1 < irg->n_loc);
1091 assert(is_ir_node(value));
1092 irg->current_block->attr.block.graph_arr[pos + 1] = value;
1095 /* Find the value number for a node in the current block.*/
1096 int find_value(ir_node *value)
1099 ir_node *bl = current_ir_graph->current_block;
1101 for (i = ARR_LEN(bl->attr.block.graph_arr) - 1; i >= 1; --i)
1102 if (bl->attr.block.graph_arr[i] == value)
1107 /* get the current store */
1108 ir_node *get_store(void)
1110 ir_graph *irg = current_ir_graph;
1112 assert(get_irg_phase_state(irg) == phase_building);
1113 /* GL: one could call get_value instead */
1114 inc_irg_visited(irg);
1115 return get_r_value_internal(irg->current_block, 0, mode_M);
1118 /* set the current store: handles automatic Sync construction for Load nodes */
1119 void set_store(ir_node *store)
1121 ir_node *load, *pload, *pred, *in[2];
1123 assert(get_irg_phase_state(current_ir_graph) == phase_building);
1124 /* Beware: due to dead code elimination, a store might become a Bad node even in
1125 the construction phase. */
1126 assert((get_irn_mode(store) == mode_M || is_Bad(store)) && "storing non-memory node");
1128 if (get_opt_auto_create_sync()) {
1129 /* handle non-volatile Load nodes by automatically creating Sync's */
1130 load = skip_Proj(store);
1131 if (is_Load(load) && get_Load_volatility(load) == volatility_non_volatile) {
1132 pred = get_Load_mem(load);
1134 if (is_Sync(pred)) {
1135 /* a Load after a Sync: move it up */
1136 ir_node *mem = skip_Proj(get_Sync_pred(pred, 0));
1138 set_Load_mem(load, get_memop_mem(mem));
1139 add_Sync_pred(pred, store);
1142 pload = skip_Proj(pred);
1143 if (is_Load(pload) && get_Load_volatility(pload) == volatility_non_volatile) {
1144 /* a Load after a Load: create a new Sync */
1145 set_Load_mem(load, get_Load_mem(pload));
1149 store = new_Sync(2, in);
1154 current_ir_graph->current_block->attr.block.graph_arr[0] = store;
1157 void keep_alive(ir_node *ka)
1159 add_End_keepalive(get_irg_end(current_ir_graph), ka);
1162 /* --- Useful access routines --- */
1163 /* Returns the current block of the current graph. To set the current
1164 block use set_cur_block. */
1165 ir_node *get_cur_block(void)
1167 return get_irg_current_block(current_ir_graph);
1168 } /* get_cur_block */
1170 /* Returns the frame type of the current graph */
1171 ir_type *get_cur_frame_type(void)
1173 return get_irg_frame_type(current_ir_graph);
1174 } /* get_cur_frame_type */
1177 /* ********************************************************************* */
1180 /* call once for each run of the library */
1181 void ir_set_uninitialized_local_variable_func(
1182 uninitialized_local_variable_func_t *func)
1184 default_initialize_local_variable = func;
1187 void irg_finalize_cons(ir_graph *irg)
1189 set_irg_phase_state(irg, phase_high);
1192 void irp_finalize_cons(void)
1195 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
1196 irg_finalize_cons(get_irp_irg(i));
1198 irp->phase_state = phase_high;
1201 ir_node *new_Start(void)
1203 return new_d_Start(NULL);
1205 ir_node *new_End(void)
1207 return new_d_End(NULL);
1209 ir_node *new_Const(tarval *con)
1211 return new_d_Const(NULL, con);
1214 ir_node *new_Const_long(ir_mode *mode, long value)
1216 return new_d_Const_long(NULL, mode, value);
1219 ir_node *new_Const_type(tarval *con, ir_type *tp)
1221 return new_d_Const_type(NULL, con, tp);
1224 ir_node *new_SymConst_type(ir_mode *mode, symconst_symbol value, symconst_kind kind, ir_type *type)
1226 return new_d_SymConst_type(NULL, mode, value, kind, type);
1228 ir_node *new_SymConst(ir_mode *mode, symconst_symbol value, symconst_kind kind)
1230 return new_d_SymConst(NULL, mode, value, kind);
1232 ir_node *new_simpleSel(ir_node *store, ir_node *objptr, ir_entity *ent)
1234 return new_d_simpleSel(NULL, store, objptr, ent);
1236 ir_node *new_Phi(int arity, ir_node **in, ir_mode *mode)
1238 return new_d_Phi(NULL, arity, in, mode);
1240 ir_node *new_Sync(int arity, ir_node *in[])
1242 return new_d_Sync(NULL, arity, in);
1244 ir_node *new_defaultProj(ir_node *arg, long max_proj)
1246 return new_d_defaultProj(NULL, arg, max_proj);
1248 ir_node *new_Bad(void)
1250 return get_irg_bad(current_ir_graph);
1252 ir_node *new_NoMem(void)
1254 return get_irg_no_mem(current_ir_graph);
1256 ir_node *new_ASM(int arity, ir_node *in[], ir_asm_constraint *inputs,
1257 int n_outs, ir_asm_constraint *outputs,
1258 int n_clobber, ident *clobber[], ident *text)
1260 return new_d_ASM(NULL, arity, in, inputs, n_outs, outputs, n_clobber, clobber, text);
1263 /* create a new anchor node */
1264 ir_node *new_Anchor(ir_graph *irg)
1266 ir_node *in[anchor_last];
1268 memset(in, 0, sizeof(in));
1269 res = new_ir_node(NULL, irg, NULL, op_Anchor, mode_ANY, anchor_last, in);
1271 /* hack to get get_irn_irg working: set block to ourself and allow
1272 * get_Block_irg for anchor */
1273 res->attr.irg.irg = irg;