2 * Copyright (C) 1995-2011 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
25 * Michael Beck, Matthias Braun
31 #include "irgraph_t.h"
41 #include "irbackedge_t.h"
43 #include "iredges_t.h"
47 #include "gen_ir_cons.c.inl"
50 * Language dependent variable initialization callback.
52 static uninitialized_local_variable_func_t *default_initialize_local_variable = NULL;
54 ir_node *new_rd_Const_long(dbg_info *db, ir_graph *irg, ir_mode *mode,
57 return new_rd_Const(db, irg, new_tarval_from_long(value, mode));
60 ir_node *new_rd_defaultProj(dbg_info *db, ir_node *arg, long max_proj)
65 arg->attr.cond.default_proj = max_proj;
66 res = new_rd_Proj(db, arg, mode_X, max_proj);
70 ir_node *new_rd_ASM(dbg_info *db, ir_node *block, int arity, ir_node *in[],
71 ir_asm_constraint *inputs, int n_outs,
72 ir_asm_constraint *outputs, int n_clobber,
73 ident *clobber[], ident *text)
75 ir_graph *irg = get_irn_irg(block);
76 ir_node *res = new_ir_node(db, irg, block, op_ASM, mode_T, arity, in);
78 res->attr.assem.pin_state = op_pin_state_pinned;
79 res->attr.assem.input_constraints
80 = NEW_ARR_D(ir_asm_constraint, irg->obst, arity);
81 res->attr.assem.output_constraints
82 = NEW_ARR_D(ir_asm_constraint, irg->obst, n_outs);
83 res->attr.assem.clobbers = NEW_ARR_D(ident *, irg->obst, n_clobber);
84 res->attr.assem.text = text;
86 memcpy(res->attr.assem.input_constraints, inputs, sizeof(inputs[0]) * arity);
87 memcpy(res->attr.assem.output_constraints, outputs, sizeof(outputs[0]) * n_outs);
88 memcpy(res->attr.assem.clobbers, clobber, sizeof(clobber[0]) * n_clobber);
90 res = optimize_node(res);
91 irn_verify_irg(res, irg);
95 ir_node *new_rd_simpleSel(dbg_info *db, ir_node *block, ir_node *store,
96 ir_node *objptr, ir_entity *ent)
98 return new_rd_Sel(db, block, store, objptr, 0, NULL, ent);
101 ir_node *new_rd_SymConst(dbg_info *db, ir_graph *irg, ir_mode *mode,
102 symconst_symbol value, symconst_kind symkind)
104 ir_node *block = get_irg_start_block(irg);
105 ir_node *res = new_ir_node(db, irg, block, op_SymConst, mode, 0, NULL);
106 res->attr.symc.kind = symkind;
107 res->attr.symc.sym = value;
109 res = optimize_node(res);
110 irn_verify_irg(res, irg);
114 ir_node *new_rd_SymConst_addr_ent(dbg_info *db, ir_graph *irg, ir_mode *mode, ir_entity *symbol)
117 sym.entity_p = symbol;
118 return new_rd_SymConst(db, irg, mode, sym, symconst_addr_ent);
121 ir_node *new_rd_SymConst_ofs_ent(dbg_info *db, ir_graph *irg, ir_mode *mode, ir_entity *symbol)
124 sym.entity_p = symbol;
125 return new_rd_SymConst(db, irg, mode, sym, symconst_ofs_ent);
128 ir_node *new_rd_SymConst_type_tag(dbg_info *db, ir_graph *irg, ir_mode *mode, ir_type *symbol)
132 return new_rd_SymConst(db, irg, mode, sym, symconst_type_tag);
135 ir_node *new_rd_SymConst_size(dbg_info *db, ir_graph *irg, ir_mode *mode, ir_type *symbol)
139 return new_rd_SymConst(db, irg, mode, sym, symconst_type_size);
142 ir_node *new_rd_SymConst_align(dbg_info *db, ir_graph *irg, ir_mode *mode, ir_type *symbol)
146 return new_rd_SymConst(db, irg, mode, sym, symconst_type_align);
149 ir_node *new_r_Const_long(ir_graph *irg, ir_mode *mode, long value)
151 return new_rd_Const_long(NULL, irg, mode, value);
153 ir_node *new_r_SymConst(ir_graph *irg, ir_mode *mode, symconst_symbol value,
154 symconst_kind symkind)
156 return new_rd_SymConst(NULL, irg, mode, value, symkind);
158 ir_node *new_r_simpleSel(ir_node *block, ir_node *store, ir_node *objptr,
161 return new_rd_Sel(NULL, block, store, objptr, 0, NULL, ent);
163 ir_node *new_r_defaultProj(ir_node *arg, long max_proj)
165 return new_rd_defaultProj(NULL, arg, max_proj);
167 ir_node *new_r_ASM(ir_node *block,
168 int arity, ir_node *in[], ir_asm_constraint *inputs,
169 int n_outs, ir_asm_constraint *outputs,
170 int n_clobber, ident *clobber[], ident *text)
172 return new_rd_ASM(NULL, block, arity, in, inputs, n_outs, outputs, n_clobber, clobber, text);
175 /** Creates a Phi node with 0 predecessors. */
176 static inline ir_node *new_rd_Phi0(dbg_info *dbgi, ir_node *block,
177 ir_mode *mode, int pos)
179 ir_graph *irg = get_irn_irg(block);
180 ir_node *res = new_ir_node(dbgi, irg, block, op_Phi, mode, 0, NULL);
181 res->attr.phi.u.pos = pos;
182 irn_verify_irg(res, irg);
186 static ir_node *get_r_value_internal(ir_node *block, int pos, ir_mode *mode);
189 * Computes the predecessors for the real phi node, and then
190 * allocates and returns this node. The routine called to allocate the
191 * node might optimize it away and return a real value.
192 * This function must be called with an in-array of proper size.
194 static ir_node *set_phi_arguments(ir_node *phi, int pos)
196 ir_node *block = get_nodes_block(phi);
197 ir_graph *irg = get_irn_irg(block);
198 int arity = get_irn_arity(block);
199 ir_node **in = ALLOCAN(ir_node*, arity);
200 ir_mode *mode = get_irn_mode(phi);
201 ir_node *phi_value = NULL;
202 bool no_phi_value = false;
205 /* This loop goes to all predecessor blocks of the block the Phi node
206 is in and there finds the operands of the Phi node by calling
207 get_r_value_internal. */
208 for (i = 0; i < arity; ++i) {
209 ir_node *cfgpred = get_Block_cfgpred_block(block, i);
211 if (is_Bad(cfgpred)) {
212 value = new_r_Bad(irg);
214 value = get_r_value_internal(cfgpred, pos, mode);
216 if (!no_phi_value && value != phi) {
217 if (phi_value == NULL) {
219 } else if (value != phi_value) {
227 if (phi_value != NULL && !no_phi_value) {
228 exchange(phi, phi_value);
232 phi->attr.phi.u.backedge = new_backedge_arr(irg->obst, arity);
233 set_irn_in(phi, arity, in);
234 set_irn_op(phi, op_Phi);
236 phi = optimize_in_place_2(phi);
237 irn_verify_irg(phi, irg);
239 /* Memory Phis in endless loops must be kept alive.
240 As we can't distinguish these easily we keep all of them alive. */
241 if (is_Phi(phi) && mode == mode_M)
242 add_End_keepalive(get_irg_end(irg), phi);
247 * This function returns the last definition of a value. In case
248 * this value was last defined in a previous block, Phi nodes are
249 * inserted. If the part of the firm graph containing the definition
250 * is not yet constructed, a dummy Phi node is returned.
252 * @param block the current block
253 * @param pos the value number of the value searched
254 * @param mode the mode of this value (needed for Phi construction)
256 static ir_node *get_r_value_internal(ir_node *block, int pos, ir_mode *mode)
258 ir_node *res = block->attr.block.graph_arr[pos];
262 /* in a matured block we can immediated determine the phi arguments */
263 if (block->attr.block.is_matured) {
264 int arity = get_irn_arity(block);
265 /* no predecessors: use unknown value */
266 if (arity == 0 && block == get_irg_start_block(get_irn_irg(block))) {
267 ir_graph *irg = get_irn_irg(block);
268 if (default_initialize_local_variable != NULL) {
269 ir_node *rem = get_r_cur_block(irg);
270 set_r_cur_block(irg, block);
271 res = default_initialize_local_variable(irg, mode, pos - 1);
272 set_r_cur_block(irg, rem);
274 res = new_r_Unknown(irg, mode);
276 /* one predecessor just use its value */
277 } else if (arity == 1) {
278 ir_node *cfgpred = get_Block_cfgpred_block(block, 0);
279 if (is_Bad(cfgpred)) {
282 res = get_r_value_internal(cfgpred, pos, mode);
284 /* multiple predecessors construct Phi */
286 res = new_rd_Phi0(NULL, block, mode, pos);
287 /* enter phi0 into our variable value table to break cycles
288 * arising from set_phi_arguments */
289 block->attr.block.graph_arr[pos] = res;
290 res = set_phi_arguments(res, pos);
293 /* in case of immature block we have to keep a Phi0 */
294 res = new_rd_Phi0(NULL, block, mode, pos);
295 /* enqueue phi so we can set arguments once the block matures */
296 res->attr.phi.next = block->attr.block.phis;
297 block->attr.block.phis = res;
299 block->attr.block.graph_arr[pos] = res;
303 /* ************************************************************************** */
306 * Finalize a Block node, when all control flows are known.
307 * Acceptable parameters are only Block nodes.
309 void mature_immBlock(ir_node *block)
316 assert(is_Block(block));
317 if (get_Block_matured(block))
320 irg = get_irn_irg(block);
321 n_preds = ARR_LEN(block->in) - 1;
322 /* Fix block parameters */
323 block->attr.block.backedge = new_backedge_arr(irg->obst, n_preds);
325 /* Traverse a chain of Phi nodes attached to this block and mature
327 for (phi = block->attr.block.phis; phi != NULL; phi = next) {
329 int pos = phi->attr.phi.u.pos;
331 next = phi->attr.phi.next;
332 new_value = set_phi_arguments(phi, pos);
333 if (block->attr.block.graph_arr[pos] == phi) {
334 block->attr.block.graph_arr[pos] = new_value;
338 block->attr.block.is_matured = 1;
340 /* Now, as the block is a finished Firm node, we can optimize it.
341 Since other nodes have been allocated since the block was created
342 we can not free the node on the obstack. Therefore we have to call
344 Unfortunately the optimization does not change a lot, as all allocated
345 nodes refer to the unoptimized node.
346 We can call optimize_in_place_2(), as global cse has no effect on blocks.
348 block = optimize_in_place_2(block);
349 irn_verify_irg(block, irg);
352 ir_node *new_d_Const_long(dbg_info *db, ir_mode *mode, long value)
354 assert(get_irg_phase_state(current_ir_graph) == phase_building);
355 return new_rd_Const_long(db, current_ir_graph, mode, value);
358 ir_node *new_d_defaultProj(dbg_info *db, ir_node *arg, long max_proj)
361 assert(is_Cond(arg) || is_Bad(arg));
362 assert(get_irg_phase_state(current_ir_graph) == phase_building);
364 arg->attr.cond.default_proj = max_proj;
365 res = new_d_Proj(db, arg, mode_X, max_proj);
369 ir_node *new_d_simpleSel(dbg_info *db, ir_node *store, ir_node *objptr,
372 assert(get_irg_phase_state(current_ir_graph) == phase_building);
373 return new_rd_Sel(db, current_ir_graph->current_block,
374 store, objptr, 0, NULL, ent);
377 ir_node *new_d_SymConst(dbg_info *db, ir_mode *mode, symconst_symbol value,
380 assert(get_irg_phase_state(current_ir_graph) == phase_building);
381 return new_rd_SymConst(db, current_ir_graph, mode, value, kind);
384 ir_node *new_d_ASM(dbg_info *db, int arity, ir_node *in[],
385 ir_asm_constraint *inputs,
386 int n_outs, ir_asm_constraint *outputs, int n_clobber,
387 ident *clobber[], ident *text)
389 assert(get_irg_phase_state(current_ir_graph) == phase_building);
390 return new_rd_ASM(db, current_ir_graph->current_block, arity, in, inputs,
391 n_outs, outputs, n_clobber, clobber, text);
394 ir_node *new_rd_strictConv(dbg_info *dbgi, ir_node *block, ir_node * irn_op, ir_mode * mode)
397 ir_graph *irg = get_Block_irg(block);
402 res = new_ir_node(dbgi, irg, block, op_Conv, mode, 1, in);
403 res->attr.conv.strict = 1;
404 res = optimize_node(res);
405 irn_verify_irg(res, irg);
409 ir_node *new_r_strictConv(ir_node *block, ir_node * irn_op, ir_mode * mode)
411 return new_rd_strictConv(NULL, block, irn_op, mode);
414 ir_node *new_d_strictConv(dbg_info *dbgi, ir_node * irn_op, ir_mode * mode)
417 assert(get_irg_phase_state(current_ir_graph) == phase_building);
418 res = new_rd_strictConv(dbgi, current_ir_graph->current_block, irn_op, mode);
422 ir_node *new_strictConv(ir_node * irn_op, ir_mode * mode)
424 return new_d_strictConv(NULL, irn_op, mode);
427 ir_node *new_rd_DivRL(dbg_info *dbgi, ir_node *block, ir_node * irn_mem, ir_node * irn_left, ir_node * irn_right, ir_mode* resmode, op_pin_state pin_state)
430 ir_graph *irg = get_Block_irg(block);
437 res = new_ir_node(dbgi, irg, block, op_Div, mode_T, 3, in);
438 res->attr.divmod.resmode = resmode;
439 res->attr.divmod.no_remainder = 1;
440 res->attr.divmod.exc.pin_state = pin_state;
441 res = optimize_node(res);
442 irn_verify_irg(res, irg);
446 ir_node *new_r_DivRL(ir_node *block, ir_node * irn_mem, ir_node * irn_left, ir_node * irn_right, ir_mode* resmode, op_pin_state pin_state)
448 return new_rd_DivRL(NULL, block, irn_mem, irn_left, irn_right, resmode, pin_state);
451 ir_node *new_d_DivRL(dbg_info *dbgi, ir_node * irn_mem, ir_node * irn_left, ir_node * irn_right, ir_mode* resmode, op_pin_state pin_state)
454 assert(get_irg_phase_state(current_ir_graph) == phase_building);
455 res = new_rd_DivRL(dbgi, current_ir_graph->current_block, irn_mem, irn_left, irn_right, resmode, pin_state);
459 ir_node *new_DivRL(ir_node * irn_mem, ir_node * irn_left, ir_node * irn_right, ir_mode* resmode, op_pin_state pin_state)
461 return new_d_DivRL(NULL, irn_mem, irn_left, irn_right, resmode, pin_state);
464 ir_node *new_rd_immBlock(dbg_info *dbgi, ir_graph *irg)
468 assert(get_irg_phase_state(irg) == phase_building);
469 /* creates a new dynamic in-array as length of in is -1 */
470 res = new_ir_node(dbgi, irg, NULL, op_Block, mode_BB, -1, NULL);
472 res->attr.block.is_matured = 0;
473 res->attr.block.is_dead = 0;
474 res->attr.block.irg.irg = irg;
475 res->attr.block.backedge = NULL;
476 res->attr.block.in_cg = NULL;
477 res->attr.block.cg_backedge = NULL;
478 res->attr.block.extblk = NULL;
479 res->attr.block.region = NULL;
480 res->attr.block.entity = NULL;
482 set_Block_block_visited(res, 0);
484 /* Create and initialize array for Phi-node construction. */
485 res->attr.block.graph_arr = NEW_ARR_D(ir_node *, irg->obst, irg->n_loc);
486 memset(res->attr.block.graph_arr, 0, sizeof(ir_node*) * irg->n_loc);
488 /* Immature block may not be optimized! */
489 irn_verify_irg(res, irg);
494 ir_node *new_r_immBlock(ir_graph *irg)
496 return new_rd_immBlock(NULL, irg);
499 ir_node *new_d_immBlock(dbg_info *dbgi)
501 return new_rd_immBlock(dbgi, current_ir_graph);
504 ir_node *new_immBlock(void)
506 return new_rd_immBlock(NULL, current_ir_graph);
509 void add_immBlock_pred(ir_node *block, ir_node *jmp)
511 int n = ARR_LEN(block->in) - 1;
513 assert(is_Block(block) && "Error: Must be a Block");
514 assert(!block->attr.block.is_matured && "Error: Block already matured!\n");
515 assert(is_ir_node(jmp));
517 ARR_APP1(ir_node *, block->in, jmp);
519 hook_set_irn_n(block, n, jmp, NULL);
522 void set_cur_block(ir_node *target)
524 current_ir_graph->current_block = target;
527 void set_r_cur_block(ir_graph *irg, ir_node *target)
529 irg->current_block = target;
532 ir_node *get_r_cur_block(ir_graph *irg)
534 return irg->current_block;
537 ir_node *get_cur_block(void)
539 return get_r_cur_block(current_ir_graph);
542 ir_node *get_r_value(ir_graph *irg, int pos, ir_mode *mode)
544 assert(get_irg_phase_state(irg) == phase_building);
547 return get_r_value_internal(irg->current_block, pos + 1, mode);
550 ir_node *get_value(int pos, ir_mode *mode)
552 return get_r_value(current_ir_graph, pos, mode);
556 * helper function for guess_mode: recursively look for a definition for
557 * local variable @p pos, returns its mode if found.
559 static ir_mode *guess_recursively(ir_node *block, int pos)
565 if (irn_visited(block))
567 mark_irn_visited(block);
569 /* already have a defintion -> we can simply look at its mode */
570 value = block->attr.block.graph_arr[pos];
572 return get_irn_mode(value);
574 /* now we try to guess, by looking at the predecessor blocks */
575 n_preds = get_irn_arity(block);
576 for (i = 0; i < n_preds; ++i) {
577 ir_node *pred_block = get_Block_cfgpred_block(block, i);
578 ir_mode *mode = guess_recursively(pred_block, pos);
583 /* no way to guess */
587 ir_mode *ir_r_guess_mode(ir_graph *irg, int pos)
589 ir_node *block = irg->current_block;
590 ir_node *value = block->attr.block.graph_arr[pos+1];
593 /* already have a defintion -> we can simply look at its mode */
595 return get_irn_mode(value);
597 ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
598 inc_irg_visited(irg);
599 mode = guess_recursively(block, pos+1);
600 ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
605 ir_mode *ir_guess_mode(int pos)
607 return ir_r_guess_mode(current_ir_graph, pos);
610 void set_r_value(ir_graph *irg, int pos, ir_node *value)
612 assert(get_irg_phase_state(irg) == phase_building);
614 assert(pos+1 < irg->n_loc);
615 assert(is_ir_node(value));
616 irg->current_block->attr.block.graph_arr[pos + 1] = value;
619 void set_value(int pos, ir_node *value)
621 set_r_value(current_ir_graph, pos, value);
624 int r_find_value(ir_graph *irg, ir_node *value)
627 ir_node *bl = irg->current_block;
629 for (i = ARR_LEN(bl->attr.block.graph_arr) - 1; i >= 1; --i)
630 if (bl->attr.block.graph_arr[i] == value)
635 int find_value(ir_node *value)
637 return r_find_value(current_ir_graph, value);
640 ir_node *get_r_store(ir_graph *irg)
642 assert(get_irg_phase_state(irg) == phase_building);
643 return get_r_value_internal(irg->current_block, 0, mode_M);
646 ir_node *get_store(void)
648 return get_r_store(current_ir_graph);
651 void set_r_store(ir_graph *irg, ir_node *store)
653 ir_node *load, *pload, *pred, *in[2];
655 assert(get_irg_phase_state(irg) == phase_building);
656 /* Beware: due to dead code elimination, a store might become a Bad node even in
657 the construction phase. */
658 assert((get_irn_mode(store) == mode_M || is_Bad(store)) && "storing non-memory node");
660 if (get_opt_auto_create_sync()) {
661 /* handle non-volatile Load nodes by automatically creating Sync's */
662 load = skip_Proj(store);
663 if (is_Load(load) && get_Load_volatility(load) == volatility_non_volatile) {
664 pred = get_Load_mem(load);
667 /* a Load after a Sync: move it up */
668 ir_node *mem = skip_Proj(get_Sync_pred(pred, 0));
670 set_Load_mem(load, get_memop_mem(mem));
671 add_Sync_pred(pred, store);
674 pload = skip_Proj(pred);
675 if (is_Load(pload) && get_Load_volatility(pload) == volatility_non_volatile) {
676 /* a Load after a Load: create a new Sync */
677 set_Load_mem(load, get_Load_mem(pload));
681 store = new_r_Sync(irg->current_block, 2, in);
686 irg->current_block->attr.block.graph_arr[0] = store;
689 void set_store(ir_node *store)
691 set_r_store(current_ir_graph, store);
694 void r_keep_alive(ir_graph *irg, ir_node *ka)
696 add_End_keepalive(get_irg_end(irg), ka);
699 void keep_alive(ir_node *ka)
701 r_keep_alive(current_ir_graph, ka);
704 void ir_set_uninitialized_local_variable_func(
705 uninitialized_local_variable_func_t *func)
707 default_initialize_local_variable = func;
710 void irg_finalize_cons(ir_graph *irg)
712 set_irg_phase_state(irg, phase_high);
715 void irp_finalize_cons(void)
718 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
719 irg_finalize_cons(get_irp_irg(i));
721 irp->phase_state = phase_high;
724 ir_node *new_Const_long(ir_mode *mode, long value)
726 return new_d_Const_long(NULL, mode, value);
729 ir_node *new_SymConst(ir_mode *mode, symconst_symbol value, symconst_kind kind)
731 return new_d_SymConst(NULL, mode, value, kind);
733 ir_node *new_simpleSel(ir_node *store, ir_node *objptr, ir_entity *ent)
735 return new_d_simpleSel(NULL, store, objptr, ent);
737 ir_node *new_defaultProj(ir_node *arg, long max_proj)
739 return new_d_defaultProj(NULL, arg, max_proj);
741 ir_node *new_ASM(int arity, ir_node *in[], ir_asm_constraint *inputs,
742 int n_outs, ir_asm_constraint *outputs,
743 int n_clobber, ident *clobber[], ident *text)
745 return new_d_ASM(NULL, arity, in, inputs, n_outs, outputs, n_clobber, clobber, text);
748 ir_node *new_r_Anchor(ir_graph *irg)
750 ir_node *in[anchor_last];
752 memset(in, 0, sizeof(in));
753 res = new_ir_node(NULL, irg, NULL, op_Anchor, mode_ANY, anchor_last, in);
754 res->attr.anchor.irg.irg = irg;
756 /* hack to get get_irn_irg working: set block to ourself and allow
757 * get_Block_irg for anchor */
763 ir_node *new_r_Block_noopt(ir_graph *irg, int arity, ir_node *in[])
765 ir_node *res = new_ir_node(NULL, irg, NULL, op_Block, mode_BB, arity, in);
766 res->attr.block.irg.irg = irg;
767 res->attr.block.backedge = new_backedge_arr(irg->obst, arity);
768 set_Block_matured(res, 1);
769 /* Create and initialize array for Phi-node construction. */
770 if (get_irg_phase_state(irg) == phase_building) {
771 res->attr.block.graph_arr = NEW_ARR_D(ir_node *, irg->obst, irg->n_loc);
772 memset(res->attr.block.graph_arr, 0, irg->n_loc * sizeof(ir_node*));
774 irn_verify_irg(res, irg);