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
12 # include "irgraph_t.h"
13 # include "irnode_t.h"
21 /* memset belongs to string.h */
24 #if USE_EXPICIT_PHI_IN_STACK
25 /* A stack needed for the automatic Phi node construction in constructor
26 Phi_in. Redefinition in irgraph.c!! */
31 typedef struct Phi_in_stack Phi_in_stack;
34 /*********************************************** */
35 /** privat interfaces, for professional use only */
37 /* Constructs a Block with a fixed number of predecessors.
38 Does not set current_block. Can not be used with automatic
39 Phi node construction. */
41 new_r_Block (ir_graph *irg, int arity, ir_node **in)
45 res = new_ir_node (irg, NULL, op_Block, mode_R, arity, in);
46 set_Block_matured(res, 1);
47 set_Block_block_visited(res, 0);
54 new_r_Start (ir_graph *irg, ir_node *block)
58 res = new_ir_node (irg, block, op_Start, mode_T, 0, NULL);
65 new_r_End (ir_graph *irg, ir_node *block)
69 res = new_ir_node (irg, block, op_End, mode_X, -1, NULL);
75 /* Creates a Phi node with all predecessors. Calling this constructor
76 is only allowed if the corresponding block is mature. */
78 new_r_Phi (ir_graph *irg, ir_node *block, int arity, ir_node **in, ir_mode *mode)
82 assert( get_Block_matured(block) );
83 assert( get_irn_arity(block) == arity );
85 res = new_ir_node (irg, block, op_Phi, mode, arity, in);
93 new_r_Const (ir_graph *irg, ir_node *block, ir_mode *mode, tarval *con)
96 res = new_ir_node (irg, block, op_Const, mode, 0, NULL);
102 res = local_optimize_newby (res);
109 new_r_Id (ir_graph *irg, ir_node *block, ir_node *val, ir_mode *mode)
111 ir_node *in[1] = {val};
113 res = new_ir_node (irg, block, op_Id, mode, 1, in);
114 res = optimize (res);
120 new_r_Proj (ir_graph *irg, ir_node *block, ir_node *arg, ir_mode *mode,
123 ir_node *in[1] = {arg};
125 res = new_ir_node (irg, block, op_Proj, mode, 1, in);
126 res->attr.proj = proj;
129 assert(get_Proj_pred(res));
130 assert(get_nodes_Block(get_Proj_pred(res)));
132 res = optimize (res);
140 new_r_Conv (ir_graph *irg, ir_node *block, ir_node *op, ir_mode *mode)
142 ir_node *in[1] = {op};
144 res = new_ir_node (irg, block, op_Conv, mode, 1, in);
145 res = optimize (res);
152 new_r_Tuple (ir_graph *irg, ir_node *block, int arity, ir_node **in)
156 res = new_ir_node (irg, block, op_Tuple, mode_T, arity, in);
157 res = optimize (res);
163 new_r_Add (ir_graph *irg, ir_node *block,
164 ir_node *op1, ir_node *op2, ir_mode *mode)
166 ir_node *in[2] = {op1, op2};
168 res = new_ir_node (irg, block, op_Add, mode, 2, in);
169 res = optimize (res);
175 new_r_Sub (ir_graph *irg, ir_node *block,
176 ir_node *op1, ir_node *op2, ir_mode *mode)
178 ir_node *in[2] = {op1, op2};
180 res = new_ir_node (irg, block, op_Sub, mode, 2, in);
181 res = optimize (res);
187 new_r_Minus (ir_graph *irg, ir_node *block,
188 ir_node *op, ir_mode *mode)
190 ir_node *in[1] = {op};
192 res = new_ir_node (irg, block, op_Minus, mode, 1, in);
193 res = optimize (res);
199 new_r_Mul (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_Mul, mode, 2, in);
205 res = optimize (res);
211 new_r_Quot (ir_graph *irg, ir_node *block,
212 ir_node *memop, ir_node *op1, ir_node *op2)
214 ir_node *in[3] = {memop, op1, op2};
216 res = new_ir_node (irg, block, op_Quot, mode_T, 3, in);
217 res = optimize (res);
223 new_r_DivMod (ir_graph *irg, ir_node *block,
224 ir_node *memop, ir_node *op1, ir_node *op2)
226 ir_node *in[3] = {memop, op1, op2};
228 res = new_ir_node (irg, block, op_DivMod, mode_T, 3, in);
229 res = optimize (res);
235 new_r_Div (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_Div, mode_T, 3, in);
241 res = optimize (res);
247 new_r_Mod (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_Mod, mode_T, 3, in);
253 res = optimize (res);
259 new_r_And (ir_graph *irg, ir_node *block,
260 ir_node *op1, ir_node *op2, ir_mode *mode)
262 ir_node *in[2] = {op1, op2};
264 res = new_ir_node (irg, block, op_And, mode, 2, in);
265 res = optimize (res);
271 new_r_Or (ir_graph *irg, ir_node *block,
272 ir_node *op1, ir_node *op2, ir_mode *mode)
274 ir_node *in[2] = {op1, op2};
276 res = new_ir_node (irg, block, op_Or, mode, 2, in);
277 res = optimize (res);
283 new_r_Eor (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_Eor, mode, 2, in);
289 res = optimize (res);
295 new_r_Not (ir_graph *irg, ir_node *block,
296 ir_node *op, ir_mode *mode)
298 ir_node *in[1] = {op};
300 res = new_ir_node (irg, block, op_Not, mode, 1, in);
301 res = optimize (res);
307 new_r_Shl (ir_graph *irg, ir_node *block,
308 ir_node *op, ir_node *k, ir_mode *mode)
310 ir_node *in[2] = {op, k};
312 res = new_ir_node (irg, block, op_Shl, mode, 2, in);
313 res = optimize (res);
319 new_r_Shr (ir_graph *irg, ir_node *block,
320 ir_node *op, ir_node *k, ir_mode *mode)
322 ir_node *in[2] = {op, k};
324 res = new_ir_node (irg, block, op_Shr, mode, 2, in);
325 res = optimize (res);
331 new_r_Shrs (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_Shrs, mode, 2, in);
337 res = optimize (res);
343 new_r_Rot (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_Rot, mode, 2, in);
349 res = optimize (res);
355 new_r_Abs (ir_graph *irg, ir_node *block,
356 ir_node *op, ir_mode *mode)
358 ir_node *in[1] = {op};
360 res = new_ir_node (irg, block, op_Abs, mode, 1, in);
361 res = optimize (res);
367 new_r_Cmp (ir_graph *irg, ir_node *block,
368 ir_node *op1, ir_node *op2)
370 ir_node *in[2] = {op1, op2};
372 res = new_ir_node (irg, block, op_Cmp, mode_T, 2, in);
373 res = optimize (res);
379 new_r_Jmp (ir_graph *irg, ir_node *block)
383 res = new_ir_node (irg, block, op_Jmp, mode_X, 0, in);
384 res = optimize (res);
390 new_r_Cond (ir_graph *irg, ir_node *block, ir_node *c)
392 ir_node *in[1] = {c};
394 res = new_ir_node (irg, block, op_Cond, mode_T, 1, in);
395 res = optimize (res);
401 new_r_Call (ir_graph *irg, ir_node *block, ir_node *store,
402 ir_node *callee, int arity, ir_node **in, type_method *type)
409 NEW_ARR_A (ir_node *, r_in, r_arity);
412 memcpy (&r_in[2], in, sizeof (ir_node *) * arity);
414 res = new_ir_node (irg, block, op_Call, mode_T, r_arity, r_in);
416 set_Call_type(res, type);
417 res = optimize (res);
423 new_r_Return (ir_graph *irg, ir_node *block,
424 ir_node *store, int arity, ir_node **in)
431 NEW_ARR_A (ir_node *, r_in, r_arity);
433 memcpy (&r_in[1], in, sizeof (ir_node *) * arity);
434 res = new_ir_node (irg, block, op_Return, mode_X, r_arity, r_in);
435 res = optimize (res);
441 new_r_Raise (ir_graph *irg, ir_node *block, ir_node *store, ir_node *obj)
443 ir_node *in[2] = {store, obj};
445 res = new_ir_node (irg, block, op_Raise, mode_X, 2, in);
447 res = optimize (res);
453 new_r_Load (ir_graph *irg, ir_node *block,
454 ir_node *store, ir_node *adr)
456 ir_node *in[2] = {store, adr};
458 res = new_ir_node (irg, block, op_Load, mode_T, 2, in);
460 res = optimize (res);
466 new_r_Store (ir_graph *irg, ir_node *block,
467 ir_node *store, ir_node *adr, ir_node *val)
469 ir_node *in[3] = {store, adr, val};
471 res = new_ir_node (irg, block, op_Store, mode_T, 3, in);
473 res = optimize (res);
479 new_r_Alloc (ir_graph *irg, ir_node *block, ir_node *store,
480 ir_node *size, type *alloc_type, where_alloc where)
482 ir_node *in[2] = {store, size};
484 res = new_ir_node (irg, block, op_Alloc, mode_T, 2, in);
486 res->attr.a.where = where;
487 res->attr.a.type = alloc_type;
489 res = optimize (res);
495 new_r_Free (ir_graph *irg, ir_node *block, ir_node *store,
496 ir_node *ptr, ir_node *size, type *free_type)
498 ir_node *in[3] = {store, ptr, size};
500 res = new_ir_node (irg, block, op_Free, mode_T, 3, in);
502 res->attr.f = free_type;
504 res = optimize (res);
510 new_r_Sel (ir_graph *irg, ir_node *block, ir_node *store, ir_node *objptr,
511 int arity, ir_node **in, entity *ent)
518 NEW_ARR_A (ir_node *, r_in, r_arity);
521 memcpy (&r_in[2], in, sizeof (ir_node *) * arity);
522 res = new_ir_node (irg, block, op_Sel, mode_p, r_arity, r_in);
524 res->attr.s.ltyp = static_linkage;
525 res->attr.s.ent = ent;
527 res = optimize (res);
533 new_r_SymConst (ir_graph *irg, ir_node *block, type_or_id_p value,
534 symconst_kind symkind)
539 if (symkind == linkage_ptr_info)
543 res = new_ir_node (irg, block, op_SymConst, mode, 0, in);
545 res->attr.i.num = symkind;
546 if (symkind == linkage_ptr_info) {
547 res->attr.i.tori.ptrinfo = (ident *)value;
549 assert ( ( (symkind == type_tag)
550 || (symkind == size))
551 && (is_type(value)));
552 res->attr.i.tori.typ = (type *)value;
554 res = optimize (res);
560 new_r_Sync (ir_graph *irg, ir_node *block, int arity, ir_node **in)
564 res = new_ir_node (irg, block, op_Sync, mode_M, arity, in);
566 res = optimize (res);
574 return current_ir_graph->bad;
577 /***********************/
578 /** public interfaces */
579 /** construction tools */
586 res = new_ir_node (current_ir_graph, current_ir_graph->current_block,
587 op_Start, mode_T, 0, NULL);
589 res = optimize (res);
599 res = new_ir_node (current_ir_graph, current_ir_graph->current_block,
600 op_End, mode_X, -1, NULL);
602 res = optimize (res);
609 /* Constructs a Block with a fixed number of predecessors.
610 Does set current_block. Can be used with automatic Phi
611 node construction. */
613 new_Block (int arity, ir_node **in)
617 res = new_r_Block (current_ir_graph, arity, in);
618 current_ir_graph->current_block = res;
620 /* Create and initialize array for Phi-node construction. */
621 res->attr.block.graph_arr = NEW_ARR_D (ir_node *, current_ir_graph->obst,
622 current_ir_graph->params);
623 memset(res->attr.block.graph_arr, 0, sizeof(ir_node *)*current_ir_graph->params);
625 res = optimize (res);
634 return new_immBlock();
638 /*************************************************************************/
639 /* Methods necessary for automatic Phi node creation */
641 ir_node *phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
642 ir_node *get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
643 ir_node *new_r_Phi0 (ir_graph *irg, ir_node *block, ir_mode *mode)
644 ir_node *new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode, ir_node **in, int ins)
646 Call Graph: ( A ---> B == A "calls" B)
648 get_value mature_block
656 get_r_value_internal |
660 new_r_Phi0 new_r_Phi_in
662 *****************************************************************************/
664 /* Creates a Phi node with 0 predecessors */
666 new_r_Phi0 (ir_graph *irg, ir_node *block, ir_mode *mode)
669 res = new_ir_node (irg, block, op_Phi, mode, 0, NULL);
674 /* There are two implementations of the Phi node construction. The first
675 is faster, but does not work for blocks with more than 2 predecessors.
676 The second works always but is slower and causes more unnecessary Phi
678 Select the implementations by the following preprocessor flag set in
680 #if USE_FAST_PHI_CONSTRUCTION
682 /* This is a stack used for allocating and deallocating nodes in
683 new_r_Phi_in. The original implementation used the obstack
684 to model this stack, now it is explicit. This reduces side effects.
686 #if USE_EXPICIT_PHI_IN_STACK
691 res = (Phi_in_stack *) malloc ( sizeof (Phi_in_stack));
693 res->stack = NEW_ARR_F (ir_node *, 1);
699 void free_to_Phi_in_stack(ir_node *phi) {
700 assert(get_irn_opcode(phi) == iro_Phi);
702 if (ARR_LEN(current_ir_graph->Phi_in_stack->stack) ==
703 current_ir_graph->Phi_in_stack->pos)
704 ARR_APP1 (ir_node *, current_ir_graph->Phi_in_stack->stack, phi);
706 current_ir_graph->Phi_in_stack->stack[current_ir_graph->Phi_in_stack->pos] = phi;
708 (current_ir_graph->Phi_in_stack->pos)++;
712 alloc_or_pop_from_Phi_in_stack(ir_graph *irg, ir_node *block, ir_mode *mode,
713 int arity, ir_node **in) {
715 ir_node **stack = current_ir_graph->Phi_in_stack->stack;
716 int pos = current_ir_graph->Phi_in_stack->pos;
720 /* We need to allocate a new node */
721 res = new_ir_node (irg, block, op_Phi, mode, arity, in);
723 /* reuse the old node and initialize it again. */
726 assert (res->kind == k_ir_node);
727 assert (res->op == op_Phi);
732 /* ???!!! How to free the old in array?? */
733 res->in = NEW_ARR_D (ir_node *, irg->obst, (arity+1));
735 memcpy (&res->in[1], in, sizeof (ir_node *) * arity);
737 (current_ir_graph->Phi_in_stack->pos)--;
741 #endif /* USE_EXPICIT_PHI_IN_STACK */
743 /* Creates a Phi node with a given, fixed array **in of predecessors.
744 If the Phi node is unnecessary, as the same value reaches the block
745 through all control flow paths, it is eliminated and the value
746 returned directly. This constructor is only intended for use in
747 the automatic Phi node generation triggered by get_value or mature.
748 The implementation is quite tricky and depends on the fact, that
749 the nodes are allocated on a stack:
750 The in array contains predecessors and NULLs. The NULLs appear,
751 if get_r_value_internal, that computed the predecessors, reached
752 the same block on two paths. In this case the same value reaches
753 this block on both paths, there is no definition in between. We need
754 not allocate a Phi where these path's merge, but we have to communicate
755 this fact to the caller. This happens by returning a pointer to the
756 node the caller _will_ allocate. (Yes, we predict the address. We can
757 do so because the nodes are allocated on the obstack.) The caller then
758 finds a pointer to itself and, when this routine is called again,
762 new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode,
763 ir_node **in, int ins)
766 ir_node *res, *known;
768 /* allocate a new node on the obstack.
769 This can return a node to which some of the pointers in the in-array
771 Attention: the constructor copies the in array, i.e., the later changes
772 to the array in this routine do not affect the constructed node! If
773 the in array contains NULLs, there will be missing predecessors in the
775 Is this a possible internal state of the Phi node generation? */
776 #if USE_EXPICIT_PHI_IN_STACK
777 res = known = alloc_or_pop_from_Phi_in_stack(irg, block, mode, ins, in);
779 res = known = new_ir_node (irg, block, op_Phi, mode, ins, in);
781 /* The in-array can contain NULLs. These were returned by
782 get_r_value_internal if it reached the same block/definition on a
784 The NULLs are replaced by the node itself to simplify the test in the
786 for (i=0; i < ins; ++i)
787 if (in[i] == NULL) in[i] = res;
789 /* This loop checks whether the Phi has more than one predecessor.
790 If so, it is a real Phi node and we break the loop. Else the
791 Phi node merges the same definition on several paths and therefore
793 for (i=0; i < ins; ++i)
795 if (in[i]==res || in[i]==known) continue;
803 /* i==ins: there is at most one predecessor, we don't need a phi node. */
805 #if USE_EXPICIT_PHI_IN_STACK
806 free_to_Phi_in_stack(res);
808 obstack_free (current_ir_graph->obst, res);
812 res = optimize (res);
816 /* return the pointer to the Phi node. This node might be deallocated! */
821 get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
823 /** This function computes the predecessors for a real Phi node, and then
824 allocates and returns this node. The routine called to allocate the
825 node might optimize it away and return a real value, or even a pointer
826 to a deallocated Phi node on top of the obstack!
827 This function is called with an in-array of proper size. **/
828 static inline ir_node *
829 phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
831 ir_node *prevBlock, *res;
834 /* This loop goes to all predecessor blocks of the block the Phi node is in
835 and there finds the operands of the Phi node by calling
836 get_r_value_internal. */
837 for (i = 1; i <= ins; ++i) {
838 assert (block->in[i]);
839 prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */
841 nin[i-1] = get_r_value_internal (prevBlock, pos, mode);
844 /* After collecting all predecessors into the array nin a new Phi node
845 with these predecessors is created. This constructor contains an
846 optimization: If all predecessors of the Phi node are identical it
847 returns the only operand instead of a new Phi node. If the value
848 passes two different control flow edges without being defined, and
849 this is the second path treated, a pointer to the node that will be
850 allocated for the first path (recursion) is returned. We already
851 know the address of this node, as it is the next node to be allocated
852 and will be placed on top of the obstack. (The obstack is a _stack_!) */
853 res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins);
855 /* Now we now the value for "pos" and can enter it in the array with
856 all known local variables. Attention: this might be a pointer to
857 a node, that later will be allocated!!! See new_r_Phi_in.
858 If this is called in mature, after some set_value in the same block,
859 the proper value must not be overwritten:
861 get_value (makes Phi0, put's it into graph_arr)
862 set_value (overwrites Phi0 in graph_arr)
863 mature_block (upgrades Phi0, puts it again into graph_arr, overwriting
866 if (!block->attr.block.graph_arr[pos]) {
867 block->attr.block.graph_arr[pos] = res;
869 /* printf(" value already computed by %s\n",
870 id_to_str(block->attr.block.graph_arr[pos]->op->name)); */
876 /* This function returns the last definition of a variable. In case
877 this variable was last defined in a previous block, Phi nodes are
878 inserted. If the part of the firm graph containing the definition
879 is not yet constructed, a dummy Phi node is returned. */
881 get_r_value_internal (ir_node *block, int pos, ir_mode *mode)
884 /* There are 4 cases to treat.
886 1. The block is not mature and we visit it the first time. We can not
887 create a proper Phi node, therefore a Phi0, i.e., a Phi without
888 predecessors is returned. This node is added to the linked list (field
889 "link") of the containing block to be completed when this block is
890 matured. (Comlpletion will add a new Phi and turn the Phi0 into an Id
893 2. The value is already known in this block, graph_arr[pos] is set and we
894 visit the block the first time. We can return the value without
895 creating any new nodes.
897 3. The block is mature and we visit it the first time. A Phi node needs
898 to be created (phi_merge). If the Phi is not needed, as all it's
899 operands are the same value reaching the block through different
900 paths, it's optimized away and the value itself is returned.
902 4. The block is mature, and we visit it the second time. Now two
903 subcases are possible:
904 * The value was computed completely the last time we were here. This
905 is the case if there is no loop. We can return the proper value.
906 * The recursion that visited this node and set the flag did not
907 return yet. We are computing a value in a loop and need to
908 break the recursion without knowing the result yet.
909 @@@ strange case. Straight forward we would create a Phi before
910 starting the computation of it's predecessors. In this case we will find
911 a Phi here in any case. The problem is that this implementation only
912 creates a Phi after computing the predecessors, so that it is hard to
913 compute self references of this Phi. @@@
914 There is no simple check for the second subcase. Therefore we check
915 for a second visit and treat all such cases as the second subcase.
916 Anyways, the basic situation is the same: we reached a block
917 on two paths without finding a definition of the value: No Phi
918 nodes are needed on both paths.
919 We return this information "Two paths, no Phi needed" by a very tricky
920 implementation that relies on the fact that an obstack is a stack and
921 will return a node with the same address on different allocations.
922 Look also at phi_merge and new_r_phi_in to understand this.
923 @@@ Unfortunately this does not work, see testprogram three_cfpred_example.
927 /* case 4 -- already visited. */
928 if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) return NULL;
930 /* visited the first time */
931 set_irn_visited(block, get_irg_visited(current_ir_graph));
933 /* Get the local valid value */
934 res = block->attr.block.graph_arr[pos];
936 /* case 2 -- If the value is actually computed, return it. */
937 if (res) { return res;};
939 if (block->attr.block.matured) { /* case 3 */
941 /* The Phi has the same amount of ins as the corresponding block. */
942 int ins = get_irn_arity(block);
944 NEW_ARR_A (ir_node *, nin, ins);
946 /* Phi merge collects the predecessors and then creates a node. */
947 res = phi_merge (block, pos, mode, nin, ins);
949 } else { /* case 1 */
950 /* The block is not mature, we don't know how many in's are needed. A Phi
951 with zero predecessors is created. Such a Phi node is called Phi0
952 node. (There is also an obsolete Phi0 opcode.) The Phi0 is then added
953 to the list of Phi0 nodes in this block to be matured by mature_block
955 The Phi0 has to remember the pos of it's internal value. If the real
956 Phi is computed, pos is used to update the array with the local
959 res = new_r_Phi0 (current_ir_graph, block, mode);
960 res->attr.phi0_pos = pos;
961 res->link = block->link;
965 /* If we get here, the frontend missed a use-before-definition error */
968 printf("Error: no value set. Use of undefined variable. Initializing
970 assert (mode->code >= irm_f && mode->code <= irm_p);
971 res = new_r_Const (current_ir_graph, block, mode,
972 tarval_mode_null[mode->code]);
975 /* The local valid value is available now. */
976 block->attr.block.graph_arr[pos] = res;
983 /** This is the simple algorithm. If first generates a Phi0, then
984 it starts the recursion. This causes an Id at the entry of
985 every block that has no definition of the value! **/
987 #if USE_EXPICIT_PHI_IN_STACK
989 Phi_in_stack * new_Phi_in_stack() { return NULL; }
993 new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode,
994 ir_node **in, int ins)
997 ir_node *res, *known;
999 /* Allocate a new node on the obstack. The allocation copies the in
1001 res = new_ir_node (irg, block, op_Phi, mode, ins, in);
1003 /* This loop checks whether the Phi has more than one predecessor.
1004 If so, it is a real Phi node and we break the loop. Else the
1005 Phi node merges the same definition on several paths and therefore
1006 is not needed. Don't consider Bad nodes! */
1008 for (i=0; i < ins; ++i)
1010 if (in[i]==res || in[i]==known || is_Bad(in[i])) continue;
1018 /* i==ins: there is at most one predecessor, we don't need a phi node. */
1021 obstack_free (current_ir_graph->obst, res);
1024 /* A undefined value, e.g., in unreachable code. */
1028 res = optimize (res);
1036 get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
1038 /** This function allocates a dummy Phi node to break recursions,
1039 computes the predecessors for the real phi node, and then
1040 allocates and returns this node. The routine called to allocate the
1041 node might optimize it away and return a real value.
1042 This function is called with an in-array of proper size. **/
1043 static inline ir_node *
1044 phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
1046 ir_node *prevBlock, *res, *phi0;
1050 /* If this block has no value at pos create a Phi0 and remember it
1051 in graph_arr to break recursions. */
1053 if (!block->attr.block.graph_arr[pos]) {
1054 /* Even if all variables are defined before use, it can happen that
1055 we get to the start block, if a cond has been replaced by a tuple
1056 (bad, jmp). As the start has a self referencing control flow edge,
1057 we get a self referencing Id, which is hard to optimize away. We avoid
1058 this by defining the value as a Bad node. *
1059 if (block == get_irg_start_block(current_ir_graph)) {
1060 block->attr.block.graph_arr[pos] = new_Bad();
1063 phi0 = new_r_Phi0(current_ir_graph, block, mode);
1064 block->attr.block.graph_arr[pos] = phi0;
1068 /* This loop goes to all predecessor blocks of the block the Phi node
1069 is in and there finds the operands of the Phi node by calling
1070 get_r_value_internal. */
1071 for (i = 1; i <= ins; ++i) {
1072 assert (block->in[i]);
1073 if (is_Bad(block->in[i])) {
1074 /* In case a Cond has been optimized we would get right to the start block
1075 with an invalid definition. */
1076 nin[i-1] = new_Bad();
1079 prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */
1081 if (!is_Bad(prevBlock)) {
1082 nin[i-1] = get_r_value_internal (prevBlock, pos, mode);
1084 nin[i-1] = new_Bad();
1088 /* After collecting all predecessors into the array nin a new Phi node
1089 with these predecessors is created. This constructor contains an
1090 optimization: If all predecessors of the Phi node are identical it
1091 returns the only operand instead of a new Phi node. */
1092 res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins);
1094 /* In case we allocated a Phi0 node at the beginning of this procedure,
1095 we need to exchange this Phi0 with the real Phi. */
1097 exchange(phi0, res);
1098 block->attr.block.graph_arr[pos] = res;
1104 /* This function returns the last definition of a variable. In case
1105 this variable was last defined in a previous block, Phi nodes are
1106 inserted. If the part of the firm graph containing the definition
1107 is not yet constructed, a dummy Phi node is returned. */
1109 get_r_value_internal (ir_node *block, int pos, ir_mode *mode)
1112 /* There are 4 cases to treat.
1114 1. The block is not mature and we visit it the first time. We can not
1115 create a proper Phi node, therefore a Phi0, i.e., a Phi without
1116 predecessors is returned. This node is added to the linked list (field
1117 "link") of the containing block to be completed when this block is
1118 matured. (Comlpletion will add a new Phi and turn the Phi0 into an Id
1121 2. The value is already known in this block, graph_arr[pos] is set and we
1122 visit the block the first time. We can return the value without
1123 creating any new nodes.
1125 3. The block is mature and we visit it the first time. A Phi node needs
1126 to be created (phi_merge). If the Phi is not needed, as all it's
1127 operands are the same value reaching the block through different
1128 paths, it's optimized away and the value itself is returned.
1130 4. The block is mature, and we visit it the second time. Now two
1131 subcases are possible:
1132 * The value was computed completely the last time we were here. This
1133 is the case if there is no loop. We can return the proper value.
1134 * The recursion that visited this node and set the flag did not
1135 return yet. We are computing a value in a loop and need to
1136 break the recursion. This case only happens if we visited
1137 the same block with phi_merge before, which inserted a Phi0.
1138 So we return the Phi0.
1141 /* case 4 -- already visited. */
1142 if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) {
1143 /* As phi_merge allocates a Phi0 this value is always defined. Here
1144 is the critical difference of the two algorithms. */
1145 assert(block->attr.block.graph_arr[pos]);
1146 return block->attr.block.graph_arr[pos];
1149 /* visited the first time */
1150 set_irn_visited(block, get_irg_visited(current_ir_graph));
1152 /* Get the local valid value */
1153 res = block->attr.block.graph_arr[pos];
1155 /* case 2 -- If the value is actually computed, return it. */
1156 if (res) { return res; };
1158 if (block->attr.block.matured) { /* case 3 */
1160 /* The Phi has the same amount of ins as the corresponding block. */
1161 int ins = get_irn_arity(block);
1163 NEW_ARR_A (ir_node *, nin, ins);
1165 /* Phi merge collects the predecessors and then creates a node. */
1166 res = phi_merge (block, pos, mode, nin, ins);
1168 } else { /* case 1 */
1169 /* The block is not mature, we don't know how many in's are needed. A Phi
1170 with zero predecessors is created. Such a Phi node is called Phi0
1171 node. The Phi0 is then added to the list of Phi0 nodes in this block
1172 to be matured by mature_block later.
1173 The Phi0 has to remember the pos of it's internal value. If the real
1174 Phi is computed, pos is used to update the array with the local
1176 res = new_r_Phi0 (current_ir_graph, block, mode);
1177 res->attr.phi0_pos = pos;
1178 res->link = block->link;
1182 /* If we get here, the frontend missed a use-before-definition error */
1185 printf("Error: no value set. Use of undefined variable. Initializing
1187 assert (mode->code >= irm_f && mode->code <= irm_p);
1188 res = new_r_Const (current_ir_graph, block, mode,
1189 tarval_mode_null[mode->code]);
1192 /* The local valid value is available now. */
1193 block->attr.block.graph_arr[pos] = res;
1198 #endif /* USE_FAST_PHI_CONSTRUCTION */
1200 /****************************************************************************/
1202 /** Finalize a Block node, when all control flows are known. */
1203 /** Acceptable parameters are only Block nodes. */
1205 mature_block (ir_node *block)
1212 assert (get_irn_opcode(block) == iro_Block);
1214 if (!get_Block_matured(block)) {
1216 /* turn the dynamic in-array into a static one. */
1217 ins = ARR_LEN (block->in)-1;
1218 NEW_ARR_A (ir_node *, nin, ins);
1220 /* Traverse a chain of Phi nodes attached to this block and mature
1222 for (n = block->link; n; n=next) {
1223 inc_irg_visited(current_ir_graph);
1225 exchange (n, phi_merge (block, n->attr.phi0_pos, n->mode, nin, ins));
1228 block->attr.block.matured = 1;
1230 /* Now, as the block is a finished firm node, we can optimize it.
1231 Since other nodes have been allocated since the block was created
1232 we can not free the node on the obstack. Therefore we have to call
1234 Unfortunately the optimization does not change a lot, as all allocated
1235 nodes refer to the unoptimized node. */
1236 block = optimize_in_place(block);
1242 new_Phi (int arity, ir_node **in, ir_mode *mode)
1244 return new_r_Phi (current_ir_graph, current_ir_graph->current_block,
1249 new_Const (ir_mode *mode, tarval *con)
1251 return new_r_Const (current_ir_graph, current_ir_graph->start_block,
1256 new_Id (ir_node *val, ir_mode *mode)
1258 return new_r_Id (current_ir_graph, current_ir_graph->current_block,
1263 new_Proj (ir_node *arg, ir_mode *mode, long proj)
1265 return new_r_Proj (current_ir_graph, current_ir_graph->current_block,
1270 new_Conv (ir_node *op, ir_mode *mode)
1272 return new_r_Conv (current_ir_graph, current_ir_graph->current_block,
1277 new_Tuple (int arity, ir_node **in)
1279 return new_r_Tuple (current_ir_graph, current_ir_graph->current_block,
1284 new_Add (ir_node *op1, ir_node *op2, ir_mode *mode)
1286 return new_r_Add (current_ir_graph, current_ir_graph->current_block,
1291 new_Sub (ir_node *op1, ir_node *op2, ir_mode *mode)
1293 return new_r_Sub (current_ir_graph, current_ir_graph->current_block,
1299 new_Minus (ir_node *op, ir_mode *mode)
1301 return new_r_Minus (current_ir_graph, current_ir_graph->current_block,
1306 new_Mul (ir_node *op1, ir_node *op2, ir_mode *mode)
1308 return new_r_Mul (current_ir_graph, current_ir_graph->current_block,
1313 new_Quot (ir_node *memop, ir_node *op1, ir_node *op2)
1315 return new_r_Quot (current_ir_graph, current_ir_graph->current_block,
1320 new_DivMod (ir_node *memop, ir_node *op1, ir_node *op2)
1322 return new_r_DivMod (current_ir_graph, current_ir_graph->current_block,
1327 new_Div (ir_node *memop, ir_node *op1, ir_node *op2)
1329 return new_r_Div (current_ir_graph, current_ir_graph->current_block,
1334 new_Mod (ir_node *memop, ir_node *op1, ir_node *op2)
1336 return new_r_Mod (current_ir_graph, current_ir_graph->current_block,
1341 new_And (ir_node *op1, ir_node *op2, ir_mode *mode)
1343 return new_r_And (current_ir_graph, current_ir_graph->current_block,
1348 new_Or (ir_node *op1, ir_node *op2, ir_mode *mode)
1350 return new_r_Or (current_ir_graph, current_ir_graph->current_block,
1355 new_Eor (ir_node *op1, ir_node *op2, ir_mode *mode)
1357 return new_r_Eor (current_ir_graph, current_ir_graph->current_block,
1362 new_Not (ir_node *op, ir_mode *mode)
1364 return new_r_Not (current_ir_graph, current_ir_graph->current_block,
1369 new_Shl (ir_node *op, ir_node *k, ir_mode *mode)
1371 return new_r_Shl (current_ir_graph, current_ir_graph->current_block,
1376 new_Shr (ir_node *op, ir_node *k, ir_mode *mode)
1378 return new_r_Shr (current_ir_graph, current_ir_graph->current_block,
1383 new_Shrs (ir_node *op, ir_node *k, ir_mode *mode)
1385 return new_r_Shrs (current_ir_graph, current_ir_graph->current_block,
1390 new_Rotate (ir_node *op, ir_node *k, ir_mode *mode)
1392 return new_r_Rot (current_ir_graph, current_ir_graph->current_block,
1397 new_Abs (ir_node *op, ir_mode *mode)
1399 return new_r_Abs (current_ir_graph, current_ir_graph->current_block,
1404 new_Cmp (ir_node *op1, ir_node *op2)
1406 return new_r_Cmp (current_ir_graph, current_ir_graph->current_block,
1413 return new_r_Jmp (current_ir_graph, current_ir_graph->current_block);
1417 new_Cond (ir_node *c)
1419 return new_r_Cond (current_ir_graph, current_ir_graph->current_block, c);
1423 new_Call (ir_node *store, ir_node *callee, int arity, ir_node **in,
1426 return new_r_Call (current_ir_graph, current_ir_graph->current_block,
1427 store, callee, arity, in, type);
1431 new_Return (ir_node* store, int arity, ir_node **in)
1433 return new_r_Return (current_ir_graph, current_ir_graph->current_block,
1438 new_Raise (ir_node *store, ir_node *obj)
1440 return new_r_Raise (current_ir_graph, current_ir_graph->current_block,
1445 new_Load (ir_node *store, ir_node *addr)
1447 return new_r_Load (current_ir_graph, current_ir_graph->current_block,
1452 new_Store (ir_node *store, ir_node *addr, ir_node *val)
1454 return new_r_Store (current_ir_graph, current_ir_graph->current_block,
1459 new_Alloc (ir_node *store, ir_node *size, type *alloc_type,
1462 return new_r_Alloc (current_ir_graph, current_ir_graph->current_block,
1463 store, size, alloc_type, where);
1467 new_Free (ir_node *store, ir_node *ptr, ir_node *size, type *free_type)
1469 return new_r_Free (current_ir_graph, current_ir_graph->current_block,
1470 store, ptr, size, free_type);
1474 new_simpleSel (ir_node *store, ir_node *objptr, entity *ent)
1475 /* GL: objptr was called frame before. Frame was a bad choice for the name
1476 as the operand could as well be a pointer to a dynamic object. */
1478 return new_r_Sel (current_ir_graph, current_ir_graph->current_block,
1479 store, objptr, 0, NULL, ent);
1483 new_Sel (ir_node *store, ir_node *objptr, int n_index, ir_node **index, entity *sel)
1485 return new_r_Sel (current_ir_graph, current_ir_graph->current_block,
1486 store, objptr, n_index, index, sel);
1490 new_SymConst (type_or_id_p value, symconst_kind kind)
1492 return new_r_SymConst (current_ir_graph, current_ir_graph->current_block,
1497 new_Sync (int arity, ir_node** in)
1499 return new_r_Sync (current_ir_graph, current_ir_graph->current_block,
1507 return current_ir_graph->bad;
1510 /*************************************************************************/
1511 /* Comfortable interface with automatic Phi node construction. */
1512 /* (Uses also constructors of ?? interface, except new_Block. */
1513 /*************************************************************************/
1515 /** Block construction **/
1516 /* immature Block without predecessors */
1517 ir_node *new_immBlock (void) {
1520 /* creates a new dynamic in-array as length of in is -1 */
1521 res = new_ir_node (current_ir_graph, NULL, op_Block, mode_R, -1, NULL);
1522 current_ir_graph->current_block = res;
1523 res->attr.block.matured = 0;
1524 set_Block_block_visited(res, 0);
1526 /* Create and initialize array for Phi-node construction. */
1527 res->attr.block.graph_arr = NEW_ARR_D (ir_node *, current_ir_graph->obst,
1528 current_ir_graph->params);
1529 memset(res->attr.block.graph_arr, 0, sizeof(ir_node *)*current_ir_graph->params);
1531 /* Immature block may not be optimized! */
1537 /* add an adge to a jmp/control flow node */
1539 add_in_edge (ir_node *block, ir_node *jmp)
1541 if (block->attr.block.matured) {
1542 printf("Error: Block already matured!\n");
1545 assert (jmp != NULL);
1546 ARR_APP1 (ir_node *, block->in, jmp);
1550 /* changing the current block */
1552 switch_block (ir_node *target)
1554 current_ir_graph->current_block = target;
1557 /****************************/
1558 /* parameter administration */
1560 /* get a value from the parameter array from the current block by its index */
1562 get_value (int pos, ir_mode *mode)
1564 inc_irg_visited(current_ir_graph);
1565 return get_r_value_internal (current_ir_graph->current_block, pos + 1, mode);
1568 /* set a value at position pos in the parameter array from the current block */
1570 set_value (int pos, ir_node *value)
1572 current_ir_graph->current_block->attr.block.graph_arr[pos + 1] = value;
1575 /* get the current store */
1579 /* GL: one could call get_value instead */
1580 inc_irg_visited(current_ir_graph);
1581 return get_r_value_internal (current_ir_graph->current_block, 0, mode_M);
1584 /* set the current store */
1586 set_store (ir_node *store)
1588 /* GL: one could call set_value instead */
1589 current_ir_graph->current_block->attr.block.graph_arr[0] = store;
1592 /*************************************************************************/
1595 /* call once for each run of the library */