1 /* Copyright (C) 1998 - 2000 by Universitaet Karlsruhe
2 ** All rights reserved.
4 ** Authors: Martin Trapp, Christian Schaefer
6 ** ircons.c: basic and more detailed irnode constructors
7 ** store, block and parameter administration.
8 ** Adapted to extended FIRM nodes (exceptions...) and commented
9 ** by Goetz Lindenmaier
19 /* memset belongs to string.h */
23 #if USE_EXPICIT_PHI_IN_STACK
24 /* A stack needed for the automatic Phi node construction in constructor
32 /*********************************************** */
33 /** privat interfaces, for professional use only */
35 /* Constructs a Block with a fixed number of predecessors.
36 Does not set current_block. */
39 new_r_Block (ir_graph *irg, int arity, ir_node **in)
43 res = new_ir_node (irg, NULL, op_Block, mode_R, arity, in);
44 set_Block_matured(res, 1);
51 new_r_Start (ir_graph *irg, ir_node *block)
55 res = new_ir_node (irg, block, op_Start, mode_T, 0, NULL);
62 new_r_End (ir_graph *irg, ir_node *block)
66 res = new_ir_node (irg, block, op_End, mode_X, -1, NULL);
72 /* Creates a Phi node with all predecessors. Calling this constructor
73 is only allowed if the corresponding block is mature. */
75 new_r_Phi (ir_graph *irg, ir_node *block, int arity, ir_node **in, ir_mode *mode)
79 assert( get_Block_matured(block) );
80 assert( get_irn_arity(block) == arity );
82 res = new_ir_node (irg, block, op_Phi, mode, arity, in);
90 new_r_Const (ir_graph *irg, ir_node *block, ir_mode *mode, tarval *con)
93 res = new_ir_node (irg, block, op_Const, mode, 0, NULL);
99 res = local_optimize_newby (res);
106 new_r_Id (ir_graph *irg, ir_node *block, ir_node *val, ir_mode *mode)
108 ir_node *in[1] = {val};
110 res = new_ir_node (irg, block, op_Id, mode, 1, in);
111 res = optimize (res);
117 new_r_Proj (ir_graph *irg, ir_node *block, ir_node *arg, ir_mode *mode,
120 ir_node *in[1] = {arg};
122 res = new_ir_node (irg, block, op_Proj, mode, 1, in);
123 res->attr.proj = proj;
126 assert(get_Proj_pred(res));
127 assert(get_nodes_Block(get_Proj_pred(res)));
129 res = optimize (res);
137 new_r_Conv (ir_graph *irg, ir_node *block, ir_node *op, ir_mode *mode)
139 ir_node *in[1] = {op};
141 res = new_ir_node (irg, block, op_Conv, mode, 1, in);
142 res = optimize (res);
149 new_r_Tuple (ir_graph *irg, ir_node *block, int arity, ir_node **in)
153 res = new_ir_node (irg, block, op_Tuple, mode_T, arity, in);
154 res = optimize (res);
160 new_r_Add (ir_graph *irg, ir_node *block,
161 ir_node *op1, ir_node *op2, ir_mode *mode)
163 ir_node *in[2] = {op1, op2};
165 res = new_ir_node (irg, block, op_Add, mode, 2, in);
166 res = optimize (res);
172 new_r_Sub (ir_graph *irg, ir_node *block,
173 ir_node *op1, ir_node *op2, ir_mode *mode)
175 ir_node *in[2] = {op1, op2};
177 res = new_ir_node (irg, block, op_Sub, mode, 2, in);
178 res = optimize (res);
184 new_r_Minus (ir_graph *irg, ir_node *block,
185 ir_node *op, ir_mode *mode)
187 ir_node *in[1] = {op};
189 res = new_ir_node (irg, block, op_Minus, mode, 1, in);
190 res = optimize (res);
196 new_r_Mul (ir_graph *irg, ir_node *block,
197 ir_node *op1, ir_node *op2, ir_mode *mode)
199 ir_node *in[2] = {op1, op2};
201 res = new_ir_node (irg, block, op_Mul, mode, 2, in);
202 res = optimize (res);
208 new_r_Quot (ir_graph *irg, ir_node *block,
209 ir_node *memop, ir_node *op1, ir_node *op2)
211 ir_node *in[3] = {memop, op1, op2};
213 res = new_ir_node (irg, block, op_Quot, mode_T, 3, in);
214 res = optimize (res);
220 new_r_DivMod (ir_graph *irg, ir_node *block,
221 ir_node *memop, ir_node *op1, ir_node *op2)
223 ir_node *in[3] = {memop, op1, op2};
225 res = new_ir_node (irg, block, op_DivMod, mode_T, 3, in);
226 res = optimize (res);
232 new_r_Div (ir_graph *irg, ir_node *block,
233 ir_node *memop, ir_node *op1, ir_node *op2)
235 ir_node *in[3] = {memop, op1, op2};
237 res = new_ir_node (irg, block, op_Div, mode_T, 3, in);
238 res = optimize (res);
244 new_r_Mod (ir_graph *irg, ir_node *block,
245 ir_node *memop, ir_node *op1, ir_node *op2)
247 ir_node *in[3] = {memop, op1, op2};
249 res = new_ir_node (irg, block, op_Mod, mode_T, 3, in);
250 res = optimize (res);
256 new_r_And (ir_graph *irg, ir_node *block,
257 ir_node *op1, ir_node *op2, ir_mode *mode)
259 ir_node *in[2] = {op1, op2};
261 res = new_ir_node (irg, block, op_And, mode, 2, in);
262 res = optimize (res);
268 new_r_Or (ir_graph *irg, ir_node *block,
269 ir_node *op1, ir_node *op2, ir_mode *mode)
271 ir_node *in[2] = {op1, op2};
273 res = new_ir_node (irg, block, op_Or, mode, 2, in);
274 res = optimize (res);
280 new_r_Eor (ir_graph *irg, ir_node *block,
281 ir_node *op1, ir_node *op2, ir_mode *mode)
283 ir_node *in[2] = {op1, op2};
285 res = new_ir_node (irg, block, op_Eor, mode, 2, in);
286 res = optimize (res);
292 new_r_Not (ir_graph *irg, ir_node *block,
293 ir_node *op, ir_mode *mode)
295 ir_node *in[1] = {op};
297 res = new_ir_node (irg, block, op_Not, mode, 1, in);
298 res = optimize (res);
304 new_r_Shl (ir_graph *irg, ir_node *block,
305 ir_node *op, ir_node *k, ir_mode *mode)
307 ir_node *in[2] = {op, k};
309 res = new_ir_node (irg, block, op_Shl, mode, 2, in);
310 res = optimize (res);
316 new_r_Shr (ir_graph *irg, ir_node *block,
317 ir_node *op, ir_node *k, ir_mode *mode)
319 ir_node *in[2] = {op, k};
321 res = new_ir_node (irg, block, op_Shr, mode, 2, in);
322 res = optimize (res);
328 new_r_Shrs (ir_graph *irg, ir_node *block,
329 ir_node *op, ir_node *k, ir_mode *mode)
331 ir_node *in[2] = {op, k};
333 res = new_ir_node (irg, block, op_Shrs, mode, 2, in);
334 res = optimize (res);
340 new_r_Rot (ir_graph *irg, ir_node *block,
341 ir_node *op, ir_node *k, ir_mode *mode)
343 ir_node *in[2] = {op, k};
345 res = new_ir_node (irg, block, op_Rot, mode, 2, in);
346 res = optimize (res);
352 new_r_Abs (ir_graph *irg, ir_node *block,
353 ir_node *op, ir_mode *mode)
355 ir_node *in[1] = {op};
357 res = new_ir_node (irg, block, op_Abs, mode, 1, in);
358 res = optimize (res);
364 new_r_Cmp (ir_graph *irg, ir_node *block,
365 ir_node *op1, ir_node *op2)
367 ir_node *in[2] = {op1, op2};
369 res = new_ir_node (irg, block, op_Cmp, mode_T, 2, in);
370 res = optimize (res);
376 new_r_Jmp (ir_graph *irg, ir_node *block)
380 res = new_ir_node (irg, block, op_Jmp, mode_X, 0, in);
381 res = optimize (res);
387 new_r_Cond (ir_graph *irg, ir_node *block, ir_node *c)
389 ir_node *in[1] = {c};
391 res = new_ir_node (irg, block, op_Cond, mode_T, 1, in);
392 res = optimize (res);
398 new_r_Call (ir_graph *irg, ir_node *block, ir_node *store,
399 ir_node *callee, int arity, ir_node **in, type_method *type)
406 NEW_ARR_A (ir_node *, r_in, r_arity);
409 memcpy (&r_in[2], in, sizeof (ir_node *) * arity);
411 res = new_ir_node (irg, block, op_Call, mode_T, r_arity, r_in);
413 set_Call_type(res, type);
414 res = optimize (res);
420 new_r_Return (ir_graph *irg, ir_node *block,
421 ir_node *store, int arity, ir_node **in)
428 NEW_ARR_A (ir_node *, r_in, r_arity);
430 memcpy (&r_in[1], in, sizeof (ir_node *) * arity);
431 res = new_ir_node (irg, block, op_Return, mode_X, r_arity, r_in);
432 res = optimize (res);
438 new_r_Raise (ir_graph *irg, ir_node *block, ir_node *store, ir_node *obj)
440 ir_node *in[2] = {store, obj};
442 res = new_ir_node (irg, block, op_Raise, mode_X, 2, in);
444 res = optimize (res);
450 new_r_Load (ir_graph *irg, ir_node *block,
451 ir_node *store, ir_node *adr)
453 ir_node *in[2] = {store, adr};
455 res = new_ir_node (irg, block, op_Load, mode_T, 2, in);
457 res = optimize (res);
463 new_r_Store (ir_graph *irg, ir_node *block,
464 ir_node *store, ir_node *adr, ir_node *val)
466 ir_node *in[3] = {store, adr, val};
468 res = new_ir_node (irg, block, op_Store, mode_T, 3, in);
470 res = optimize (res);
476 new_r_Alloc (ir_graph *irg, ir_node *block, ir_node *store,
477 ir_node *size, type *alloc_type, where_alloc where)
479 ir_node *in[2] = {store, size};
481 res = new_ir_node (irg, block, op_Alloc, mode_T, 2, in);
483 res->attr.a.where = where;
484 res->attr.a.type = alloc_type;
486 res = optimize (res);
492 new_r_Free (ir_graph *irg, ir_node *block, ir_node *store,
493 ir_node *ptr, ir_node *size, type *free_type)
495 ir_node *in[3] = {store, ptr, size};
497 res = new_ir_node (irg, block, op_Free, mode_T, 3, in);
499 res->attr.f = free_type;
501 res = optimize (res);
507 new_r_Sel (ir_graph *irg, ir_node *block, ir_node *store, ir_node *objptr,
508 int arity, ir_node **in, entity *ent)
515 NEW_ARR_A (ir_node *, r_in, r_arity);
518 memcpy (&r_in[2], in, sizeof (ir_node *) * arity);
519 res = new_ir_node (irg, block, op_Sel, mode_p, r_arity, r_in);
521 res->attr.s.ltyp = static_linkage;
522 res->attr.s.ent = ent;
524 res = optimize (res);
530 new_r_SymConst (ir_graph *irg, ir_node *block, type_or_id *value,
531 symconst_kind symkind)
536 if (symkind == linkage_ptr_info)
540 res = new_ir_node (irg, block, op_SymConst, mode, 0, in);
542 res->attr.i.num = symkind;
543 if (symkind == linkage_ptr_info) {
544 res->attr.i.tori.ptrinfo = (ident *)value;
546 assert ( ( (symkind == type_tag)
547 || (symkind == size))
548 && (is_type(value)));
549 res->attr.i.tori.typ = (type *)value;
551 res = optimize (res);
557 new_r_Sync (ir_graph *irg, ir_node *block, int arity, ir_node **in)
561 res = new_ir_node (irg, block, op_Sync, mode_M, arity, in);
563 res = optimize (res);
571 return current_ir_graph->bad;
574 /***********************/
575 /** public interfaces */
576 /** construction tools */
583 res = new_ir_node (current_ir_graph, current_ir_graph->current_block,
584 op_Start, mode_T, 0, NULL);
586 res = optimize (res);
596 res = new_ir_node (current_ir_graph, current_ir_graph->current_block,
597 op_End, mode_X, -1, NULL);
599 res = optimize (res);
610 res = new_ir_node (current_ir_graph, NULL, op_Block, mode_R, -1, NULL);
611 current_ir_graph->current_block = res;
612 res->attr.block.matured = 0;
613 set_Block_block_visited(res, 0);
615 /* forget this optimization. use this only if mature !!!!
616 res = optimize (res); */
619 /** create a new dynamic array, which stores all parameters in irnodes */
620 /** using the same obstack as the whole irgraph */
621 res->attr.block.graph_arr = NEW_ARR_D (ir_node *, current_ir_graph->obst,
622 current_ir_graph->params);
624 /** initialize the parameter array */
625 memset(res->attr.block.graph_arr, 0, sizeof(ir_node *)*current_ir_graph->params);
630 /*************************************************************************/
631 /* Methods necessary for automatic Phi node creation */
633 ir_node *phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
634 ir_node *get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
635 ir_node *new_r_Phi0 (ir_graph *irg, ir_node *block, ir_mode *mode)
636 ir_node *new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode, ir_node **in, int ins)
638 Call Graph: ( A ---> B == A "calls" B)
640 get_value mature_block
648 get_r_value_internal |
652 new_r_Phi0 new_r_Phi_in
654 *****************************************************************************/
656 /* Creates a Phi node with 0 predecessors */
658 new_r_Phi0 (ir_graph *irg, ir_node *block, ir_mode *mode)
661 res = new_ir_node (irg, block, op_Phi, mode, 0, NULL);
666 /* There are two implementations of the Phi node construction. The first
667 is faster, but does not work for blocks with more than 2 predecessors.
668 The second works always but is slower and causes more unnecessary Phi
670 Select the implementations by the following preprocessor flag set in
672 #if USE_FAST_PHI_CONSTRUCTION
674 /* This is a stack used for allocating and deallocating nodes in
675 new_r_Phi_in. The original implementation used the obstack
676 to model this stack, now it is explicit. This reduces side effects.
678 #if USE_EXPICIT_PHI_IN_STACK
683 res = (Phi_in_stack *) malloc ( sizeof (Phi_in_stack));
685 res->stack = NEW_ARR_F (ir_node *, 1);
691 void free_to_Phi_in_stack(ir_node *phi) {
692 assert(get_irn_opcode(phi) == iro_Phi);
694 if (ARR_LEN(current_ir_graph->Phi_in_stack->stack) ==
695 current_ir_graph->Phi_in_stack->pos)
696 ARR_APP1 (ir_node *, current_ir_graph->Phi_in_stack->stack, phi);
698 current_ir_graph->Phi_in_stack->stack[current_ir_graph->Phi_in_stack->pos] = phi;
700 (current_ir_graph->Phi_in_stack->pos)++;
704 alloc_or_pop_from_Phi_in_stack(ir_graph *irg, ir_node *block, ir_mode *mode,
705 int arity, ir_node **in) {
707 ir_node **stack = current_ir_graph->Phi_in_stack->stack;
708 int pos = current_ir_graph->Phi_in_stack->pos;
712 /* We need to allocate a new node */
713 res = new_ir_node (irg, block, op_Phi, mode, arity, in);
715 /* reuse the old node and initialize it again. */
718 assert (res->kind == k_ir_node);
719 assert (res->op == op_Phi);
724 /* ???!!! How to free the old in array?? */
725 res->in = NEW_ARR_D (ir_node *, irg->obst, (arity+1));
727 memcpy (&res->in[1], in, sizeof (ir_node *) * arity);
729 (current_ir_graph->Phi_in_stack->pos)--;
733 #endif /* USE_EXPICIT_PHI_IN_STACK */
735 /* Creates a Phi node with a given, fixed array **in of predecessors.
736 If the Phi node is unnecessary, as the same value reaches the block
737 through all control flow paths, it is eliminated and the value
738 returned directly. This constructor is only intended for use in
739 the automatic Phi node generation triggered by get_value or mature.
740 The implementation is quite tricky and depends on the fact, that
741 the nodes are allocated on a stack:
742 The in array contains predecessors and NULLs. The NULLs appear,
743 if get_r_value_internal, that computed the predecessors, reached
744 the same block on two paths. In this case the same value reaches
745 this block on both paths, there is no definition in between. We need
746 not allocate a Phi where these path's merge, but we have to communicate
747 this fact to the caller. This happens by returning a pointer to the
748 node the caller _will_ allocate. (Yes, we predict the address. We can
749 do so because the nodes are allocated on the obstack.) The caller then
750 finds a pointer to itself and, when this routine is called again,
754 new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode,
755 ir_node **in, int ins)
758 ir_node *res, *known;
760 /* allocate a new node on the obstack.
761 This can return a node to which some of the pointers in the in-array
763 Attention: the constructor copies the in array, i.e., the later changes
764 to the array in this routine do not affect the constructed node! If
765 the in array contains NULLs, there will be missing predecessors in the
767 Is this a possible internal state of the Phi node generation? */
768 #if USE_EXPICIT_PHI_IN_STACK
769 res = known = alloc_or_pop_from_Phi_in_stack(irg, block, mode, ins, in);
771 res = known = new_ir_node (irg, block, op_Phi, mode, ins, in);
773 /* The in-array can contain NULLs. These were returned by
774 get_r_value_internal if it reached the same block/definition on a
776 The NULLs are replaced by the node itself to simplify the test in the
778 for (i=0; i < ins; ++i)
779 if (in[i] == NULL) in[i] = res;
781 /* This loop checks whether the Phi has more than one predecessor.
782 If so, it is a real Phi node and we break the loop. Else the
783 Phi node merges the same definition on several paths and therefore
785 for (i=0; i < ins; ++i)
787 if (in[i]==res || in[i]==known) continue;
795 /* i==ins: there is at most one predecessor, we don't need a phi node. */
797 #if USE_EXPICIT_PHI_IN_STACK
798 free_to_Phi_in_stack(res);
800 obstack_free (current_ir_graph->obst, res);
804 res = optimize (res);
808 /* return the pointer to the Phi node. This node might be deallocated! */
813 get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
815 /** This function computes the predecessors for a real Phi node, and then
816 allocates and returns this node. The routine called to allocate the
817 node might optimize it away and return a real value, or even a pointer
818 to a deallocated Phi node on top of the obstack!
819 This function is called with an in-array of proper size. **/
820 static inline ir_node *
821 phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
823 ir_node *prevBlock, *res;
826 /* This loop goes to all predecessor blocks of the block the Phi node is in
827 and there finds the operands of the Phi node by calling
828 get_r_value_internal. */
829 for (i = 1; i <= ins; ++i) {
830 assert (block->in[i]);
831 prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */
833 nin[i-1] = get_r_value_internal (prevBlock, pos, mode);
836 /* After collecting all predecessors into the array nin a new Phi node
837 with these predecessors is created. This constructor contains an
838 optimization: If all predecessors of the Phi node are identical it
839 returns the only operand instead of a new Phi node. If the value
840 passes two different control flow edges without being defined, and
841 this is the second path treated, a pointer to the node that will be
842 allocated for the first path (recursion) is returned. We already
843 know the address of this node, as it is the next node to be allocated
844 and will be placed on top of the obstack. (The obstack is a _stack_!) */
845 res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins);
847 /* Now we now the value for "pos" and can enter it in the array with
848 all known local variables. Attention: this might be a pointer to
849 a node, that later will be allocated!!! See new_r_Phi_in.
850 If this is called in mature, after some set_value in the same block,
851 the proper value must not be overwritten:
853 get_value (makes Phi0, put's it into graph_arr)
854 set_value (overwrites Phi0 in graph_arr)
855 mature_block (upgrades Phi0, puts it again into graph_arr, overwriting
858 if (!block->attr.block.graph_arr[pos]) {
859 block->attr.block.graph_arr[pos] = res;
861 /* printf(" value already computed by %s\n",
862 id_to_str(block->attr.block.graph_arr[pos]->op->name)); */
868 /* This function returns the last definition of a variable. In case
869 this variable was last defined in a previous block, Phi nodes are
870 inserted. If the part of the firm graph containing the definition
871 is not yet constructed, a dummy Phi node is returned. */
873 get_r_value_internal (ir_node *block, int pos, ir_mode *mode)
876 /* There are 4 cases to treat.
878 1. The block is not mature and we visit it the first time. We can not
879 create a proper Phi node, therefore a Phi0, i.e., a Phi without
880 predecessors is returned. This node is added to the linked list (field
881 "link") of the containing block to be completed when this block is
882 matured. (Comlpletion will add a new Phi and turn the Phi0 into an Id
885 2. The value is already known in this block, graph_arr[pos] is set and we
886 visit the block the first time. We can return the value without
887 creating any new nodes.
889 3. The block is mature and we visit it the first time. A Phi node needs
890 to be created (phi_merge). If the Phi is not needed, as all it's
891 operands are the same value reaching the block through different
892 paths, it's optimized away and the value itself is returned.
894 4. The block is mature, and we visit it the second time. Now two
895 subcases are possible:
896 * The value was computed completely the last time we were here. This
897 is the case if there is no loop. We can return the proper value.
898 * The recursion that visited this node and set the flag did not
899 return yet. We are computing a value in a loop and need to
900 break the recursion without knowing the result yet.
901 @@@ strange case. Straight forward we would create a Phi before
902 starting the computation of it's predecessors. In this case we will find
903 a Phi here in any case. The problem is that this implementation only
904 creates a Phi after computing the predecessors, so that it is hard to
905 compute self references of this Phi. @@@
906 There is no simple check for the second subcase. Therefore we check
907 for a second visit and treat all such cases as the second subcase.
908 Anyways, the basic situation is the same: we reached a block
909 on two paths without finding a definition of the value: No Phi
910 nodes are needed on both paths.
911 We return this information "Two paths, no Phi needed" by a very tricky
912 implementation that relies on the fact that an obstack is a stack and
913 will return a node with the same address on different allocations.
914 Look also at phi_merge and new_r_phi_in to understand this.
915 @@@ Unfortunately this does not work, see testprogram three_cfpred_example.
919 /* case 4 -- already visited. */
920 if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) return NULL;
922 /* visited the first time */
923 set_irn_visited(block, get_irg_visited(current_ir_graph));
925 /* Get the local valid value */
926 res = block->attr.block.graph_arr[pos];
928 /* case 2 -- If the value is actually computed, return it. */
929 if (res) { return res;};
931 if (block->attr.block.matured) { /* case 3 */
933 /* The Phi has the same amount of ins as the corresponding block. */
934 int ins = get_irn_arity(block);
936 NEW_ARR_A (ir_node *, nin, ins);
938 /* Phi merge collects the predecessors and then creates a node. */
939 res = phi_merge (block, pos, mode, nin, ins);
941 } else { /* case 1 */
942 /* The block is not mature, we don't know how many in's are needed. A Phi
943 with zero predecessors is created. Such a Phi node is called Phi0
944 node. (There is also an obsolete Phi0 opcode.) The Phi0 is then added
945 to the list of Phi0 nodes in this block to be matured by mature_block
947 The Phi0 has to remember the pos of it's internal value. If the real
948 Phi is computed, pos is used to update the array with the local
951 res = new_r_Phi0 (current_ir_graph, block, mode);
952 res->attr.phi0_pos = pos;
953 res->link = block->link;
957 /* If we get here, the frontend missed a use-before-definition error */
960 printf("Error: no value set. Use of undefined variable. Initializing
962 assert (mode->code >= irm_f && mode->code <= irm_p);
963 res = new_r_Const (current_ir_graph, block, mode,
964 tarval_mode_null[mode->code]);
967 /* The local valid value is available now. */
968 block->attr.block.graph_arr[pos] = res;
975 /** This is the simple algorithm. If first generates a Phi0, then
976 it starts the recursion. This causes an Id at the entry of
977 every block that has no definition of the value! **/
979 #if USE_EXPICIT_PHI_IN_STACK
981 Phi_in_stack * new_Phi_in_stack() { return NULL; }
985 new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode,
986 ir_node **in, int ins)
989 ir_node *res, *known;
991 /* Allocate a new node on the obstack. The allocation copies the in
993 res = new_ir_node (irg, block, op_Phi, mode, ins, in);
995 /* This loop checks whether the Phi has more than one predecessor.
996 If so, it is a real Phi node and we break the loop. Else the
997 Phi node merges the same definition on several paths and therefore
998 is not needed. Don't consider Bad nodes! */
1000 for (i=0; i < ins; ++i)
1002 if (in[i]==res || in[i]==known || is_Bad(in[i])) continue;
1010 /* i==ins: there is at most one predecessor, we don't need a phi node. */
1013 obstack_free (current_ir_graph->obst, res);
1016 /* A undefined value, e.g., in unreachable code. */
1020 res = optimize (res);
1028 get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
1030 /** This function allocates a dummy Phi node to break recursions,
1031 computes the predecessors for the real phi node, and then
1032 allocates and returns this node. The routine called to allocate the
1033 node might optimize it away and return a real value.
1034 This function is called with an in-array of proper size. **/
1035 static inline ir_node *
1036 phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
1038 ir_node *prevBlock, *res, *phi0;
1042 /* If this block has no value at pos create a Phi0 and remember it
1043 in graph_arr to break recursions. */
1045 if (!block->attr.block.graph_arr[pos]) {
1046 /* Even if all variables are defined before use, it can happen that
1047 we get to the start block, if a cond has been replaced by a tuple
1048 (bad, jmp). As the start has a self referencing control flow edge,
1049 we get a self referencing Id, which is hard to optimize away. We avoid
1050 this by defining the value as a Bad node. *
1051 if (block == get_irg_start_block(current_ir_graph)) {
1052 block->attr.block.graph_arr[pos] = new_Bad();
1055 phi0 = new_r_Phi0(current_ir_graph, block, mode);
1056 block->attr.block.graph_arr[pos] = phi0;
1060 /* This loop goes to all predecessor blocks of the block the Phi node
1061 is in and there finds the operands of the Phi node by calling
1062 get_r_value_internal. */
1063 for (i = 1; i <= ins; ++i) {
1064 assert (block->in[i]);
1065 if (is_Bad(block->in[i])) {
1066 /* In case a Cond has been optimized we would get right to the start block
1067 with an invalid definition. */
1068 nin[i-1] = new_Bad();
1071 prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */
1073 if (!is_Bad(prevBlock)) {
1074 nin[i-1] = get_r_value_internal (prevBlock, pos, mode);
1076 nin[i-1] = new_Bad();
1080 /* After collecting all predecessors into the array nin a new Phi node
1081 with these predecessors is created. This constructor contains an
1082 optimization: If all predecessors of the Phi node are identical it
1083 returns the only operand instead of a new Phi node. */
1084 res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins);
1086 /* In case we allocated a Phi0 node at the beginning of this procedure,
1087 we need to exchange this Phi0 with the real Phi. */
1089 exchange(phi0, res);
1090 block->attr.block.graph_arr[pos] = res;
1096 /* This function returns the last definition of a variable. In case
1097 this variable was last defined in a previous block, Phi nodes are
1098 inserted. If the part of the firm graph containing the definition
1099 is not yet constructed, a dummy Phi node is returned. */
1101 get_r_value_internal (ir_node *block, int pos, ir_mode *mode)
1104 /* There are 4 cases to treat.
1106 1. The block is not mature and we visit it the first time. We can not
1107 create a proper Phi node, therefore a Phi0, i.e., a Phi without
1108 predecessors is returned. This node is added to the linked list (field
1109 "link") of the containing block to be completed when this block is
1110 matured. (Comlpletion will add a new Phi and turn the Phi0 into an Id
1113 2. The value is already known in this block, graph_arr[pos] is set and we
1114 visit the block the first time. We can return the value without
1115 creating any new nodes.
1117 3. The block is mature and we visit it the first time. A Phi node needs
1118 to be created (phi_merge). If the Phi is not needed, as all it's
1119 operands are the same value reaching the block through different
1120 paths, it's optimized away and the value itself is returned.
1122 4. The block is mature, and we visit it the second time. Now two
1123 subcases are possible:
1124 * The value was computed completely the last time we were here. This
1125 is the case if there is no loop. We can return the proper value.
1126 * The recursion that visited this node and set the flag did not
1127 return yet. We are computing a value in a loop and need to
1128 break the recursion. This case only happens if we visited
1129 the same block with phi_merge before, which inserted a Phi0.
1130 So we return the Phi0.
1133 /* case 4 -- already visited. */
1134 if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) {
1135 /* As phi_merge allocates a Phi0 this value is always defined. Here
1136 is the critical difference of the two algorithms. */
1137 assert(block->attr.block.graph_arr[pos]);
1138 return block->attr.block.graph_arr[pos];
1141 /* visited the first time */
1142 set_irn_visited(block, get_irg_visited(current_ir_graph));
1144 /* Get the local valid value */
1145 res = block->attr.block.graph_arr[pos];
1147 /* case 2 -- If the value is actually computed, return it. */
1148 if (res) { return res; };
1150 if (block->attr.block.matured) { /* case 3 */
1152 /* The Phi has the same amount of ins as the corresponding block. */
1153 int ins = get_irn_arity(block);
1155 NEW_ARR_A (ir_node *, nin, ins);
1157 /* Phi merge collects the predecessors and then creates a node. */
1158 res = phi_merge (block, pos, mode, nin, ins);
1160 } else { /* case 1 */
1161 /* The block is not mature, we don't know how many in's are needed. A Phi
1162 with zero predecessors is created. Such a Phi node is called Phi0
1163 node. The Phi0 is then added to the list of Phi0 nodes in this block
1164 to be matured by mature_block later.
1165 The Phi0 has to remember the pos of it's internal value. If the real
1166 Phi is computed, pos is used to update the array with the local
1168 res = new_r_Phi0 (current_ir_graph, block, mode);
1169 res->attr.phi0_pos = pos;
1170 res->link = block->link;
1174 /* If we get here, the frontend missed a use-before-definition error */
1177 printf("Error: no value set. Use of undefined variable. Initializing
1179 assert (mode->code >= irm_f && mode->code <= irm_p);
1180 res = new_r_Const (current_ir_graph, block, mode,
1181 tarval_mode_null[mode->code]);
1184 /* The local valid value is available now. */
1185 block->attr.block.graph_arr[pos] = res;
1190 #endif /* USE_FAST_PHI_CONSTRUCTION */
1192 /****************************************************************************/
1194 /** Finalize a Block node, when all control flows are known. */
1195 /** Acceptable parameters are only Block nodes. */
1197 mature_block (ir_node *block)
1204 assert (get_irn_opcode(block) == iro_Block);
1206 if (!get_Block_matured(block)) {
1208 /* turn the dynamic in-array into a static one. */
1209 ins = ARR_LEN (block->in)-1;
1210 NEW_ARR_A (ir_node *, nin, ins);
1212 /* Traverse a chain of Phi nodes attached to this block and mature
1214 for (n = block->link; n; n=next) {
1215 inc_irg_visited(current_ir_graph);
1217 exchange (n, phi_merge (block, n->attr.phi0_pos, n->mode, nin, ins));
1220 block->attr.block.matured = 1;
1222 /* Now, as the block is a finished firm node, we can optimize it.
1223 Since other nodes have been allocated since the block was created
1224 we can not free the node on the obstack. Therefore we have to call
1226 Unfortunately the optimization does not change a lot, as all allocated
1227 nodes refer to the unoptimized node. */
1228 block = optimize_in_place(block);
1234 new_Phi (int arity, ir_node **in, ir_mode *mode)
1236 return new_r_Phi (current_ir_graph, current_ir_graph->current_block,
1241 new_Const (ir_mode *mode, tarval *con)
1243 return new_r_Const (current_ir_graph, current_ir_graph->start_block,
1248 new_Id (ir_node *val, ir_mode *mode)
1250 return new_r_Id (current_ir_graph, current_ir_graph->current_block,
1255 new_Proj (ir_node *arg, ir_mode *mode, long proj)
1257 return new_r_Proj (current_ir_graph, current_ir_graph->current_block,
1262 new_Conv (ir_node *op, ir_mode *mode)
1264 return new_r_Conv (current_ir_graph, current_ir_graph->current_block,
1269 new_Tuple (int arity, ir_node **in)
1271 return new_r_Tuple (current_ir_graph, current_ir_graph->current_block,
1276 new_Add (ir_node *op1, ir_node *op2, ir_mode *mode)
1278 return new_r_Add (current_ir_graph, current_ir_graph->current_block,
1283 new_Sub (ir_node *op1, ir_node *op2, ir_mode *mode)
1285 return new_r_Sub (current_ir_graph, current_ir_graph->current_block,
1291 new_Minus (ir_node *op, ir_mode *mode)
1293 return new_r_Minus (current_ir_graph, current_ir_graph->current_block,
1298 new_Mul (ir_node *op1, ir_node *op2, ir_mode *mode)
1300 return new_r_Mul (current_ir_graph, current_ir_graph->current_block,
1305 new_Quot (ir_node *memop, ir_node *op1, ir_node *op2)
1307 return new_r_Quot (current_ir_graph, current_ir_graph->current_block,
1312 new_DivMod (ir_node *memop, ir_node *op1, ir_node *op2)
1314 return new_r_DivMod (current_ir_graph, current_ir_graph->current_block,
1319 new_Div (ir_node *memop, ir_node *op1, ir_node *op2)
1321 return new_r_Div (current_ir_graph, current_ir_graph->current_block,
1326 new_Mod (ir_node *memop, ir_node *op1, ir_node *op2)
1328 return new_r_Mod (current_ir_graph, current_ir_graph->current_block,
1333 new_And (ir_node *op1, ir_node *op2, ir_mode *mode)
1335 return new_r_And (current_ir_graph, current_ir_graph->current_block,
1340 new_Or (ir_node *op1, ir_node *op2, ir_mode *mode)
1342 return new_r_Or (current_ir_graph, current_ir_graph->current_block,
1347 new_Eor (ir_node *op1, ir_node *op2, ir_mode *mode)
1349 return new_r_Eor (current_ir_graph, current_ir_graph->current_block,
1354 new_Not (ir_node *op, ir_mode *mode)
1356 return new_r_Not (current_ir_graph, current_ir_graph->current_block,
1361 new_Shl (ir_node *op, ir_node *k, ir_mode *mode)
1363 return new_r_Shl (current_ir_graph, current_ir_graph->current_block,
1368 new_Shr (ir_node *op, ir_node *k, ir_mode *mode)
1370 return new_r_Shr (current_ir_graph, current_ir_graph->current_block,
1375 new_Shrs (ir_node *op, ir_node *k, ir_mode *mode)
1377 return new_r_Shrs (current_ir_graph, current_ir_graph->current_block,
1382 new_Rotate (ir_node *op, ir_node *k, ir_mode *mode)
1384 return new_r_Rot (current_ir_graph, current_ir_graph->current_block,
1389 new_Abs (ir_node *op, ir_mode *mode)
1391 return new_r_Abs (current_ir_graph, current_ir_graph->current_block,
1396 new_Cmp (ir_node *op1, ir_node *op2)
1398 return new_r_Cmp (current_ir_graph, current_ir_graph->current_block,
1405 return new_r_Jmp (current_ir_graph, current_ir_graph->current_block);
1409 new_Cond (ir_node *c)
1411 return new_r_Cond (current_ir_graph, current_ir_graph->current_block, c);
1415 new_Call (ir_node *store, ir_node *callee, int arity, ir_node **in,
1418 return new_r_Call (current_ir_graph, current_ir_graph->current_block,
1419 store, callee, arity, in, type);
1423 new_Return (ir_node* store, int arity, ir_node **in)
1425 return new_r_Return (current_ir_graph, current_ir_graph->current_block,
1430 new_Raise (ir_node *store, ir_node *obj)
1432 return new_r_Raise (current_ir_graph, current_ir_graph->current_block,
1437 new_Load (ir_node *store, ir_node *addr)
1439 return new_r_Load (current_ir_graph, current_ir_graph->current_block,
1444 new_Store (ir_node *store, ir_node *addr, ir_node *val)
1446 return new_r_Store (current_ir_graph, current_ir_graph->current_block,
1451 new_Alloc (ir_node *store, ir_node *size, type *alloc_type,
1454 return new_r_Alloc (current_ir_graph, current_ir_graph->current_block,
1455 store, size, alloc_type, where);
1459 new_Free (ir_node *store, ir_node *ptr, ir_node *size, type *free_type)
1461 return new_r_Free (current_ir_graph, current_ir_graph->current_block,
1462 store, ptr, size, free_type);
1466 new_simpleSel (ir_node *store, ir_node *objptr, entity *ent)
1467 /* GL: objptr was called frame before. Frame was a bad choice for the name
1468 as the operand could as well be a pointer to a dynamic object. */
1470 return new_r_Sel (current_ir_graph, current_ir_graph->current_block,
1471 store, objptr, 0, NULL, ent);
1475 new_Sel (ir_node *store, ir_node *objptr, int n_index, ir_node **index, entity *sel)
1477 return new_r_Sel (current_ir_graph, current_ir_graph->current_block,
1478 store, objptr, n_index, index, sel);
1482 new_SymConst (type_or_id *value, symconst_kind kind)
1484 return new_r_SymConst (current_ir_graph, current_ir_graph->current_block,
1489 new_Sync (int arity, ir_node** in)
1491 return new_r_Sync (current_ir_graph, current_ir_graph->current_block,
1499 return current_ir_graph->bad;
1502 /*************************************************************************/
1503 /* Comfortable interface with automatic Phi node construction. */
1504 /* (Uses also constructors of ?? interface, except new_Block. */
1505 /* add an adge to a jmp node */
1507 add_in_edge (ir_node *block, ir_node *jmp)
1509 if (block->attr.block.matured) {
1510 printf("Error: Block already matured!\n");
1513 assert (jmp != NULL);
1514 ARR_APP1 (ir_node *, block->in, jmp);
1518 /* changing the current block */
1520 switch_block (ir_node *target)
1522 current_ir_graph->current_block = target;
1525 /****************************/
1526 /* parameter administration */
1528 /* get a value from the parameter array from the current block by its index */
1530 get_value (int pos, ir_mode *mode)
1532 inc_irg_visited(current_ir_graph);
1533 return get_r_value_internal (current_ir_graph->current_block, pos + 1, mode);
1536 /* set a value at position pos in the parameter array from the current block */
1538 set_value (int pos, ir_node *value)
1540 current_ir_graph->current_block->attr.block.graph_arr[pos + 1] = value;
1543 /* get the current store */
1547 /* GL: one could call get_value instead */
1548 inc_irg_visited(current_ir_graph);
1549 return get_r_value_internal (current_ir_graph->current_block, 0, mode_M);
1552 /* set the current store */
1554 set_store (ir_node *store)
1556 /* GL: one could call set_value instead */
1557 current_ir_graph->current_block->attr.block.graph_arr[0] = store;
1560 /*************************************************************************/
1563 /* call once for each run of the library */