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);
640 res = new_ir_node (current_ir_graph, current_ir_graph->current_block,
641 op_End, mode_X, -1, NULL);
643 res = optimize (res);
649 /* Constructs a Block with a fixed number of predecessors.
650 Does set current_block. Can be used with automatic Phi
651 node construction. */
653 new_Block (int arity, ir_node **in)
657 res = new_r_Block (current_ir_graph, arity, in);
659 /* Create and initialize array for Phi-node construction. */
660 res->attr.block.graph_arr = NEW_ARR_D (ir_node *, current_ir_graph->obst,
661 current_ir_graph->n_loc);
662 memset(res->attr.block.graph_arr, 0, sizeof(ir_node *)*current_ir_graph->n_loc);
664 res = optimize (res);
665 current_ir_graph->current_block = res;
672 /* ***********************************************************************/
673 /* Methods necessary for automatic Phi node creation */
675 ir_node *phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
676 ir_node *get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
677 ir_node *new_r_Phi0 (ir_graph *irg, ir_node *block, ir_mode *mode)
678 ir_node *new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode, ir_node **in, int ins)
680 Call Graph: ( A ---> B == A "calls" B)
682 get_value mature_block
690 get_r_value_internal |
694 new_r_Phi0 new_r_Phi_in
696 * *************************************************************************** */
698 /* Creates a Phi node with 0 predecessors */
700 new_r_Phi0 (ir_graph *irg, ir_node *block, ir_mode *mode)
703 res = new_ir_node (irg, block, op_Phi, mode, 0, NULL);
708 /* There are two implementations of the Phi node construction. The first
709 is faster, but does not work for blocks with more than 2 predecessors.
710 The second works always but is slower and causes more unnecessary Phi
712 Select the implementations by the following preprocessor flag set in
714 #if USE_FAST_PHI_CONSTRUCTION
716 /* This is a stack used for allocating and deallocating nodes in
717 new_r_Phi_in. The original implementation used the obstack
718 to model this stack, now it is explicit. This reduces side effects.
720 #if USE_EXPICIT_PHI_IN_STACK
725 res = (Phi_in_stack *) malloc ( sizeof (Phi_in_stack));
727 res->stack = NEW_ARR_F (ir_node *, 1);
734 free_Phi_in_stack(Phi_in_stack *s) {
739 void free_to_Phi_in_stack(ir_node *phi) {
740 assert(get_irn_opcode(phi) == iro_Phi);
742 if (ARR_LEN(current_ir_graph->Phi_in_stack->stack) ==
743 current_ir_graph->Phi_in_stack->pos)
744 ARR_APP1 (ir_node *, current_ir_graph->Phi_in_stack->stack, phi);
746 current_ir_graph->Phi_in_stack->stack[current_ir_graph->Phi_in_stack->pos] = phi;
748 (current_ir_graph->Phi_in_stack->pos)++;
752 alloc_or_pop_from_Phi_in_stack(ir_graph *irg, ir_node *block, ir_mode *mode,
753 int arity, ir_node **in) {
755 ir_node **stack = current_ir_graph->Phi_in_stack->stack;
756 int pos = current_ir_graph->Phi_in_stack->pos;
760 /* We need to allocate a new node */
761 res = new_ir_node (irg, block, op_Phi, mode, arity, in);
763 /* reuse the old node and initialize it again. */
766 assert (res->kind == k_ir_node);
767 assert (res->op == op_Phi);
772 /* ???!!! How to free the old in array?? */
773 res->in = NEW_ARR_D (ir_node *, irg->obst, (arity+1));
775 memcpy (&res->in[1], in, sizeof (ir_node *) * arity);
777 (current_ir_graph->Phi_in_stack->pos)--;
781 #endif /* USE_EXPICIT_PHI_IN_STACK */
783 /* Creates a Phi node with a given, fixed array **in of predecessors.
784 If the Phi node is unnecessary, as the same value reaches the block
785 through all control flow paths, it is eliminated and the value
786 returned directly. This constructor is only intended for use in
787 the automatic Phi node generation triggered by get_value or mature.
788 The implementation is quite tricky and depends on the fact, that
789 the nodes are allocated on a stack:
790 The in array contains predecessors and NULLs. The NULLs appear,
791 if get_r_value_internal, that computed the predecessors, reached
792 the same block on two paths. In this case the same value reaches
793 this block on both paths, there is no definition in between. We need
794 not allocate a Phi where these path's merge, but we have to communicate
795 this fact to the caller. This happens by returning a pointer to the
796 node the caller _will_ allocate. (Yes, we predict the address. We can
797 do so because the nodes are allocated on the obstack.) The caller then
798 finds a pointer to itself and, when this routine is called again,
802 new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode,
803 ir_node **in, int ins)
806 ir_node *res, *known;
808 /* allocate a new node on the obstack.
809 This can return a node to which some of the pointers in the in-array
811 Attention: the constructor copies the in array, i.e., the later changes
812 to the array in this routine do not affect the constructed node! If
813 the in array contains NULLs, there will be missing predecessors in the
815 Is this a possible internal state of the Phi node generation? */
816 #if USE_EXPICIT_PHI_IN_STACK
817 res = known = alloc_or_pop_from_Phi_in_stack(irg, block, mode, ins, in);
819 res = known = new_ir_node (irg, block, op_Phi, mode, ins, in);
821 /* The in-array can contain NULLs. These were returned by
822 get_r_value_internal if it reached the same block/definition on a
824 The NULLs are replaced by the node itself to simplify the test in the
826 for (i=0; i < ins; ++i)
827 if (in[i] == NULL) in[i] = res;
829 /* This loop checks whether the Phi has more than one predecessor.
830 If so, it is a real Phi node and we break the loop. Else the
831 Phi node merges the same definition on several paths and therefore
833 for (i=0; i < ins; ++i)
835 if (in[i]==res || in[i]==known) continue;
843 /* i==ins: there is at most one predecessor, we don't need a phi node. */
845 #if USE_EXPICIT_PHI_IN_STACK
846 free_to_Phi_in_stack(res);
848 obstack_free (current_ir_graph->obst, res);
852 res = optimize (res);
856 /* return the pointer to the Phi node. This node might be deallocated! */
861 get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
863 /** This function computes the predecessors for a real Phi node, and then
864 allocates and returns this node. The routine called to allocate the
865 node might optimize it away and return a real value, or even a pointer
866 to a deallocated Phi node on top of the obstack!
867 This function is called with an in-array of proper size. **/
868 static inline ir_node *
869 phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
871 ir_node *prevBlock, *res;
874 /* This loop goes to all predecessor blocks of the block the Phi node is in
875 and there finds the operands of the Phi node by calling
876 get_r_value_internal. */
877 for (i = 1; i <= ins; ++i) {
878 assert (block->in[i]);
879 prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */
881 nin[i-1] = get_r_value_internal (prevBlock, pos, mode);
884 /* After collecting all predecessors into the array nin a new Phi node
885 with these predecessors is created. This constructor contains an
886 optimization: If all predecessors of the Phi node are identical it
887 returns the only operand instead of a new Phi node. If the value
888 passes two different control flow edges without being defined, and
889 this is the second path treated, a pointer to the node that will be
890 allocated for the first path (recursion) is returned. We already
891 know the address of this node, as it is the next node to be allocated
892 and will be placed on top of the obstack. (The obstack is a _stack_!) */
893 res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins);
895 /* Now we now the value for "pos" and can enter it in the array with
896 all known local variables. Attention: this might be a pointer to
897 a node, that later will be allocated!!! See new_r_Phi_in.
898 If this is called in mature, after some set_value in the same block,
899 the proper value must not be overwritten:
901 get_value (makes Phi0, put's it into graph_arr)
902 set_value (overwrites Phi0 in graph_arr)
903 mature_block (upgrades Phi0, puts it again into graph_arr, overwriting
906 if (!block->attr.block.graph_arr[pos]) {
907 block->attr.block.graph_arr[pos] = res;
909 /* printf(" value already computed by %s\n",
910 id_to_str(block->attr.block.graph_arr[pos]->op->name)); */
916 /* This function returns the last definition of a variable. In case
917 this variable was last defined in a previous block, Phi nodes are
918 inserted. If the part of the firm graph containing the definition
919 is not yet constructed, a dummy Phi node is returned. */
921 get_r_value_internal (ir_node *block, int pos, ir_mode *mode)
924 /* There are 4 cases to treat.
926 1. The block is not mature and we visit it the first time. We can not
927 create a proper Phi node, therefore a Phi0, i.e., a Phi without
928 predecessors is returned. This node is added to the linked list (field
929 "link") of the containing block to be completed when this block is
930 matured. (Completion will add a new Phi and turn the Phi0 into an Id
933 2. The value is already known in this block, graph_arr[pos] is set and we
934 visit the block the first time. We can return the value without
935 creating any new nodes.
937 3. The block is mature and we visit it the first time. A Phi node needs
938 to be created (phi_merge). If the Phi is not needed, as all it's
939 operands are the same value reaching the block through different
940 paths, it's optimized away and the value itself is returned.
942 4. The block is mature, and we visit it the second time. Now two
943 subcases are possible:
944 * The value was computed completely the last time we were here. This
945 is the case if there is no loop. We can return the proper value.
946 * The recursion that visited this node and set the flag did not
947 return yet. We are computing a value in a loop and need to
948 break the recursion without knowing the result yet.
949 @@@ strange case. Straight forward we would create a Phi before
950 starting the computation of it's predecessors. In this case we will
951 find a Phi here in any case. The problem is that this implementation
952 only creates a Phi after computing the predecessors, so that it is
953 hard to compute self references of this Phi. @@@
954 There is no simple check for the second subcase. Therefore we check
955 for a second visit and treat all such cases as the second subcase.
956 Anyways, the basic situation is the same: we reached a block
957 on two paths without finding a definition of the value: No Phi
958 nodes are needed on both paths.
959 We return this information "Two paths, no Phi needed" by a very tricky
960 implementation that relies on the fact that an obstack is a stack and
961 will return a node with the same address on different allocations.
962 Look also at phi_merge and new_r_phi_in to understand this.
963 @@@ Unfortunately this does not work, see testprogram
964 three_cfpred_example.
968 /* case 4 -- already visited. */
969 if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) return NULL;
971 /* visited the first time */
972 set_irn_visited(block, get_irg_visited(current_ir_graph));
974 /* Get the local valid value */
975 res = block->attr.block.graph_arr[pos];
977 /* case 2 -- If the value is actually computed, return it. */
978 if (res) { return res;};
980 if (block->attr.block.matured) { /* case 3 */
982 /* The Phi has the same amount of ins as the corresponding block. */
983 int ins = get_irn_arity(block);
985 NEW_ARR_A (ir_node *, nin, ins);
987 /* Phi merge collects the predecessors and then creates a node. */
988 res = phi_merge (block, pos, mode, nin, ins);
990 } else { /* case 1 */
991 /* The block is not mature, we don't know how many in's are needed. A Phi
992 with zero predecessors is created. Such a Phi node is called Phi0
993 node. (There is also an obsolete Phi0 opcode.) The Phi0 is then added
994 to the list of Phi0 nodes in this block to be matured by mature_block
996 The Phi0 has to remember the pos of it's internal value. If the real
997 Phi is computed, pos is used to update the array with the local
1000 res = new_r_Phi0 (current_ir_graph, block, mode);
1001 res->attr.phi0_pos = pos;
1002 res->link = block->link;
1006 /* If we get here, the frontend missed a use-before-definition error */
1009 printf("Error: no value set. Use of undefined variable. Initializing
1011 assert (mode->code >= irm_f && mode->code <= irm_p);
1012 res = new_r_Const (current_ir_graph, block, mode,
1013 tarval_mode_null[mode->code]);
1016 /* The local valid value is available now. */
1017 block->attr.block.graph_arr[pos] = res;
1024 /** This is the simple algorithm. If first generates a Phi0, then
1025 it starts the recursion. This causes an Id at the entry of
1026 every block that has no definition of the value! **/
1028 #if USE_EXPICIT_PHI_IN_STACK
1030 Phi_in_stack * new_Phi_in_stack() { return NULL; }
1031 void free_Phi_in_stack(Phi_in_stack *s) { }
1035 new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode,
1036 ir_node **in, int ins)
1039 ir_node *res, *known;
1041 /* Allocate a new node on the obstack. The allocation copies the in
1043 res = new_ir_node (irg, block, op_Phi, mode, ins, in);
1045 /* This loop checks whether the Phi has more than one predecessor.
1046 If so, it is a real Phi node and we break the loop. Else the
1047 Phi node merges the same definition on several paths and therefore
1048 is not needed. Don't consider Bad nodes! */
1050 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));
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 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;
1146 set_frag_value(frag_arr, pos, res);
1148 res = get_r_value_internal(block, pos, mode);
1155 /** This function allocates a dummy Phi node to break recursions,
1156 computes the predecessors for the real phi node, and then
1157 allocates and returns this node. The routine called to allocate the
1158 node might optimize it away and return a real value.
1159 This function is called with an in-array of proper size. **/
1160 static inline ir_node *
1161 phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
1163 ir_node *prevBlock, *prevCfOp, *res, *phi0;
1167 /* If this block has no value at pos create a Phi0 and remember it
1168 in graph_arr to break recursions.
1169 Else we may not set graph_arr as there a later value is remembered. */
1171 if (!block->attr.block.graph_arr[pos]) {
1172 /* This is commented out as collapsing to Bads is no good idea.
1173 Either we need an assert here, or we need to call a routine
1174 that deals with this case as appropriate for the given language.
1175 Right now a self referencing Id is created which will crash irg_vrfy().
1177 Even if all variables are defined before use, it can happen that
1178 we get to the start block, if a cond has been replaced by a tuple
1179 (bad, jmp). As the start has a self referencing control flow edge,
1180 we get a self referencing Id, which is hard to optimize away. We avoid
1181 this by defining the value as a Bad node.
1182 Returning a const with tarval_bad is a preliminary solution. In some
1183 situations we might want a Warning or an Error. */
1185 if (block == get_irg_start_block(current_ir_graph)) {
1186 block->attr.block.graph_arr[pos] = new_Const(mode, tarval_bad);
1187 /* We don't need to care about exception ops in the start block.
1188 There are none by definition. */
1189 return block->attr.block.graph_arr[pos];
1191 phi0 = new_r_Phi0(current_ir_graph, block, mode);
1192 block->attr.block.graph_arr[pos] = phi0;
1193 #if PRECISE_EXC_CONTEXT
1194 /* Set graph_arr for fragile ops. Also here we should break recursion. */
1195 set_frag_value(block->attr.block.graph_arr, pos, phi0);
1200 /* This loop goes to all predecessor blocks of the block the Phi node
1201 is in and there finds the operands of the Phi node by calling
1202 get_r_value_internal. */
1203 for (i = 1; i <= ins; ++i) {
1204 prevCfOp = skip_Proj(block->in[i]);
1206 if (is_Bad(prevCfOp)) {
1207 /* In case a Cond has been optimized we would get right to the start block
1208 with an invalid definition. */
1209 nin[i-1] = new_Bad();
1212 prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */
1214 if (!is_Bad(prevBlock)) {
1215 #if PRECISE_EXC_CONTEXT
1216 if (is_fragile_op(prevCfOp))
1217 nin[i-1] = get_r_frag_value_internal (prevBlock, prevCfOp, pos, mode);
1220 nin[i-1] = get_r_value_internal (prevBlock, pos, mode);
1222 nin[i-1] = new_Bad();
1226 /* After collecting all predecessors into the array nin a new Phi node
1227 with these predecessors is created. This constructor contains an
1228 optimization: If all predecessors of the Phi node are identical it
1229 returns the only operand instead of a new Phi node. */
1230 res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins);
1232 /* In case we allocated a Phi0 node at the beginning of this procedure,
1233 we need to exchange this Phi0 with the real Phi. */
1235 exchange(phi0, res);
1236 block->attr.block.graph_arr[pos] = res;
1237 /* Don't set_frag_value as it does not overwrite. Doesn't matter, is
1238 only an optimization. */
1244 /* This function returns the last definition of a variable. In case
1245 this variable was last defined in a previous block, Phi nodes are
1246 inserted. If the part of the firm graph containing the definition
1247 is not yet constructed, a dummy Phi node is returned. */
1249 get_r_value_internal (ir_node *block, int pos, ir_mode *mode)
1252 /* There are 4 cases to treat.
1254 1. The block is not mature and we visit it the first time. We can not
1255 create a proper Phi node, therefore a Phi0, i.e., a Phi without
1256 predecessors is returned. This node is added to the linked list (field
1257 "link") of the containing block to be completed when this block is
1258 matured. (Comlpletion will add a new Phi and turn the Phi0 into an Id
1261 2. The value is already known in this block, graph_arr[pos] is set and we
1262 visit the block the first time. We can return the value without
1263 creating any new nodes.
1265 3. The block is mature and we visit it the first time. A Phi node needs
1266 to be created (phi_merge). If the Phi is not needed, as all it's
1267 operands are the same value reaching the block through different
1268 paths, it's optimized away and the value itself is returned.
1270 4. The block is mature, and we visit it the second time. Now two
1271 subcases are possible:
1272 * The value was computed completely the last time we were here. This
1273 is the case if there is no loop. We can return the proper value.
1274 * The recursion that visited this node and set the flag did not
1275 return yet. We are computing a value in a loop and need to
1276 break the recursion. This case only happens if we visited
1277 the same block with phi_merge before, which inserted a Phi0.
1278 So we return the Phi0.
1281 /* case 4 -- already visited. */
1282 if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) {
1283 /* As phi_merge allocates a Phi0 this value is always defined. Here
1284 is the critical difference of the two algorithms. */
1285 assert(block->attr.block.graph_arr[pos]);
1286 return block->attr.block.graph_arr[pos];
1289 /* visited the first time */
1290 set_irn_visited(block, get_irg_visited(current_ir_graph));
1292 /* Get the local valid value */
1293 res = block->attr.block.graph_arr[pos];
1295 /* case 2 -- If the value is actually computed, return it. */
1296 if (res) { return res; };
1298 if (block->attr.block.matured) { /* case 3 */
1300 /* The Phi has the same amount of ins as the corresponding block. */
1301 int ins = get_irn_arity(block);
1303 NEW_ARR_A (ir_node *, nin, ins);
1305 /* Phi merge collects the predecessors and then creates a node. */
1306 res = phi_merge (block, pos, mode, nin, ins);
1308 } else { /* case 1 */
1309 /* The block is not mature, we don't know how many in's are needed. A Phi
1310 with zero predecessors is created. Such a Phi node is called Phi0
1311 node. The Phi0 is then added to the list of Phi0 nodes in this block
1312 to be matured by mature_block later.
1313 The Phi0 has to remember the pos of it's internal value. If the real
1314 Phi is computed, pos is used to update the array with the local
1316 res = new_r_Phi0 (current_ir_graph, block, mode);
1317 res->attr.phi0_pos = pos;
1318 res->link = block->link;
1322 /* If we get here, the frontend missed a use-before-definition error */
1325 printf("Error: no value set. Use of undefined variable. Initializing
1327 assert (mode->code >= irm_f && mode->code <= irm_p);
1328 res = new_r_Const (current_ir_graph, block, mode,
1329 tarval_mode_null[mode->code]);
1332 /* The local valid value is available now. */
1333 block->attr.block.graph_arr[pos] = res;
1338 #endif /* USE_FAST_PHI_CONSTRUCTION */
1340 /* ************************************************************************** */
1342 /** Finalize a Block node, when all control flows are known. */
1343 /** Acceptable parameters are only Block nodes. */
1345 mature_block (ir_node *block)
1352 assert (get_irn_opcode(block) == iro_Block);
1354 if (!get_Block_matured(block)) {
1356 /* turn the dynamic in-array into a static one. */
1357 ins = ARR_LEN (block->in)-1;
1358 NEW_ARR_A (ir_node *, nin, ins);
1359 /* @@@ something is strange here... why isn't the array copied? */
1361 /* Traverse a chain of Phi nodes attached to this block and mature
1363 for (n = block->link; n; n=next) {
1364 inc_irg_visited(current_ir_graph);
1366 exchange (n, phi_merge (block, n->attr.phi0_pos, n->mode, nin, ins));
1369 block->attr.block.matured = 1;
1371 /* Now, as the block is a finished firm node, we can optimize it.
1372 Since other nodes have been allocated since the block was created
1373 we can not free the node on the obstack. Therefore we have to call
1375 Unfortunately the optimization does not change a lot, as all allocated
1376 nodes refer to the unoptimized node. */
1377 block = optimize_in_place(block);
1383 new_Phi (int arity, ir_node **in, ir_mode *mode)
1385 return new_r_Phi (current_ir_graph, current_ir_graph->current_block,
1390 new_Const (ir_mode *mode, tarval *con)
1392 return new_r_Const (current_ir_graph, current_ir_graph->start_block,
1397 new_Id (ir_node *val, ir_mode *mode)
1399 return new_r_Id (current_ir_graph, current_ir_graph->current_block,
1404 new_Proj (ir_node *arg, ir_mode *mode, long proj)
1406 return new_r_Proj (current_ir_graph, current_ir_graph->current_block,
1411 new_defaultProj (ir_node *arg, long max_proj)
1414 assert((arg->op==op_Cond) && (get_irn_mode(arg->in[1]) == mode_I));
1415 arg->attr.c.kind = fragmentary;
1416 arg->attr.c.default_proj = max_proj;
1417 res = new_Proj (arg, mode_X, max_proj);
1422 new_Conv (ir_node *op, ir_mode *mode)
1424 return new_r_Conv (current_ir_graph, current_ir_graph->current_block,
1429 new_Tuple (int arity, ir_node **in)
1431 return new_r_Tuple (current_ir_graph, current_ir_graph->current_block,
1436 new_Add (ir_node *op1, ir_node *op2, ir_mode *mode)
1438 return new_r_Add (current_ir_graph, current_ir_graph->current_block,
1443 new_Sub (ir_node *op1, ir_node *op2, ir_mode *mode)
1445 return new_r_Sub (current_ir_graph, current_ir_graph->current_block,
1451 new_Minus (ir_node *op, ir_mode *mode)
1453 return new_r_Minus (current_ir_graph, current_ir_graph->current_block,
1458 new_Mul (ir_node *op1, ir_node *op2, ir_mode *mode)
1460 return new_r_Mul (current_ir_graph, current_ir_graph->current_block,
1465 new_Quot (ir_node *memop, ir_node *op1, ir_node *op2)
1468 res = new_r_Quot (current_ir_graph, current_ir_graph->current_block,
1470 #if PRECISE_EXC_CONTEXT
1471 res->attr.frag_arr = new_frag_arr(res);
1478 new_DivMod (ir_node *memop, ir_node *op1, ir_node *op2)
1481 res = new_r_DivMod (current_ir_graph, current_ir_graph->current_block,
1483 #if PRECISE_EXC_CONTEXT
1484 res->attr.frag_arr = new_frag_arr(res);
1491 new_Div (ir_node *memop, ir_node *op1, ir_node *op2)
1494 res = new_r_Div (current_ir_graph, current_ir_graph->current_block,
1496 #if PRECISE_EXC_CONTEXT
1497 res->attr.frag_arr = new_frag_arr(res);
1504 new_Mod (ir_node *memop, ir_node *op1, ir_node *op2)
1507 res = new_r_Mod (current_ir_graph, current_ir_graph->current_block,
1509 #if PRECISE_EXC_CONTEXT
1510 res->attr.frag_arr = new_frag_arr(res);
1517 new_And (ir_node *op1, ir_node *op2, ir_mode *mode)
1519 return new_r_And (current_ir_graph, current_ir_graph->current_block,
1524 new_Or (ir_node *op1, ir_node *op2, ir_mode *mode)
1526 return new_r_Or (current_ir_graph, current_ir_graph->current_block,
1531 new_Eor (ir_node *op1, ir_node *op2, ir_mode *mode)
1533 return new_r_Eor (current_ir_graph, current_ir_graph->current_block,
1538 new_Not (ir_node *op, ir_mode *mode)
1540 return new_r_Not (current_ir_graph, current_ir_graph->current_block,
1545 new_Shl (ir_node *op, ir_node *k, ir_mode *mode)
1547 return new_r_Shl (current_ir_graph, current_ir_graph->current_block,
1552 new_Shr (ir_node *op, ir_node *k, ir_mode *mode)
1554 return new_r_Shr (current_ir_graph, current_ir_graph->current_block,
1559 new_Shrs (ir_node *op, ir_node *k, ir_mode *mode)
1561 return new_r_Shrs (current_ir_graph, current_ir_graph->current_block,
1566 new_Rotate (ir_node *op, ir_node *k, ir_mode *mode)
1568 return new_r_Rot (current_ir_graph, current_ir_graph->current_block,
1573 new_Abs (ir_node *op, ir_mode *mode)
1575 return new_r_Abs (current_ir_graph, current_ir_graph->current_block,
1580 new_Cmp (ir_node *op1, ir_node *op2)
1582 return new_r_Cmp (current_ir_graph, current_ir_graph->current_block,
1589 return new_r_Jmp (current_ir_graph, current_ir_graph->current_block);
1593 new_Cond (ir_node *c)
1595 return new_r_Cond (current_ir_graph, current_ir_graph->current_block, c);
1599 new_Call (ir_node *store, ir_node *callee, int arity, ir_node **in,
1603 res = new_r_Call (current_ir_graph, current_ir_graph->current_block,
1604 store, callee, arity, in, type);
1605 #if PRECISE_EXC_CONTEXT
1606 res->attr.call.frag_arr = new_frag_arr(res);
1613 new_Return (ir_node* store, int arity, ir_node **in)
1615 return new_r_Return (current_ir_graph, current_ir_graph->current_block,
1620 new_Raise (ir_node *store, ir_node *obj)
1622 return new_r_Raise (current_ir_graph, current_ir_graph->current_block,
1627 new_Load (ir_node *store, ir_node *addr)
1630 res = new_r_Load (current_ir_graph, current_ir_graph->current_block,
1632 #if PRECISE_EXC_CONTEXT
1633 res->attr.frag_arr = new_frag_arr(res);
1640 new_Store (ir_node *store, ir_node *addr, ir_node *val)
1643 res = new_r_Store (current_ir_graph, current_ir_graph->current_block,
1645 #if PRECISE_EXC_CONTEXT
1646 res->attr.frag_arr = new_frag_arr(res);
1653 new_Alloc (ir_node *store, ir_node *size, type *alloc_type,
1657 res = new_r_Alloc (current_ir_graph, current_ir_graph->current_block,
1658 store, size, alloc_type, where);
1659 #if PRECISE_EXC_CONTEXT
1660 res->attr.a.frag_arr = new_frag_arr(res);
1667 new_Free (ir_node *store, ir_node *ptr, ir_node *size, type *free_type)
1669 return new_r_Free (current_ir_graph, current_ir_graph->current_block,
1670 store, ptr, size, free_type);
1674 new_simpleSel (ir_node *store, ir_node *objptr, entity *ent)
1675 /* GL: objptr was called frame before. Frame was a bad choice for the name
1676 as the operand could as well be a pointer to a dynamic object. */
1678 return new_r_Sel (current_ir_graph, current_ir_graph->current_block,
1679 store, objptr, 0, NULL, ent);
1683 new_Sel (ir_node *store, ir_node *objptr, int n_index, ir_node **index, entity *sel)
1685 return new_r_Sel (current_ir_graph, current_ir_graph->current_block,
1686 store, objptr, n_index, index, sel);
1690 new_SymConst (type_or_id_p value, symconst_kind kind)
1692 return new_r_SymConst (current_ir_graph, current_ir_graph->current_block,
1697 new_Sync (int arity, ir_node** in)
1699 return new_r_Sync (current_ir_graph, current_ir_graph->current_block,
1707 return current_ir_graph->bad;
1710 /* ********************************************************************* */
1711 /* Comfortable interface with automatic Phi node construction. */
1712 /* (Uses also constructors of ?? interface, except new_Block. */
1713 /* ********************************************************************* */
1715 /** Block construction **/
1716 /* immature Block without predecessors */
1717 ir_node *new_immBlock (void) {
1720 /* creates a new dynamic in-array as length of in is -1 */
1721 res = new_ir_node (current_ir_graph, NULL, op_Block, mode_R, -1, NULL);
1722 current_ir_graph->current_block = res;
1723 res->attr.block.matured = 0;
1724 set_Block_block_visited(res, 0);
1726 /* Create and initialize array for Phi-node construction. */
1727 res->attr.block.graph_arr = NEW_ARR_D (ir_node *, current_ir_graph->obst,
1728 current_ir_graph->n_loc);
1729 memset(res->attr.block.graph_arr, 0, sizeof(ir_node *)*current_ir_graph->n_loc);
1731 /* Immature block may not be optimized! */
1737 /* add an adge to a jmp/control flow node */
1739 add_in_edge (ir_node *block, ir_node *jmp)
1741 if (block->attr.block.matured) {
1742 assert(0 && "Error: Block already matured!\n");
1745 assert (jmp != NULL);
1746 ARR_APP1 (ir_node *, block->in, jmp);
1750 /* changing the current block */
1752 switch_block (ir_node *target)
1754 current_ir_graph->current_block = target;
1757 /* ************************ */
1758 /* parameter administration */
1760 /* get a value from the parameter array from the current block by its index */
1762 get_value (int pos, ir_mode *mode)
1764 inc_irg_visited(current_ir_graph);
1765 return get_r_value_internal (current_ir_graph->current_block, pos + 1, mode);
1769 /* set a value at position pos in the parameter array from the current block */
1771 set_value (int pos, ir_node *value)
1773 current_ir_graph->current_block->attr.block.graph_arr[pos + 1] = value;
1776 /* get the current store */
1780 /* GL: one could call get_value instead */
1781 inc_irg_visited(current_ir_graph);
1782 return get_r_value_internal (current_ir_graph->current_block, 0, mode_M);
1785 /* set the current store */
1787 set_store (ir_node *store)
1789 /* GL: one could call set_value instead */
1790 current_ir_graph->current_block->attr.block.graph_arr[0] = store;
1794 keep_alive (ir_node *ka)
1796 add_End_keepalive(current_ir_graph->end, ka);
1799 /** Useful access routines **/
1800 /* Returns the current block of the current graph. To set the current
1801 block use switch_block(). */
1802 ir_node *get_cur_block() {
1803 return get_irg_current_block(current_ir_graph);
1806 /* Returns the frame type of the current graph */
1807 type *get_cur_frame_type() {
1808 return get_irg_frame_type(current_ir_graph);
1812 /* ********************************************************************* */
1815 /* call once for each run of the library */