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
18 # include "irgraph_t.h"
19 # include "irnode_t.h"
20 # include "irmode_t.h"
28 /* memset belongs to string.h */
31 #if USE_EXPICIT_PHI_IN_STACK
32 /* A stack needed for the automatic Phi node construction in constructor
33 Phi_in. Redefinition in irgraph.c!! */
38 typedef struct Phi_in_stack Phi_in_stack;
41 /*** ******************************************** */
42 /** privat interfaces, for professional use only */
44 /* Constructs a Block with a fixed number of predecessors.
45 Does not set current_block. Can not be used with automatic
46 Phi node construction. */
48 new_r_Block (ir_graph *irg, int arity, ir_node **in)
52 res = new_ir_node (irg, NULL, op_Block, mode_R, arity, in);
53 set_Block_matured(res, 1);
54 set_Block_block_visited(res, 0);
61 new_r_Start (ir_graph *irg, ir_node *block)
65 res = new_ir_node (irg, block, op_Start, mode_T, 0, NULL);
72 new_r_End (ir_graph *irg, ir_node *block)
76 res = new_ir_node (irg, block, op_End, mode_X, -1, NULL);
82 /* Creates a Phi node with all predecessors. Calling this constructor
83 is only allowed if the corresponding block is mature. */
85 new_r_Phi (ir_graph *irg, ir_node *block, int arity, ir_node **in, ir_mode *mode)
89 assert( get_Block_matured(block) );
90 assert( get_irn_arity(block) == arity );
92 res = new_ir_node (irg, block, op_Phi, mode, arity, in);
97 /* Memory Phis in endless loops must be kept alive.
98 As we can't distinguish these easily we keep all of them alive. */
99 if ((res->op == op_Phi) && (mode == mode_M))
100 add_End_keepalive(irg->end, res);
105 new_r_Const (ir_graph *irg, ir_node *block, ir_mode *mode, tarval *con)
108 res = new_ir_node (irg, block, op_Const, mode, 0, NULL);
110 res = optimize (res);
114 res = local_optimize_newby (res);
121 new_r_Id (ir_graph *irg, ir_node *block, ir_node *val, ir_mode *mode)
123 ir_node *in[1] = {val};
125 res = new_ir_node (irg, block, op_Id, mode, 1, in);
126 res = optimize (res);
132 new_r_Proj (ir_graph *irg, ir_node *block, ir_node *arg, ir_mode *mode,
135 ir_node *in[1] = {arg};
137 res = new_ir_node (irg, block, op_Proj, mode, 1, in);
138 res->attr.proj = proj;
141 assert(get_Proj_pred(res));
142 assert(get_nodes_Block(get_Proj_pred(res)));
144 res = optimize (res);
152 new_r_defaultProj (ir_graph *irg, ir_node *block, ir_node *arg,
156 assert((arg->op==op_Cond) && (get_irn_mode(arg->in[1]) == mode_I));
157 arg->attr.c.kind = fragmentary;
158 arg->attr.c.default_proj = max_proj;
159 res = new_r_Proj (irg, block, arg, mode_X, max_proj);
164 new_r_Conv (ir_graph *irg, ir_node *block, ir_node *op, ir_mode *mode)
166 ir_node *in[1] = {op};
168 res = new_ir_node (irg, block, op_Conv, mode, 1, in);
169 res = optimize (res);
176 new_r_Tuple (ir_graph *irg, ir_node *block, int arity, ir_node **in)
180 res = new_ir_node (irg, block, op_Tuple, mode_T, arity, in);
181 res = optimize (res);
187 new_r_Add (ir_graph *irg, ir_node *block,
188 ir_node *op1, ir_node *op2, ir_mode *mode)
190 ir_node *in[2] = {op1, op2};
192 res = new_ir_node (irg, block, op_Add, mode, 2, in);
193 res = optimize (res);
199 new_r_Sub (ir_graph *irg, ir_node *block,
200 ir_node *op1, ir_node *op2, ir_mode *mode)
202 ir_node *in[2] = {op1, op2};
204 res = new_ir_node (irg, block, op_Sub, mode, 2, in);
205 res = optimize (res);
211 new_r_Minus (ir_graph *irg, ir_node *block,
212 ir_node *op, ir_mode *mode)
214 ir_node *in[1] = {op};
216 res = new_ir_node (irg, block, op_Minus, mode, 1, in);
217 res = optimize (res);
223 new_r_Mul (ir_graph *irg, ir_node *block,
224 ir_node *op1, ir_node *op2, ir_mode *mode)
226 ir_node *in[2] = {op1, op2};
228 res = new_ir_node (irg, block, op_Mul, mode, 2, in);
229 res = optimize (res);
235 new_r_Quot (ir_graph *irg, ir_node *block,
236 ir_node *memop, ir_node *op1, ir_node *op2)
238 ir_node *in[3] = {memop, op1, op2};
240 res = new_ir_node (irg, block, op_Quot, mode_T, 3, in);
241 res = optimize (res);
247 new_r_DivMod (ir_graph *irg, ir_node *block,
248 ir_node *memop, ir_node *op1, ir_node *op2)
250 ir_node *in[3] = {memop, op1, op2};
252 res = new_ir_node (irg, block, op_DivMod, mode_T, 3, in);
253 res = optimize (res);
259 new_r_Div (ir_graph *irg, ir_node *block,
260 ir_node *memop, ir_node *op1, ir_node *op2)
262 ir_node *in[3] = {memop, op1, op2};
264 res = new_ir_node (irg, block, op_Div, mode_T, 3, in);
265 res = optimize (res);
271 new_r_Mod (ir_graph *irg, ir_node *block,
272 ir_node *memop, ir_node *op1, ir_node *op2)
274 ir_node *in[3] = {memop, op1, op2};
276 res = new_ir_node (irg, block, op_Mod, mode_T, 3, in);
277 res = optimize (res);
283 new_r_And (ir_graph *irg, ir_node *block,
284 ir_node *op1, ir_node *op2, ir_mode *mode)
286 ir_node *in[2] = {op1, op2};
288 res = new_ir_node (irg, block, op_And, mode, 2, in);
289 res = optimize (res);
295 new_r_Or (ir_graph *irg, ir_node *block,
296 ir_node *op1, ir_node *op2, ir_mode *mode)
298 ir_node *in[2] = {op1, op2};
300 res = new_ir_node (irg, block, op_Or, mode, 2, in);
301 res = optimize (res);
307 new_r_Eor (ir_graph *irg, ir_node *block,
308 ir_node *op1, ir_node *op2, ir_mode *mode)
310 ir_node *in[2] = {op1, op2};
312 res = new_ir_node (irg, block, op_Eor, mode, 2, in);
313 res = optimize (res);
319 new_r_Not (ir_graph *irg, ir_node *block,
320 ir_node *op, ir_mode *mode)
322 ir_node *in[1] = {op};
324 res = new_ir_node (irg, block, op_Not, mode, 1, in);
325 res = optimize (res);
331 new_r_Shl (ir_graph *irg, ir_node *block,
332 ir_node *op, ir_node *k, ir_mode *mode)
334 ir_node *in[2] = {op, k};
336 res = new_ir_node (irg, block, op_Shl, mode, 2, in);
337 res = optimize (res);
343 new_r_Shr (ir_graph *irg, ir_node *block,
344 ir_node *op, ir_node *k, ir_mode *mode)
346 ir_node *in[2] = {op, k};
348 res = new_ir_node (irg, block, op_Shr, mode, 2, in);
349 res = optimize (res);
355 new_r_Shrs (ir_graph *irg, ir_node *block,
356 ir_node *op, ir_node *k, ir_mode *mode)
358 ir_node *in[2] = {op, k};
360 res = new_ir_node (irg, block, op_Shrs, mode, 2, in);
361 res = optimize (res);
367 new_r_Rot (ir_graph *irg, ir_node *block,
368 ir_node *op, ir_node *k, ir_mode *mode)
370 ir_node *in[2] = {op, k};
372 res = new_ir_node (irg, block, op_Rot, mode, 2, in);
373 res = optimize (res);
379 new_r_Abs (ir_graph *irg, ir_node *block,
380 ir_node *op, ir_mode *mode)
382 ir_node *in[1] = {op};
384 res = new_ir_node (irg, block, op_Abs, mode, 1, in);
385 res = optimize (res);
391 new_r_Cmp (ir_graph *irg, ir_node *block,
392 ir_node *op1, ir_node *op2)
394 ir_node *in[2] = {op1, op2};
396 res = new_ir_node (irg, block, op_Cmp, mode_T, 2, in);
397 res = optimize (res);
403 new_r_Jmp (ir_graph *irg, ir_node *block)
407 res = new_ir_node (irg, block, op_Jmp, mode_X, 0, in);
408 res = optimize (res);
414 new_r_Cond (ir_graph *irg, ir_node *block, ir_node *c)
416 ir_node *in[1] = {c};
418 res = new_ir_node (irg, block, op_Cond, mode_T, 1, in);
419 res->attr.c.kind = dense;
420 res->attr.c.default_proj = 0;
421 res = optimize (res);
427 new_r_Call (ir_graph *irg, ir_node *block, ir_node *store,
428 ir_node *callee, int arity, ir_node **in, type *type)
435 NEW_ARR_A (ir_node *, r_in, r_arity);
438 memcpy (&r_in[2], in, sizeof (ir_node *) * arity);
440 res = new_ir_node (irg, block, op_Call, mode_T, r_arity, r_in);
442 assert(is_method_type(type));
443 set_Call_type(res, type);
444 res = optimize (res);
450 new_r_Return (ir_graph *irg, ir_node *block,
451 ir_node *store, int arity, ir_node **in)
458 NEW_ARR_A (ir_node *, r_in, r_arity);
460 memcpy (&r_in[1], in, sizeof (ir_node *) * arity);
461 res = new_ir_node (irg, block, op_Return, mode_X, r_arity, r_in);
462 res = optimize (res);
468 new_r_Raise (ir_graph *irg, ir_node *block, ir_node *store, ir_node *obj)
470 ir_node *in[2] = {store, obj};
472 res = new_ir_node (irg, block, op_Raise, mode_T, 2, in);
474 res = optimize (res);
480 new_r_Load (ir_graph *irg, ir_node *block,
481 ir_node *store, ir_node *adr)
483 ir_node *in[2] = {store, adr};
485 res = new_ir_node (irg, block, op_Load, mode_T, 2, in);
487 res = optimize (res);
493 new_r_Store (ir_graph *irg, ir_node *block,
494 ir_node *store, ir_node *adr, ir_node *val)
496 ir_node *in[3] = {store, adr, val};
498 res = new_ir_node (irg, block, op_Store, mode_T, 3, in);
500 res = optimize (res);
506 new_r_Alloc (ir_graph *irg, ir_node *block, ir_node *store,
507 ir_node *size, type *alloc_type, where_alloc where)
509 ir_node *in[2] = {store, size};
511 res = new_ir_node (irg, block, op_Alloc, mode_T, 2, in);
513 res->attr.a.where = where;
514 res->attr.a.type = alloc_type;
516 res = optimize (res);
522 new_r_Free (ir_graph *irg, ir_node *block, ir_node *store,
523 ir_node *ptr, ir_node *size, type *free_type)
525 ir_node *in[3] = {store, ptr, size};
527 res = new_ir_node (irg, block, op_Free, mode_T, 3, in);
529 res->attr.f = free_type;
531 res = optimize (res);
537 new_r_Sel (ir_graph *irg, ir_node *block, ir_node *store, ir_node *objptr,
538 int arity, ir_node **in, entity *ent)
545 NEW_ARR_A (ir_node *, r_in, r_arity);
548 memcpy (&r_in[2], in, sizeof (ir_node *) * arity);
549 res = new_ir_node (irg, block, op_Sel, mode_p, r_arity, r_in);
551 res->attr.s.ltyp = static_linkage;
552 res->attr.s.ent = ent;
554 res = optimize (res);
560 new_r_SymConst (ir_graph *irg, ir_node *block, type_or_id_p value,
561 symconst_kind symkind)
566 if (symkind == linkage_ptr_info)
570 res = new_ir_node (irg, block, op_SymConst, mode, 0, in);
572 res->attr.i.num = symkind;
573 if (symkind == linkage_ptr_info) {
574 res->attr.i.tori.ptrinfo = (ident *)value;
576 assert ( ( (symkind == type_tag)
577 || (symkind == size))
578 && (is_type(value)));
579 res->attr.i.tori.typ = (type *)value;
581 res = optimize (res);
587 new_r_Sync (ir_graph *irg, ir_node *block, int arity, ir_node **in)
591 res = new_ir_node (irg, block, op_Sync, mode_M, arity, in);
593 res = optimize (res);
601 return current_ir_graph->bad;
604 /** ********************/
605 /** public interfaces */
606 /** construction tools */
608 /****f* ircons/new_Start
611 * new_Start -- create a new Start node in the current block
614 * s = new_Start(void);
615 * ir_node* new_Start(void);
618 * s - pointer to the created Start node
627 res = new_ir_node (current_ir_graph, current_ir_graph->current_block,
628 op_Start, mode_T, 0, NULL);
630 res = optimize (res);
639 res = new_ir_node (current_ir_graph, current_ir_graph->current_block,
640 op_End, mode_X, -1, NULL);
641 res = optimize (res);
647 /* Constructs a Block with a fixed number of predecessors.
648 Does set current_block. Can be used with automatic Phi
649 node construction. */
651 new_Block (int arity, ir_node **in)
655 res = new_r_Block (current_ir_graph, arity, in);
657 /* Create and initialize array for Phi-node construction. */
658 res->attr.block.graph_arr = NEW_ARR_D (ir_node *, current_ir_graph->obst,
659 current_ir_graph->n_loc);
660 memset(res->attr.block.graph_arr, 0, sizeof(ir_node *)*current_ir_graph->n_loc);
662 res = optimize (res);
663 current_ir_graph->current_block = res;
670 /* ***********************************************************************/
671 /* Methods necessary for automatic Phi node creation */
673 ir_node *phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
674 ir_node *get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
675 ir_node *new_r_Phi0 (ir_graph *irg, ir_node *block, ir_mode *mode)
676 ir_node *new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode, ir_node **in, int ins)
678 Call Graph: ( A ---> B == A "calls" B)
680 get_value mature_block
688 get_r_value_internal |
692 new_r_Phi0 new_r_Phi_in
694 * *************************************************************************** */
696 /* Creates a Phi node with 0 predecessors */
698 new_r_Phi0 (ir_graph *irg, ir_node *block, ir_mode *mode)
701 res = new_ir_node (irg, block, op_Phi, mode, 0, NULL);
706 /* There are two implementations of the Phi node construction. The first
707 is faster, but does not work for blocks with more than 2 predecessors.
708 The second works always but is slower and causes more unnecessary Phi
710 Select the implementations by the following preprocessor flag set in
712 #if USE_FAST_PHI_CONSTRUCTION
714 /* This is a stack used for allocating and deallocating nodes in
715 new_r_Phi_in. The original implementation used the obstack
716 to model this stack, now it is explicit. This reduces side effects.
718 #if USE_EXPICIT_PHI_IN_STACK
723 res = (Phi_in_stack *) malloc ( sizeof (Phi_in_stack));
725 res->stack = NEW_ARR_F (ir_node *, 1);
732 free_Phi_in_stack(Phi_in_stack *s) {
737 void free_to_Phi_in_stack(ir_node *phi) {
738 assert(get_irn_opcode(phi) == iro_Phi);
740 if (ARR_LEN(current_ir_graph->Phi_in_stack->stack) ==
741 current_ir_graph->Phi_in_stack->pos)
742 ARR_APP1 (ir_node *, current_ir_graph->Phi_in_stack->stack, phi);
744 current_ir_graph->Phi_in_stack->stack[current_ir_graph->Phi_in_stack->pos] = phi;
746 (current_ir_graph->Phi_in_stack->pos)++;
750 alloc_or_pop_from_Phi_in_stack(ir_graph *irg, ir_node *block, ir_mode *mode,
751 int arity, ir_node **in) {
753 ir_node **stack = current_ir_graph->Phi_in_stack->stack;
754 int pos = current_ir_graph->Phi_in_stack->pos;
758 /* We need to allocate a new node */
759 res = new_ir_node (irg, block, op_Phi, mode, arity, in);
761 /* reuse the old node and initialize it again. */
764 assert (res->kind == k_ir_node);
765 assert (res->op == op_Phi);
770 /* ???!!! How to free the old in array?? */
771 res->in = NEW_ARR_D (ir_node *, irg->obst, (arity+1));
773 memcpy (&res->in[1], in, sizeof (ir_node *) * arity);
775 (current_ir_graph->Phi_in_stack->pos)--;
779 #endif /* USE_EXPICIT_PHI_IN_STACK */
781 /* Creates a Phi node with a given, fixed array **in of predecessors.
782 If the Phi node is unnecessary, as the same value reaches the block
783 through all control flow paths, it is eliminated and the value
784 returned directly. This constructor is only intended for use in
785 the automatic Phi node generation triggered by get_value or mature.
786 The implementation is quite tricky and depends on the fact, that
787 the nodes are allocated on a stack:
788 The in array contains predecessors and NULLs. The NULLs appear,
789 if get_r_value_internal, that computed the predecessors, reached
790 the same block on two paths. In this case the same value reaches
791 this block on both paths, there is no definition in between. We need
792 not allocate a Phi where these path's merge, but we have to communicate
793 this fact to the caller. This happens by returning a pointer to the
794 node the caller _will_ allocate. (Yes, we predict the address. We can
795 do so because the nodes are allocated on the obstack.) The caller then
796 finds a pointer to itself and, when this routine is called again,
800 new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode,
801 ir_node **in, int ins)
804 ir_node *res, *known;
806 /* allocate a new node on the obstack.
807 This can return a node to which some of the pointers in the in-array
809 Attention: the constructor copies the in array, i.e., the later changes
810 to the array in this routine do not affect the constructed node! If
811 the in array contains NULLs, there will be missing predecessors in the
813 Is this a possible internal state of the Phi node generation? */
814 #if USE_EXPICIT_PHI_IN_STACK
815 res = known = alloc_or_pop_from_Phi_in_stack(irg, block, mode, ins, in);
817 res = known = new_ir_node (irg, block, op_Phi, mode, ins, in);
819 /* The in-array can contain NULLs. These were returned by
820 get_r_value_internal if it reached the same block/definition on a
822 The NULLs are replaced by the node itself to simplify the test in the
824 for (i=0; i < ins; ++i)
825 if (in[i] == NULL) in[i] = res;
827 /* This loop checks whether the Phi has more than one predecessor.
828 If so, it is a real Phi node and we break the loop. Else the
829 Phi node merges the same definition on several paths and therefore
831 for (i=0; i < ins; ++i)
833 if (in[i]==res || in[i]==known) continue;
841 /* i==ins: there is at most one predecessor, we don't need a phi node. */
843 #if USE_EXPICIT_PHI_IN_STACK
844 free_to_Phi_in_stack(res);
846 obstack_free (current_ir_graph->obst, res);
850 res = optimize (res);
854 /* return the pointer to the Phi node. This node might be deallocated! */
859 get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
861 /** This function computes the predecessors for a real Phi node, and then
862 allocates and returns this node. The routine called to allocate the
863 node might optimize it away and return a real value, or even a pointer
864 to a deallocated Phi node on top of the obstack!
865 This function is called with an in-array of proper size. **/
866 static inline ir_node *
867 phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
869 ir_node *prevBlock, *res;
872 /* This loop goes to all predecessor blocks of the block the Phi node is in
873 and there finds the operands of the Phi node by calling
874 get_r_value_internal. */
875 for (i = 1; i <= ins; ++i) {
876 assert (block->in[i]);
877 prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */
879 nin[i-1] = get_r_value_internal (prevBlock, pos, mode);
882 /* After collecting all predecessors into the array nin a new Phi node
883 with these predecessors is created. This constructor contains an
884 optimization: If all predecessors of the Phi node are identical it
885 returns the only operand instead of a new Phi node. If the value
886 passes two different control flow edges without being defined, and
887 this is the second path treated, a pointer to the node that will be
888 allocated for the first path (recursion) is returned. We already
889 know the address of this node, as it is the next node to be allocated
890 and will be placed on top of the obstack. (The obstack is a _stack_!) */
891 res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins);
893 /* Now we now the value for "pos" and can enter it in the array with
894 all known local variables. Attention: this might be a pointer to
895 a node, that later will be allocated!!! See new_r_Phi_in.
896 If this is called in mature, after some set_value in the same block,
897 the proper value must not be overwritten:
899 get_value (makes Phi0, put's it into graph_arr)
900 set_value (overwrites Phi0 in graph_arr)
901 mature_block (upgrades Phi0, puts it again into graph_arr, overwriting
904 if (!block->attr.block.graph_arr[pos]) {
905 block->attr.block.graph_arr[pos] = res;
907 /* printf(" value already computed by %s\n",
908 id_to_str(block->attr.block.graph_arr[pos]->op->name)); */
914 /* This function returns the last definition of a variable. In case
915 this variable was last defined in a previous block, Phi nodes are
916 inserted. If the part of the firm graph containing the definition
917 is not yet constructed, a dummy Phi node is returned. */
919 get_r_value_internal (ir_node *block, int pos, ir_mode *mode)
922 /* There are 4 cases to treat.
924 1. The block is not mature and we visit it the first time. We can not
925 create a proper Phi node, therefore a Phi0, i.e., a Phi without
926 predecessors is returned. This node is added to the linked list (field
927 "link") of the containing block to be completed when this block is
928 matured. (Completion will add a new Phi and turn the Phi0 into an Id
931 2. The value is already known in this block, graph_arr[pos] is set and we
932 visit the block the first time. We can return the value without
933 creating any new nodes.
935 3. The block is mature and we visit it the first time. A Phi node needs
936 to be created (phi_merge). If the Phi is not needed, as all it's
937 operands are the same value reaching the block through different
938 paths, it's optimized away and the value itself is returned.
940 4. The block is mature, and we visit it the second time. Now two
941 subcases are possible:
942 * The value was computed completely the last time we were here. This
943 is the case if there is no loop. We can return the proper value.
944 * The recursion that visited this node and set the flag did not
945 return yet. We are computing a value in a loop and need to
946 break the recursion without knowing the result yet.
947 @@@ strange case. Straight forward we would create a Phi before
948 starting the computation of it's predecessors. In this case we will
949 find a Phi here in any case. The problem is that this implementation
950 only creates a Phi after computing the predecessors, so that it is
951 hard to compute self references of this Phi. @@@
952 There is no simple check for the second subcase. Therefore we check
953 for a second visit and treat all such cases as the second subcase.
954 Anyways, the basic situation is the same: we reached a block
955 on two paths without finding a definition of the value: No Phi
956 nodes are needed on both paths.
957 We return this information "Two paths, no Phi needed" by a very tricky
958 implementation that relies on the fact that an obstack is a stack and
959 will return a node with the same address on different allocations.
960 Look also at phi_merge and new_r_phi_in to understand this.
961 @@@ Unfortunately this does not work, see testprogram
962 three_cfpred_example.
966 /* case 4 -- already visited. */
967 if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) return NULL;
969 /* visited the first time */
970 set_irn_visited(block, get_irg_visited(current_ir_graph));
972 /* Get the local valid value */
973 res = block->attr.block.graph_arr[pos];
975 /* case 2 -- If the value is actually computed, return it. */
976 if (res) { return res;};
978 if (block->attr.block.matured) { /* case 3 */
980 /* The Phi has the same amount of ins as the corresponding block. */
981 int ins = get_irn_arity(block);
983 NEW_ARR_A (ir_node *, nin, ins);
985 /* Phi merge collects the predecessors and then creates a node. */
986 res = phi_merge (block, pos, mode, nin, ins);
988 } else { /* case 1 */
989 /* The block is not mature, we don't know how many in's are needed. A Phi
990 with zero predecessors is created. Such a Phi node is called Phi0
991 node. (There is also an obsolete Phi0 opcode.) The Phi0 is then added
992 to the list of Phi0 nodes in this block to be matured by mature_block
994 The Phi0 has to remember the pos of it's internal value. If the real
995 Phi is computed, pos is used to update the array with the local
998 res = new_r_Phi0 (current_ir_graph, block, mode);
999 res->attr.phi0_pos = pos;
1000 res->link = block->link;
1004 /* If we get here, the frontend missed a use-before-definition error */
1007 printf("Error: no value set. Use of undefined variable. Initializing
1009 assert (mode->code >= irm_f && mode->code <= irm_p);
1010 res = new_r_Const (current_ir_graph, block, mode,
1011 tarval_mode_null[mode->code]);
1014 /* The local valid value is available now. */
1015 block->attr.block.graph_arr[pos] = res;
1022 /** This is the simple algorithm. If first generates a Phi0, then
1023 it starts the recursion. This causes an Id at the entry of
1024 every block that has no definition of the value! **/
1026 #if USE_EXPICIT_PHI_IN_STACK
1028 Phi_in_stack * new_Phi_in_stack() { return NULL; }
1029 void free_Phi_in_stack(Phi_in_stack *s) { }
1033 new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode,
1034 ir_node **in, int ins)
1037 ir_node *res, *known;
1039 /* Allocate a new node on the obstack. The allocation copies the in
1041 res = new_ir_node (irg, block, op_Phi, mode, ins, in);
1043 /* This loop checks whether the Phi has more than one predecessor.
1044 If so, it is a real Phi node and we break the loop. Else the
1045 Phi node merges the same definition on several paths and therefore
1046 is not needed. Don't consider Bad nodes! */
1048 for (i=0; i < ins; ++i)
1052 if (in[i]==res || in[i]==known || is_Bad(in[i])) continue;
1060 /* i==ins: there is at most one predecessor, we don't need a phi node. */
1063 obstack_free (current_ir_graph->obst, res);
1066 /* A undefined value, e.g., in unreachable code. */
1070 res = optimize (res);
1072 /* Memory Phis in endless loops must be kept alive.
1073 As we can't distinguish these easily we keep all of the alive. */
1074 if ((res->op == op_Phi) && (mode == mode_M))
1075 add_End_keepalive(irg->end, res);
1082 get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
1084 #if PRECISE_EXC_CONTEXT
1085 static inline ir_node *
1086 phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins);
1089 new_frag_arr (ir_node *n) {
1091 arr = NEW_ARR_D (ir_node *, current_ir_graph->obst, current_ir_graph->n_loc);
1092 memcpy(arr, current_ir_graph->current_block->attr.block.graph_arr,
1093 sizeof(ir_node *)*current_ir_graph->n_loc);
1094 /* Here we rely on the fact that all frag ops have Memory as first result! */
1095 if (get_irn_op(n) == op_Call)
1096 arr[0] = new_Proj(n, mode_M, 3);
1098 arr[0] = new_Proj(n, mode_M, 0);
1099 current_ir_graph->current_block->attr.block.graph_arr[current_ir_graph->n_loc-1] = n;
1104 get_frag_arr (ir_node *n) {
1105 if (get_irn_op(n) == op_Call) {
1106 return n->attr.call.frag_arr;
1107 } else if (get_irn_op(n) == op_Alloc) {
1108 return n->attr.a.frag_arr;
1110 return n->attr.frag_arr;
1115 set_frag_value(ir_node **frag_arr, int pos, ir_node *val) {
1116 if (!frag_arr[pos]) frag_arr[pos] = val;
1117 if (frag_arr[current_ir_graph->n_loc - 1])
1118 set_frag_value (get_frag_arr(frag_arr[current_ir_graph->n_loc - 1]), pos, val);
1122 get_r_frag_value_internal (ir_node *block, ir_node *cfOp, int pos, ir_mode *mode) {
1127 assert(is_fragile_op(cfOp) && (get_irn_op(cfOp) != op_Bad));
1129 frag_arr = get_frag_arr(cfOp);
1130 res = frag_arr[pos];
1132 if (block->attr.block.graph_arr[pos]) {
1133 /* There was a set_value after the cfOp and no get_value before that
1134 set_value. We must build a Phi node now. */
1135 if (block->attr.block.matured) {
1136 int ins = get_irn_arity(block);
1138 NEW_ARR_A (ir_node *, nin, ins);
1139 res = phi_merge(block, pos, mode, nin, ins);
1141 res = new_r_Phi0 (current_ir_graph, block, mode);
1142 res->attr.phi0_pos = pos;
1143 res->link = block->link;
1147 /* It's a Phi, we can write this into all graph_arrs with NULL */
1148 set_frag_value(block->attr.block.graph_arr, pos, res);
1150 res = get_r_value_internal(block, pos, mode);
1151 set_frag_value(block->attr.block.graph_arr, pos, res);
1158 /** This function allocates a dummy Phi node to break recursions,
1159 computes the predecessors for the real phi node, and then
1160 allocates and returns this node. The routine called to allocate the
1161 node might optimize it away and return a real value.
1162 This function is called with an in-array of proper size. **/
1163 static inline ir_node *
1164 phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
1166 ir_node *prevBlock, *prevCfOp, *res, *phi0;
1170 /* If this block has no value at pos create a Phi0 and remember it
1171 in graph_arr to break recursions.
1172 Else we may not set graph_arr as there a later value is remembered. */
1174 if (!block->attr.block.graph_arr[pos]) {
1175 /* This is commented out as collapsing to Bads is no good idea.
1176 Either we need an assert here, or we need to call a routine
1177 that deals with this case as appropriate for the given language.
1178 Right now a self referencing Id is created which will crash irg_vrfy().
1180 Even if all variables are defined before use, it can happen that
1181 we get to the start block, if a cond has been replaced by a tuple
1182 (bad, jmp). As the start has a self referencing control flow edge,
1183 we get a self referencing Id, which is hard to optimize away. We avoid
1184 this by defining the value as a Bad node.
1185 Returning a const with tarval_bad is a preliminary solution. In some
1186 situations we might want a Warning or an Error. */
1188 if (block == get_irg_start_block(current_ir_graph)) {
1189 block->attr.block.graph_arr[pos] = new_Const(mode, tarval_bad);
1190 /* We don't need to care about exception ops in the start block.
1191 There are none by definition. */
1192 return block->attr.block.graph_arr[pos];
1194 phi0 = new_r_Phi0(current_ir_graph, block, mode);
1195 block->attr.block.graph_arr[pos] = phi0;
1196 #if PRECISE_EXC_CONTEXT
1197 /* Set graph_arr for fragile ops. Also here we should break recursion. */
1198 set_frag_value(block->attr.block.graph_arr, pos, phi0);
1203 /* This loop goes to all predecessor blocks of the block the Phi node
1204 is in and there finds the operands of the Phi node by calling
1205 get_r_value_internal. */
1206 for (i = 1; i <= ins; ++i) {
1207 prevCfOp = skip_Proj(block->in[i]);
1209 if (is_Bad(prevCfOp)) {
1210 /* In case a Cond has been optimized we would get right to the start block
1211 with an invalid definition. */
1212 nin[i-1] = new_Bad();
1215 prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */
1217 if (!is_Bad(prevBlock)) {
1218 #if PRECISE_EXC_CONTEXT
1219 if (is_fragile_op(prevCfOp) && (get_irn_op (prevCfOp) != op_Bad)) {
1220 assert(get_r_frag_value_internal (prevBlock, prevCfOp, pos, mode));
1222 nin[i-1] = get_r_frag_value_internal (prevBlock, prevCfOp, pos, mode);
1225 nin[i-1] = get_r_value_internal (prevBlock, pos, mode);
1227 nin[i-1] = new_Bad();
1231 /* After collecting all predecessors into the array nin a new Phi node
1232 with these predecessors is created. This constructor contains an
1233 optimization: If all predecessors of the Phi node are identical it
1234 returns the only operand instead of a new Phi node. */
1235 res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins);
1237 /* In case we allocated a Phi0 node at the beginning of this procedure,
1238 we need to exchange this Phi0 with the real Phi. */
1240 exchange(phi0, res);
1241 block->attr.block.graph_arr[pos] = res;
1242 /* Don't set_frag_value as it does not overwrite. Doesn't matter, is
1243 only an optimization. */
1249 /* This function returns the last definition of a variable. In case
1250 this variable was last defined in a previous block, Phi nodes are
1251 inserted. If the part of the firm graph containing the definition
1252 is not yet constructed, a dummy Phi node is returned. */
1254 get_r_value_internal (ir_node *block, int pos, ir_mode *mode)
1257 /* There are 4 cases to treat.
1259 1. The block is not mature and we visit it the first time. We can not
1260 create a proper Phi node, therefore a Phi0, i.e., a Phi without
1261 predecessors is returned. This node is added to the linked list (field
1262 "link") of the containing block to be completed when this block is
1263 matured. (Comlpletion will add a new Phi and turn the Phi0 into an Id
1266 2. The value is already known in this block, graph_arr[pos] is set and we
1267 visit the block the first time. We can return the value without
1268 creating any new nodes.
1270 3. The block is mature and we visit it the first time. A Phi node needs
1271 to be created (phi_merge). If the Phi is not needed, as all it's
1272 operands are the same value reaching the block through different
1273 paths, it's optimized away and the value itself is returned.
1275 4. The block is mature, and we visit it the second time. Now two
1276 subcases are possible:
1277 * The value was computed completely the last time we were here. This
1278 is the case if there is no loop. We can return the proper value.
1279 * The recursion that visited this node and set the flag did not
1280 return yet. We are computing a value in a loop and need to
1281 break the recursion. This case only happens if we visited
1282 the same block with phi_merge before, which inserted a Phi0.
1283 So we return the Phi0.
1286 /* case 4 -- already visited. */
1287 if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) {
1288 /* As phi_merge allocates a Phi0 this value is always defined. Here
1289 is the critical difference of the two algorithms. */
1290 assert(block->attr.block.graph_arr[pos]);
1291 return block->attr.block.graph_arr[pos];
1294 /* visited the first time */
1295 set_irn_visited(block, get_irg_visited(current_ir_graph));
1297 /* Get the local valid value */
1298 res = block->attr.block.graph_arr[pos];
1300 /* case 2 -- If the value is actually computed, return it. */
1301 if (res) { return res; };
1303 if (block->attr.block.matured) { /* case 3 */
1305 /* The Phi has the same amount of ins as the corresponding block. */
1306 int ins = get_irn_arity(block);
1308 NEW_ARR_A (ir_node *, nin, ins);
1310 /* Phi merge collects the predecessors and then creates a node. */
1311 res = phi_merge (block, pos, mode, nin, ins);
1313 } else { /* case 1 */
1314 /* The block is not mature, we don't know how many in's are needed. A Phi
1315 with zero predecessors is created. Such a Phi node is called Phi0
1316 node. The Phi0 is then added to the list of Phi0 nodes in this block
1317 to be matured by mature_block later.
1318 The Phi0 has to remember the pos of it's internal value. If the real
1319 Phi is computed, pos is used to update the array with the local
1321 res = new_r_Phi0 (current_ir_graph, block, mode);
1322 res->attr.phi0_pos = pos;
1323 res->link = block->link;
1327 /* If we get here, the frontend missed a use-before-definition error */
1330 printf("Error: no value set. Use of undefined variable. Initializing
1332 assert (mode->code >= irm_f && mode->code <= irm_p);
1333 res = new_r_Const (current_ir_graph, block, mode,
1334 tarval_mode_null[mode->code]);
1337 /* The local valid value is available now. */
1338 block->attr.block.graph_arr[pos] = res;
1343 #endif /* USE_FAST_PHI_CONSTRUCTION */
1345 /* ************************************************************************** */
1347 /** Finalize a Block node, when all control flows are known. */
1348 /** Acceptable parameters are only Block nodes. */
1350 mature_block (ir_node *block)
1357 assert (get_irn_opcode(block) == iro_Block);
1359 if (!get_Block_matured(block)) {
1361 /* an in-array for phi-merge with same size. */
1362 ins = ARR_LEN (block->in)-1;
1363 NEW_ARR_A (ir_node *, nin, ins);
1365 /* Traverse a chain of Phi nodes attached to this block and mature
1367 for (n = block->link; n; n=next) {
1368 inc_irg_visited(current_ir_graph);
1370 exchange (n, phi_merge (block, n->attr.phi0_pos, n->mode, nin, ins));
1373 block->attr.block.matured = 1;
1375 /* Now, as the block is a finished firm node, we can optimize it.
1376 Since other nodes have been allocated since the block was created
1377 we can not free the node on the obstack. Therefore we have to call
1379 Unfortunately the optimization does not change a lot, as all allocated
1380 nodes refer to the unoptimized node.
1381 We can call _2, as global cse has no effect on blocks. */
1382 block = optimize_in_place_2(block);
1388 new_Phi (int arity, ir_node **in, ir_mode *mode)
1390 return new_r_Phi (current_ir_graph, current_ir_graph->current_block,
1395 new_Const (ir_mode *mode, tarval *con)
1397 return new_r_Const (current_ir_graph, current_ir_graph->start_block,
1402 new_Id (ir_node *val, ir_mode *mode)
1404 return new_r_Id (current_ir_graph, current_ir_graph->current_block,
1409 new_Proj (ir_node *arg, ir_mode *mode, long proj)
1411 return new_r_Proj (current_ir_graph, current_ir_graph->current_block,
1416 new_defaultProj (ir_node *arg, long max_proj)
1419 assert((arg->op==op_Cond) && (get_irn_mode(arg->in[1]) == mode_I));
1420 arg->attr.c.kind = fragmentary;
1421 arg->attr.c.default_proj = max_proj;
1422 res = new_Proj (arg, mode_X, max_proj);
1427 new_Conv (ir_node *op, ir_mode *mode)
1429 return new_r_Conv (current_ir_graph, current_ir_graph->current_block,
1434 new_Tuple (int arity, ir_node **in)
1436 return new_r_Tuple (current_ir_graph, current_ir_graph->current_block,
1441 new_Add (ir_node *op1, ir_node *op2, ir_mode *mode)
1443 return new_r_Add (current_ir_graph, current_ir_graph->current_block,
1448 new_Sub (ir_node *op1, ir_node *op2, ir_mode *mode)
1450 return new_r_Sub (current_ir_graph, current_ir_graph->current_block,
1456 new_Minus (ir_node *op, ir_mode *mode)
1458 return new_r_Minus (current_ir_graph, current_ir_graph->current_block,
1463 new_Mul (ir_node *op1, ir_node *op2, ir_mode *mode)
1465 return new_r_Mul (current_ir_graph, current_ir_graph->current_block,
1470 new_Quot (ir_node *memop, ir_node *op1, ir_node *op2)
1473 res = new_r_Quot (current_ir_graph, current_ir_graph->current_block,
1475 #if PRECISE_EXC_CONTEXT
1476 res->attr.frag_arr = new_frag_arr(res);
1483 new_DivMod (ir_node *memop, ir_node *op1, ir_node *op2)
1486 res = new_r_DivMod (current_ir_graph, current_ir_graph->current_block,
1488 #if PRECISE_EXC_CONTEXT
1489 res->attr.frag_arr = new_frag_arr(res);
1496 new_Div (ir_node *memop, ir_node *op1, ir_node *op2)
1499 res = new_r_Div (current_ir_graph, current_ir_graph->current_block,
1501 #if PRECISE_EXC_CONTEXT
1502 res->attr.frag_arr = new_frag_arr(res);
1509 new_Mod (ir_node *memop, ir_node *op1, ir_node *op2)
1512 res = new_r_Mod (current_ir_graph, current_ir_graph->current_block,
1514 #if PRECISE_EXC_CONTEXT
1515 res->attr.frag_arr = new_frag_arr(res);
1522 new_And (ir_node *op1, ir_node *op2, ir_mode *mode)
1524 return new_r_And (current_ir_graph, current_ir_graph->current_block,
1529 new_Or (ir_node *op1, ir_node *op2, ir_mode *mode)
1531 return new_r_Or (current_ir_graph, current_ir_graph->current_block,
1536 new_Eor (ir_node *op1, ir_node *op2, ir_mode *mode)
1538 return new_r_Eor (current_ir_graph, current_ir_graph->current_block,
1543 new_Not (ir_node *op, ir_mode *mode)
1545 return new_r_Not (current_ir_graph, current_ir_graph->current_block,
1550 new_Shl (ir_node *op, ir_node *k, ir_mode *mode)
1552 return new_r_Shl (current_ir_graph, current_ir_graph->current_block,
1557 new_Shr (ir_node *op, ir_node *k, ir_mode *mode)
1559 return new_r_Shr (current_ir_graph, current_ir_graph->current_block,
1564 new_Shrs (ir_node *op, ir_node *k, ir_mode *mode)
1566 return new_r_Shrs (current_ir_graph, current_ir_graph->current_block,
1571 new_Rotate (ir_node *op, ir_node *k, ir_mode *mode)
1573 return new_r_Rot (current_ir_graph, current_ir_graph->current_block,
1578 new_Abs (ir_node *op, ir_mode *mode)
1580 return new_r_Abs (current_ir_graph, current_ir_graph->current_block,
1585 new_Cmp (ir_node *op1, ir_node *op2)
1587 return new_r_Cmp (current_ir_graph, current_ir_graph->current_block,
1594 return new_r_Jmp (current_ir_graph, current_ir_graph->current_block);
1598 new_Cond (ir_node *c)
1600 return new_r_Cond (current_ir_graph, current_ir_graph->current_block, c);
1604 new_Call (ir_node *store, ir_node *callee, int arity, ir_node **in,
1608 res = new_r_Call (current_ir_graph, current_ir_graph->current_block,
1609 store, callee, arity, in, type);
1610 #if PRECISE_EXC_CONTEXT
1611 res->attr.call.frag_arr = new_frag_arr(res);
1618 new_Return (ir_node* store, int arity, ir_node **in)
1620 return new_r_Return (current_ir_graph, current_ir_graph->current_block,
1625 new_Raise (ir_node *store, ir_node *obj)
1627 return new_r_Raise (current_ir_graph, current_ir_graph->current_block,
1632 new_Load (ir_node *store, ir_node *addr)
1635 res = new_r_Load (current_ir_graph, current_ir_graph->current_block,
1637 #if PRECISE_EXC_CONTEXT
1638 res->attr.frag_arr = new_frag_arr(res);
1645 new_Store (ir_node *store, ir_node *addr, ir_node *val)
1648 res = new_r_Store (current_ir_graph, current_ir_graph->current_block,
1650 #if PRECISE_EXC_CONTEXT
1651 res->attr.frag_arr = new_frag_arr(res);
1658 new_Alloc (ir_node *store, ir_node *size, type *alloc_type,
1662 res = new_r_Alloc (current_ir_graph, current_ir_graph->current_block,
1663 store, size, alloc_type, where);
1664 #if PRECISE_EXC_CONTEXT
1665 res->attr.a.frag_arr = new_frag_arr(res);
1672 new_Free (ir_node *store, ir_node *ptr, ir_node *size, type *free_type)
1674 return new_r_Free (current_ir_graph, current_ir_graph->current_block,
1675 store, ptr, size, free_type);
1679 new_simpleSel (ir_node *store, ir_node *objptr, entity *ent)
1680 /* GL: objptr was called frame before. Frame was a bad choice for the name
1681 as the operand could as well be a pointer to a dynamic object. */
1683 return new_r_Sel (current_ir_graph, current_ir_graph->current_block,
1684 store, objptr, 0, NULL, ent);
1688 new_Sel (ir_node *store, ir_node *objptr, int n_index, ir_node **index, entity *sel)
1690 return new_r_Sel (current_ir_graph, current_ir_graph->current_block,
1691 store, objptr, n_index, index, sel);
1695 new_SymConst (type_or_id_p value, symconst_kind kind)
1697 return new_r_SymConst (current_ir_graph, current_ir_graph->current_block,
1702 new_Sync (int arity, ir_node** in)
1704 return new_r_Sync (current_ir_graph, current_ir_graph->current_block,
1712 return current_ir_graph->bad;
1715 /* ********************************************************************* */
1716 /* Comfortable interface with automatic Phi node construction. */
1717 /* (Uses also constructors of ?? interface, except new_Block. */
1718 /* ********************************************************************* */
1720 /** Block construction **/
1721 /* immature Block without predecessors */
1722 ir_node *new_immBlock (void) {
1725 assert(get_irg_phase_state (current_ir_graph) == phase_building);
1726 /* creates a new dynamic in-array as length of in is -1 */
1727 res = new_ir_node (current_ir_graph, NULL, op_Block, mode_R, -1, NULL);
1728 current_ir_graph->current_block = res;
1729 res->attr.block.matured = 0;
1730 set_Block_block_visited(res, 0);
1732 /* Create and initialize array for Phi-node construction. */
1733 res->attr.block.graph_arr = NEW_ARR_D (ir_node *, current_ir_graph->obst,
1734 current_ir_graph->n_loc);
1735 memset(res->attr.block.graph_arr, 0, sizeof(ir_node *)*current_ir_graph->n_loc);
1737 /* Immature block may not be optimized! */
1743 /* add an adge to a jmp/control flow node */
1745 add_in_edge (ir_node *block, ir_node *jmp)
1747 if (block->attr.block.matured) {
1748 assert(0 && "Error: Block already matured!\n");
1751 assert (jmp != NULL);
1752 ARR_APP1 (ir_node *, block->in, jmp);
1756 /* changing the current block */
1758 switch_block (ir_node *target)
1760 current_ir_graph->current_block = target;
1763 /* ************************ */
1764 /* parameter administration */
1766 /* get a value from the parameter array from the current block by its index */
1768 get_value (int pos, ir_mode *mode)
1770 assert(get_irg_phase_state (current_ir_graph) == phase_building);
1771 inc_irg_visited(current_ir_graph);
1772 return get_r_value_internal (current_ir_graph->current_block, pos + 1, mode);
1776 /* set a value at position pos in the parameter array from the current block */
1778 set_value (int pos, ir_node *value)
1780 assert(get_irg_phase_state (current_ir_graph) == phase_building);
1781 current_ir_graph->current_block->attr.block.graph_arr[pos + 1] = value;
1784 /* get the current store */
1788 assert(get_irg_phase_state (current_ir_graph) == phase_building);
1789 /* GL: one could call get_value instead */
1790 inc_irg_visited(current_ir_graph);
1791 return get_r_value_internal (current_ir_graph->current_block, 0, mode_M);
1794 /* set the current store */
1796 set_store (ir_node *store)
1798 assert(get_irg_phase_state (current_ir_graph) == phase_building);
1799 /* GL: one could call set_value instead */
1800 current_ir_graph->current_block->attr.block.graph_arr[0] = store;
1804 keep_alive (ir_node *ka)
1806 add_End_keepalive(current_ir_graph->end, ka);
1809 /** Useful access routines **/
1810 /* Returns the current block of the current graph. To set the current
1811 block use switch_block(). */
1812 ir_node *get_cur_block() {
1813 return get_irg_current_block(current_ir_graph);
1816 /* Returns the frame type of the current graph */
1817 type *get_cur_frame_type() {
1818 return get_irg_frame_type(current_ir_graph);
1822 /* ********************************************************************* */
1825 /* call once for each run of the library */
1831 /* call for each graph */
1833 finalize_cons (ir_graph *irg) {
1834 irg->phase_state = phase_high;