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
16 # include "irgraph_t.h"
17 # include "irnode_t.h"
18 # include "irmode_t.h"
26 /* memset belongs to string.h */
29 #if USE_EXPICIT_PHI_IN_STACK
30 /* A stack needed for the automatic Phi node construction in constructor
31 Phi_in. Redefinition in irgraph.c!! */
36 typedef struct Phi_in_stack Phi_in_stack;
39 /*********************************************** */
40 /** privat interfaces, for professional use only */
42 /* Constructs a Block with a fixed number of predecessors.
43 Does not set current_block. Can not be used with automatic
44 Phi node construction. */
46 new_r_Block (ir_graph *irg, int arity, ir_node **in)
50 res = new_ir_node (irg, NULL, op_Block, mode_R, arity, in);
51 set_Block_matured(res, 1);
52 set_Block_block_visited(res, 0);
59 new_r_Start (ir_graph *irg, ir_node *block)
63 res = new_ir_node (irg, block, op_Start, mode_T, 0, NULL);
70 new_r_End (ir_graph *irg, ir_node *block)
74 res = new_ir_node (irg, block, op_End, mode_X, -1, NULL);
80 /* Creates a Phi node with all predecessors. Calling this constructor
81 is only allowed if the corresponding block is mature. */
83 new_r_Phi (ir_graph *irg, ir_node *block, int arity, ir_node **in, ir_mode *mode)
87 assert( get_Block_matured(block) );
88 assert( get_irn_arity(block) == arity );
90 res = new_ir_node (irg, block, op_Phi, mode, arity, in);
98 new_r_Const (ir_graph *irg, ir_node *block, ir_mode *mode, tarval *con)
101 res = new_ir_node (irg, block, op_Const, mode, 0, NULL);
103 res = optimize (res);
107 res = local_optimize_newby (res);
114 new_r_Id (ir_graph *irg, ir_node *block, ir_node *val, ir_mode *mode)
116 ir_node *in[1] = {val};
118 res = new_ir_node (irg, block, op_Id, mode, 1, in);
119 res = optimize (res);
125 new_r_Proj (ir_graph *irg, ir_node *block, ir_node *arg, ir_mode *mode,
128 ir_node *in[1] = {arg};
130 res = new_ir_node (irg, block, op_Proj, mode, 1, in);
131 res->attr.proj = proj;
134 assert(get_Proj_pred(res));
135 assert(get_nodes_Block(get_Proj_pred(res)));
137 res = optimize (res);
145 new_r_Conv (ir_graph *irg, ir_node *block, ir_node *op, ir_mode *mode)
147 ir_node *in[1] = {op};
149 res = new_ir_node (irg, block, op_Conv, mode, 1, in);
150 res = optimize (res);
157 new_r_Tuple (ir_graph *irg, ir_node *block, int arity, ir_node **in)
161 res = new_ir_node (irg, block, op_Tuple, mode_T, arity, in);
162 res = optimize (res);
168 new_r_Add (ir_graph *irg, ir_node *block,
169 ir_node *op1, ir_node *op2, ir_mode *mode)
171 ir_node *in[2] = {op1, op2};
173 res = new_ir_node (irg, block, op_Add, mode, 2, in);
174 res = optimize (res);
180 new_r_Sub (ir_graph *irg, ir_node *block,
181 ir_node *op1, ir_node *op2, ir_mode *mode)
183 ir_node *in[2] = {op1, op2};
185 res = new_ir_node (irg, block, op_Sub, mode, 2, in);
186 res = optimize (res);
192 new_r_Minus (ir_graph *irg, ir_node *block,
193 ir_node *op, ir_mode *mode)
195 ir_node *in[1] = {op};
197 res = new_ir_node (irg, block, op_Minus, mode, 1, in);
198 res = optimize (res);
204 new_r_Mul (ir_graph *irg, ir_node *block,
205 ir_node *op1, ir_node *op2, ir_mode *mode)
207 ir_node *in[2] = {op1, op2};
209 res = new_ir_node (irg, block, op_Mul, mode, 2, in);
210 res = optimize (res);
216 new_r_Quot (ir_graph *irg, ir_node *block,
217 ir_node *memop, ir_node *op1, ir_node *op2)
219 ir_node *in[3] = {memop, op1, op2};
221 res = new_ir_node (irg, block, op_Quot, mode_T, 3, in);
222 res = optimize (res);
228 new_r_DivMod (ir_graph *irg, ir_node *block,
229 ir_node *memop, ir_node *op1, ir_node *op2)
231 ir_node *in[3] = {memop, op1, op2};
233 res = new_ir_node (irg, block, op_DivMod, mode_T, 3, in);
234 res = optimize (res);
240 new_r_Div (ir_graph *irg, ir_node *block,
241 ir_node *memop, ir_node *op1, ir_node *op2)
243 ir_node *in[3] = {memop, op1, op2};
245 res = new_ir_node (irg, block, op_Div, mode_T, 3, in);
246 res = optimize (res);
252 new_r_Mod (ir_graph *irg, ir_node *block,
253 ir_node *memop, ir_node *op1, ir_node *op2)
255 ir_node *in[3] = {memop, op1, op2};
257 res = new_ir_node (irg, block, op_Mod, mode_T, 3, in);
258 res = optimize (res);
264 new_r_And (ir_graph *irg, ir_node *block,
265 ir_node *op1, ir_node *op2, ir_mode *mode)
267 ir_node *in[2] = {op1, op2};
269 res = new_ir_node (irg, block, op_And, mode, 2, in);
270 res = optimize (res);
276 new_r_Or (ir_graph *irg, ir_node *block,
277 ir_node *op1, ir_node *op2, ir_mode *mode)
279 ir_node *in[2] = {op1, op2};
281 res = new_ir_node (irg, block, op_Or, mode, 2, in);
282 res = optimize (res);
288 new_r_Eor (ir_graph *irg, ir_node *block,
289 ir_node *op1, ir_node *op2, ir_mode *mode)
291 ir_node *in[2] = {op1, op2};
293 res = new_ir_node (irg, block, op_Eor, mode, 2, in);
294 res = optimize (res);
300 new_r_Not (ir_graph *irg, ir_node *block,
301 ir_node *op, ir_mode *mode)
303 ir_node *in[1] = {op};
305 res = new_ir_node (irg, block, op_Not, mode, 1, in);
306 res = optimize (res);
312 new_r_Shl (ir_graph *irg, ir_node *block,
313 ir_node *op, ir_node *k, ir_mode *mode)
315 ir_node *in[2] = {op, k};
317 res = new_ir_node (irg, block, op_Shl, mode, 2, in);
318 res = optimize (res);
324 new_r_Shr (ir_graph *irg, ir_node *block,
325 ir_node *op, ir_node *k, ir_mode *mode)
327 ir_node *in[2] = {op, k};
329 res = new_ir_node (irg, block, op_Shr, mode, 2, in);
330 res = optimize (res);
336 new_r_Shrs (ir_graph *irg, ir_node *block,
337 ir_node *op, ir_node *k, ir_mode *mode)
339 ir_node *in[2] = {op, k};
341 res = new_ir_node (irg, block, op_Shrs, mode, 2, in);
342 res = optimize (res);
348 new_r_Rot (ir_graph *irg, ir_node *block,
349 ir_node *op, ir_node *k, ir_mode *mode)
351 ir_node *in[2] = {op, k};
353 res = new_ir_node (irg, block, op_Rot, mode, 2, in);
354 res = optimize (res);
360 new_r_Abs (ir_graph *irg, ir_node *block,
361 ir_node *op, ir_mode *mode)
363 ir_node *in[1] = {op};
365 res = new_ir_node (irg, block, op_Abs, mode, 1, in);
366 res = optimize (res);
372 new_r_Cmp (ir_graph *irg, ir_node *block,
373 ir_node *op1, ir_node *op2)
375 ir_node *in[2] = {op1, op2};
377 res = new_ir_node (irg, block, op_Cmp, mode_T, 2, in);
378 res = optimize (res);
384 new_r_Jmp (ir_graph *irg, ir_node *block)
388 res = new_ir_node (irg, block, op_Jmp, mode_X, 0, in);
389 res = optimize (res);
395 new_r_Cond (ir_graph *irg, ir_node *block, ir_node *c)
397 ir_node *in[1] = {c};
399 res = new_ir_node (irg, block, op_Cond, mode_T, 1, in);
400 res = optimize (res);
406 new_r_Call (ir_graph *irg, ir_node *block, ir_node *store,
407 ir_node *callee, int arity, ir_node **in, type_method *type)
414 NEW_ARR_A (ir_node *, r_in, r_arity);
417 memcpy (&r_in[2], in, sizeof (ir_node *) * arity);
419 res = new_ir_node (irg, block, op_Call, mode_T, r_arity, r_in);
421 set_Call_type(res, type);
422 res = optimize (res);
428 new_r_Return (ir_graph *irg, ir_node *block,
429 ir_node *store, int arity, ir_node **in)
436 NEW_ARR_A (ir_node *, r_in, r_arity);
438 memcpy (&r_in[1], in, sizeof (ir_node *) * arity);
439 res = new_ir_node (irg, block, op_Return, mode_X, r_arity, r_in);
440 res = optimize (res);
446 new_r_Raise (ir_graph *irg, ir_node *block, ir_node *store, ir_node *obj)
448 ir_node *in[2] = {store, obj};
450 res = new_ir_node (irg, block, op_Raise, mode_X, 2, in);
452 res = optimize (res);
458 new_r_Load (ir_graph *irg, ir_node *block,
459 ir_node *store, ir_node *adr)
461 ir_node *in[2] = {store, adr};
463 res = new_ir_node (irg, block, op_Load, mode_T, 2, in);
465 res = optimize (res);
471 new_r_Store (ir_graph *irg, ir_node *block,
472 ir_node *store, ir_node *adr, ir_node *val)
474 ir_node *in[3] = {store, adr, val};
476 res = new_ir_node (irg, block, op_Store, mode_T, 3, in);
478 res = optimize (res);
484 new_r_Alloc (ir_graph *irg, ir_node *block, ir_node *store,
485 ir_node *size, type *alloc_type, where_alloc where)
487 ir_node *in[2] = {store, size};
489 res = new_ir_node (irg, block, op_Alloc, mode_T, 2, in);
491 res->attr.a.where = where;
492 res->attr.a.type = alloc_type;
494 res = optimize (res);
500 new_r_Free (ir_graph *irg, ir_node *block, ir_node *store,
501 ir_node *ptr, ir_node *size, type *free_type)
503 ir_node *in[3] = {store, ptr, size};
505 res = new_ir_node (irg, block, op_Free, mode_T, 3, in);
507 res->attr.f = free_type;
509 res = optimize (res);
515 new_r_Sel (ir_graph *irg, ir_node *block, ir_node *store, ir_node *objptr,
516 int arity, ir_node **in, entity *ent)
523 NEW_ARR_A (ir_node *, r_in, r_arity);
526 memcpy (&r_in[2], in, sizeof (ir_node *) * arity);
527 res = new_ir_node (irg, block, op_Sel, mode_p, r_arity, r_in);
529 res->attr.s.ltyp = static_linkage;
530 res->attr.s.ent = ent;
532 res = optimize (res);
538 new_r_SymConst (ir_graph *irg, ir_node *block, type_or_id_p value,
539 symconst_kind symkind)
544 if (symkind == linkage_ptr_info)
548 res = new_ir_node (irg, block, op_SymConst, mode, 0, in);
550 res->attr.i.num = symkind;
551 if (symkind == linkage_ptr_info) {
552 res->attr.i.tori.ptrinfo = (ident *)value;
554 assert ( ( (symkind == type_tag)
555 || (symkind == size))
556 && (is_type(value)));
557 res->attr.i.tori.typ = (type *)value;
559 res = optimize (res);
565 new_r_Sync (ir_graph *irg, ir_node *block, int arity, ir_node **in)
569 res = new_ir_node (irg, block, op_Sync, mode_M, arity, in);
571 res = optimize (res);
579 return current_ir_graph->bad;
582 /***********************/
583 /** public interfaces */
584 /** construction tools */
591 res = new_ir_node (current_ir_graph, current_ir_graph->current_block,
592 op_Start, mode_T, 0, NULL);
594 res = optimize (res);
604 res = new_ir_node (current_ir_graph, current_ir_graph->current_block,
605 op_End, mode_X, -1, NULL);
607 res = optimize (res);
613 /* Constructs a Block with a fixed number of predecessors.
614 Does set current_block. Can be used with automatic Phi
615 node construction. */
617 new_Block (int arity, ir_node **in)
621 res = new_r_Block (current_ir_graph, arity, in);
622 current_ir_graph->current_block = res;
624 /* Create and initialize array for Phi-node construction. */
625 res->attr.block.graph_arr = NEW_ARR_D (ir_node *, current_ir_graph->obst,
626 current_ir_graph->n_loc);
627 memset(res->attr.block.graph_arr, 0, sizeof(ir_node *)*current_ir_graph->n_loc);
629 res = optimize (res);
635 /*************************************************************************/
636 /* Methods necessary for automatic Phi node creation */
638 ir_node *phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
639 ir_node *get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
640 ir_node *new_r_Phi0 (ir_graph *irg, ir_node *block, ir_mode *mode)
641 ir_node *new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode, ir_node **in, int ins)
643 Call Graph: ( A ---> B == A "calls" B)
645 get_value mature_block
653 get_r_value_internal |
657 new_r_Phi0 new_r_Phi_in
659 *****************************************************************************/
661 /* Creates a Phi node with 0 predecessors */
663 new_r_Phi0 (ir_graph *irg, ir_node *block, ir_mode *mode)
666 res = new_ir_node (irg, block, op_Phi, mode, 0, NULL);
671 /* There are two implementations of the Phi node construction. The first
672 is faster, but does not work for blocks with more than 2 predecessors.
673 The second works always but is slower and causes more unnecessary Phi
675 Select the implementations by the following preprocessor flag set in
677 #if USE_FAST_PHI_CONSTRUCTION
679 /* This is a stack used for allocating and deallocating nodes in
680 new_r_Phi_in. The original implementation used the obstack
681 to model this stack, now it is explicit. This reduces side effects.
683 #if USE_EXPICIT_PHI_IN_STACK
688 res = (Phi_in_stack *) malloc ( sizeof (Phi_in_stack));
690 res->stack = NEW_ARR_F (ir_node *, 1);
696 void free_to_Phi_in_stack(ir_node *phi) {
697 assert(get_irn_opcode(phi) == iro_Phi);
699 if (ARR_LEN(current_ir_graph->Phi_in_stack->stack) ==
700 current_ir_graph->Phi_in_stack->pos)
701 ARR_APP1 (ir_node *, current_ir_graph->Phi_in_stack->stack, phi);
703 current_ir_graph->Phi_in_stack->stack[current_ir_graph->Phi_in_stack->pos] = phi;
705 (current_ir_graph->Phi_in_stack->pos)++;
709 alloc_or_pop_from_Phi_in_stack(ir_graph *irg, ir_node *block, ir_mode *mode,
710 int arity, ir_node **in) {
712 ir_node **stack = current_ir_graph->Phi_in_stack->stack;
713 int pos = current_ir_graph->Phi_in_stack->pos;
717 /* We need to allocate a new node */
718 res = new_ir_node (irg, block, op_Phi, mode, arity, in);
720 /* reuse the old node and initialize it again. */
723 assert (res->kind == k_ir_node);
724 assert (res->op == op_Phi);
729 /* ???!!! How to free the old in array?? */
730 res->in = NEW_ARR_D (ir_node *, irg->obst, (arity+1));
732 memcpy (&res->in[1], in, sizeof (ir_node *) * arity);
734 (current_ir_graph->Phi_in_stack->pos)--;
738 #endif /* USE_EXPICIT_PHI_IN_STACK */
740 /* Creates a Phi node with a given, fixed array **in of predecessors.
741 If the Phi node is unnecessary, as the same value reaches the block
742 through all control flow paths, it is eliminated and the value
743 returned directly. This constructor is only intended for use in
744 the automatic Phi node generation triggered by get_value or mature.
745 The implementation is quite tricky and depends on the fact, that
746 the nodes are allocated on a stack:
747 The in array contains predecessors and NULLs. The NULLs appear,
748 if get_r_value_internal, that computed the predecessors, reached
749 the same block on two paths. In this case the same value reaches
750 this block on both paths, there is no definition in between. We need
751 not allocate a Phi where these path's merge, but we have to communicate
752 this fact to the caller. This happens by returning a pointer to the
753 node the caller _will_ allocate. (Yes, we predict the address. We can
754 do so because the nodes are allocated on the obstack.) The caller then
755 finds a pointer to itself and, when this routine is called again,
759 new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode,
760 ir_node **in, int ins)
763 ir_node *res, *known;
765 /* allocate a new node on the obstack.
766 This can return a node to which some of the pointers in the in-array
768 Attention: the constructor copies the in array, i.e., the later changes
769 to the array in this routine do not affect the constructed node! If
770 the in array contains NULLs, there will be missing predecessors in the
772 Is this a possible internal state of the Phi node generation? */
773 #if USE_EXPICIT_PHI_IN_STACK
774 res = known = alloc_or_pop_from_Phi_in_stack(irg, block, mode, ins, in);
776 res = known = new_ir_node (irg, block, op_Phi, mode, ins, in);
778 /* The in-array can contain NULLs. These were returned by
779 get_r_value_internal if it reached the same block/definition on a
781 The NULLs are replaced by the node itself to simplify the test in the
783 for (i=0; i < ins; ++i)
784 if (in[i] == NULL) in[i] = res;
786 /* This loop checks whether the Phi has more than one predecessor.
787 If so, it is a real Phi node and we break the loop. Else the
788 Phi node merges the same definition on several paths and therefore
790 for (i=0; i < ins; ++i)
792 if (in[i]==res || in[i]==known) continue;
800 /* i==ins: there is at most one predecessor, we don't need a phi node. */
802 #if USE_EXPICIT_PHI_IN_STACK
803 free_to_Phi_in_stack(res);
805 obstack_free (current_ir_graph->obst, res);
809 res = optimize (res);
813 /* return the pointer to the Phi node. This node might be deallocated! */
818 get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
820 /** This function computes the predecessors for a real Phi node, and then
821 allocates and returns this node. The routine called to allocate the
822 node might optimize it away and return a real value, or even a pointer
823 to a deallocated Phi node on top of the obstack!
824 This function is called with an in-array of proper size. **/
825 static inline ir_node *
826 phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
828 ir_node *prevBlock, *res;
831 /* This loop goes to all predecessor blocks of the block the Phi node is in
832 and there finds the operands of the Phi node by calling
833 get_r_value_internal. */
834 for (i = 1; i <= ins; ++i) {
835 assert (block->in[i]);
836 prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */
838 nin[i-1] = get_r_value_internal (prevBlock, pos, mode);
841 /* After collecting all predecessors into the array nin a new Phi node
842 with these predecessors is created. This constructor contains an
843 optimization: If all predecessors of the Phi node are identical it
844 returns the only operand instead of a new Phi node. If the value
845 passes two different control flow edges without being defined, and
846 this is the second path treated, a pointer to the node that will be
847 allocated for the first path (recursion) is returned. We already
848 know the address of this node, as it is the next node to be allocated
849 and will be placed on top of the obstack. (The obstack is a _stack_!) */
850 res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins);
852 /* Now we now the value for "pos" and can enter it in the array with
853 all known local variables. Attention: this might be a pointer to
854 a node, that later will be allocated!!! See new_r_Phi_in.
855 If this is called in mature, after some set_value in the same block,
856 the proper value must not be overwritten:
858 get_value (makes Phi0, put's it into graph_arr)
859 set_value (overwrites Phi0 in graph_arr)
860 mature_block (upgrades Phi0, puts it again into graph_arr, overwriting
863 if (!block->attr.block.graph_arr[pos]) {
864 block->attr.block.graph_arr[pos] = res;
866 /* printf(" value already computed by %s\n",
867 id_to_str(block->attr.block.graph_arr[pos]->op->name)); */
873 /* This function returns the last definition of a variable. In case
874 this variable was last defined in a previous block, Phi nodes are
875 inserted. If the part of the firm graph containing the definition
876 is not yet constructed, a dummy Phi node is returned. */
878 get_r_value_internal (ir_node *block, int pos, ir_mode *mode)
881 /* There are 4 cases to treat.
883 1. The block is not mature and we visit it the first time. We can not
884 create a proper Phi node, therefore a Phi0, i.e., a Phi without
885 predecessors is returned. This node is added to the linked list (field
886 "link") of the containing block to be completed when this block is
887 matured. (Comlpletion will add a new Phi and turn the Phi0 into an Id
890 2. The value is already known in this block, graph_arr[pos] is set and we
891 visit the block the first time. We can return the value without
892 creating any new nodes.
894 3. The block is mature and we visit it the first time. A Phi node needs
895 to be created (phi_merge). If the Phi is not needed, as all it's
896 operands are the same value reaching the block through different
897 paths, it's optimized away and the value itself is returned.
899 4. The block is mature, and we visit it the second time. Now two
900 subcases are possible:
901 * The value was computed completely the last time we were here. This
902 is the case if there is no loop. We can return the proper value.
903 * The recursion that visited this node and set the flag did not
904 return yet. We are computing a value in a loop and need to
905 break the recursion without knowing the result yet.
906 @@@ strange case. Straight forward we would create a Phi before
907 starting the computation of it's predecessors. In this case we will find
908 a Phi here in any case. The problem is that this implementation only
909 creates a Phi after computing the predecessors, so that it is hard to
910 compute self references of this Phi. @@@
911 There is no simple check for the second subcase. Therefore we check
912 for a second visit and treat all such cases as the second subcase.
913 Anyways, the basic situation is the same: we reached a block
914 on two paths without finding a definition of the value: No Phi
915 nodes are needed on both paths.
916 We return this information "Two paths, no Phi needed" by a very tricky
917 implementation that relies on the fact that an obstack is a stack and
918 will return a node with the same address on different allocations.
919 Look also at phi_merge and new_r_phi_in to understand this.
920 @@@ Unfortunately this does not work, see testprogram three_cfpred_example.
924 /* case 4 -- already visited. */
925 if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) return NULL;
927 /* visited the first time */
928 set_irn_visited(block, get_irg_visited(current_ir_graph));
930 /* Get the local valid value */
931 res = block->attr.block.graph_arr[pos];
933 /* case 2 -- If the value is actually computed, return it. */
934 if (res) { return res;};
936 if (block->attr.block.matured) { /* case 3 */
938 /* The Phi has the same amount of ins as the corresponding block. */
939 int ins = get_irn_arity(block);
941 NEW_ARR_A (ir_node *, nin, ins);
943 /* Phi merge collects the predecessors and then creates a node. */
944 res = phi_merge (block, pos, mode, nin, ins);
946 } else { /* case 1 */
947 /* The block is not mature, we don't know how many in's are needed. A Phi
948 with zero predecessors is created. Such a Phi node is called Phi0
949 node. (There is also an obsolete Phi0 opcode.) The Phi0 is then added
950 to the list of Phi0 nodes in this block to be matured by mature_block
952 The Phi0 has to remember the pos of it's internal value. If the real
953 Phi is computed, pos is used to update the array with the local
956 res = new_r_Phi0 (current_ir_graph, block, mode);
957 res->attr.phi0_pos = pos;
958 res->link = block->link;
962 /* If we get here, the frontend missed a use-before-definition error */
965 printf("Error: no value set. Use of undefined variable. Initializing
967 assert (mode->code >= irm_f && mode->code <= irm_p);
968 res = new_r_Const (current_ir_graph, block, mode,
969 tarval_mode_null[mode->code]);
972 /* The local valid value is available now. */
973 block->attr.block.graph_arr[pos] = res;
980 /** This is the simple algorithm. If first generates a Phi0, then
981 it starts the recursion. This causes an Id at the entry of
982 every block that has no definition of the value! **/
984 #if USE_EXPICIT_PHI_IN_STACK
986 Phi_in_stack * new_Phi_in_stack() { return NULL; }
990 new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode,
991 ir_node **in, int ins)
994 ir_node *res, *known;
996 /* Allocate a new node on the obstack. The allocation copies the in
998 res = new_ir_node (irg, block, op_Phi, mode, ins, in);
1000 /* This loop checks whether the Phi has more than one predecessor.
1001 If so, it is a real Phi node and we break the loop. Else the
1002 Phi node merges the same definition on several paths and therefore
1003 is not needed. Don't consider Bad nodes! */
1005 for (i=0; i < ins; ++i)
1007 if (in[i]==res || in[i]==known || is_Bad(in[i])) continue;
1015 /* i==ins: there is at most one predecessor, we don't need a phi node. */
1018 obstack_free (current_ir_graph->obst, res);
1021 /* A undefined value, e.g., in unreachable code. */
1025 res = optimize (res);
1033 get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
1035 /** This function allocates a dummy Phi node to break recursions,
1036 computes the predecessors for the real phi node, and then
1037 allocates and returns this node. The routine called to allocate the
1038 node might optimize it away and return a real value.
1039 This function is called with an in-array of proper size. **/
1040 static inline ir_node *
1041 phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
1043 ir_node *prevBlock, *res, *phi0;
1047 /* If this block has no value at pos create a Phi0 and remember it
1048 in graph_arr to break recursions. */
1050 if (!block->attr.block.graph_arr[pos]) {
1051 /* Even if all variables are defined before use, it can happen that
1052 we get to the start block, if a cond has been replaced by a tuple
1053 (bad, jmp). As the start has a self referencing control flow edge,
1054 we get a self referencing Id, which is hard to optimize away. We avoid
1055 this by defining the value as a Bad node. *
1056 if (block == get_irg_start_block(current_ir_graph)) {
1057 block->attr.block.graph_arr[pos] = new_Bad();
1060 phi0 = new_r_Phi0(current_ir_graph, block, mode);
1061 block->attr.block.graph_arr[pos] = phi0;
1065 /* This loop goes to all predecessor blocks of the block the Phi node
1066 is in and there finds the operands of the Phi node by calling
1067 get_r_value_internal. */
1068 for (i = 1; i <= ins; ++i) {
1069 assert (block->in[i]);
1070 if (is_Bad(block->in[i])) {
1071 /* In case a Cond has been optimized we would get right to the start block
1072 with an invalid definition. */
1073 nin[i-1] = new_Bad();
1076 prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */
1078 if (!is_Bad(prevBlock)) {
1079 nin[i-1] = get_r_value_internal (prevBlock, pos, mode);
1081 nin[i-1] = new_Bad();
1085 /* After collecting all predecessors into the array nin a new Phi node
1086 with these predecessors is created. This constructor contains an
1087 optimization: If all predecessors of the Phi node are identical it
1088 returns the only operand instead of a new Phi node. */
1089 res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins);
1091 /* In case we allocated a Phi0 node at the beginning of this procedure,
1092 we need to exchange this Phi0 with the real Phi. */
1094 exchange(phi0, res);
1095 block->attr.block.graph_arr[pos] = res;
1101 /* This function returns the last definition of a variable. In case
1102 this variable was last defined in a previous block, Phi nodes are
1103 inserted. If the part of the firm graph containing the definition
1104 is not yet constructed, a dummy Phi node is returned. */
1106 get_r_value_internal (ir_node *block, int pos, ir_mode *mode)
1109 /* There are 4 cases to treat.
1111 1. The block is not mature and we visit it the first time. We can not
1112 create a proper Phi node, therefore a Phi0, i.e., a Phi without
1113 predecessors is returned. This node is added to the linked list (field
1114 "link") of the containing block to be completed when this block is
1115 matured. (Comlpletion will add a new Phi and turn the Phi0 into an Id
1118 2. The value is already known in this block, graph_arr[pos] is set and we
1119 visit the block the first time. We can return the value without
1120 creating any new nodes.
1122 3. The block is mature and we visit it the first time. A Phi node needs
1123 to be created (phi_merge). If the Phi is not needed, as all it's
1124 operands are the same value reaching the block through different
1125 paths, it's optimized away and the value itself is returned.
1127 4. The block is mature, and we visit it the second time. Now two
1128 subcases are possible:
1129 * The value was computed completely the last time we were here. This
1130 is the case if there is no loop. We can return the proper value.
1131 * The recursion that visited this node and set the flag did not
1132 return yet. We are computing a value in a loop and need to
1133 break the recursion. This case only happens if we visited
1134 the same block with phi_merge before, which inserted a Phi0.
1135 So we return the Phi0.
1138 /* case 4 -- already visited. */
1139 if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) {
1140 /* As phi_merge allocates a Phi0 this value is always defined. Here
1141 is the critical difference of the two algorithms. */
1142 assert(block->attr.block.graph_arr[pos]);
1143 return block->attr.block.graph_arr[pos];
1146 /* visited the first time */
1147 set_irn_visited(block, get_irg_visited(current_ir_graph));
1149 /* Get the local valid value */
1150 res = block->attr.block.graph_arr[pos];
1152 /* case 2 -- If the value is actually computed, return it. */
1153 if (res) { return res; };
1155 if (block->attr.block.matured) { /* case 3 */
1157 /* The Phi has the same amount of ins as the corresponding block. */
1158 int ins = get_irn_arity(block);
1160 NEW_ARR_A (ir_node *, nin, ins);
1162 /* Phi merge collects the predecessors and then creates a node. */
1163 res = phi_merge (block, pos, mode, nin, ins);
1165 } else { /* case 1 */
1166 /* The block is not mature, we don't know how many in's are needed. A Phi
1167 with zero predecessors is created. Such a Phi node is called Phi0
1168 node. The Phi0 is then added to the list of Phi0 nodes in this block
1169 to be matured by mature_block later.
1170 The Phi0 has to remember the pos of it's internal value. If the real
1171 Phi is computed, pos is used to update the array with the local
1173 res = new_r_Phi0 (current_ir_graph, block, mode);
1174 res->attr.phi0_pos = pos;
1175 res->link = block->link;
1179 /* If we get here, the frontend missed a use-before-definition error */
1182 printf("Error: no value set. Use of undefined variable. Initializing
1184 assert (mode->code >= irm_f && mode->code <= irm_p);
1185 res = new_r_Const (current_ir_graph, block, mode,
1186 tarval_mode_null[mode->code]);
1189 /* The local valid value is available now. */
1190 block->attr.block.graph_arr[pos] = res;
1195 #endif /* USE_FAST_PHI_CONSTRUCTION */
1197 /****************************************************************************/
1199 /** Finalize a Block node, when all control flows are known. */
1200 /** Acceptable parameters are only Block nodes. */
1202 mature_block (ir_node *block)
1209 assert (get_irn_opcode(block) == iro_Block);
1211 if (!get_Block_matured(block)) {
1213 /* turn the dynamic in-array into a static one. */
1214 ins = ARR_LEN (block->in)-1;
1215 NEW_ARR_A (ir_node *, nin, ins);
1217 /* Traverse a chain of Phi nodes attached to this block and mature
1219 for (n = block->link; n; n=next) {
1220 inc_irg_visited(current_ir_graph);
1222 exchange (n, phi_merge (block, n->attr.phi0_pos, n->mode, nin, ins));
1225 block->attr.block.matured = 1;
1227 /* Now, as the block is a finished firm node, we can optimize it.
1228 Since other nodes have been allocated since the block was created
1229 we can not free the node on the obstack. Therefore we have to call
1231 Unfortunately the optimization does not change a lot, as all allocated
1232 nodes refer to the unoptimized node. */
1233 block = optimize_in_place(block);
1239 new_Phi (int arity, ir_node **in, ir_mode *mode)
1241 return new_r_Phi (current_ir_graph, current_ir_graph->current_block,
1246 new_Const (ir_mode *mode, tarval *con)
1248 return new_r_Const (current_ir_graph, current_ir_graph->start_block,
1253 new_Id (ir_node *val, ir_mode *mode)
1255 return new_r_Id (current_ir_graph, current_ir_graph->current_block,
1260 new_Proj (ir_node *arg, ir_mode *mode, long proj)
1262 return new_r_Proj (current_ir_graph, current_ir_graph->current_block,
1267 new_Conv (ir_node *op, ir_mode *mode)
1269 return new_r_Conv (current_ir_graph, current_ir_graph->current_block,
1274 new_Tuple (int arity, ir_node **in)
1276 return new_r_Tuple (current_ir_graph, current_ir_graph->current_block,
1281 new_Add (ir_node *op1, ir_node *op2, ir_mode *mode)
1283 return new_r_Add (current_ir_graph, current_ir_graph->current_block,
1288 new_Sub (ir_node *op1, ir_node *op2, ir_mode *mode)
1290 return new_r_Sub (current_ir_graph, current_ir_graph->current_block,
1296 new_Minus (ir_node *op, ir_mode *mode)
1298 return new_r_Minus (current_ir_graph, current_ir_graph->current_block,
1303 new_Mul (ir_node *op1, ir_node *op2, ir_mode *mode)
1305 return new_r_Mul (current_ir_graph, current_ir_graph->current_block,
1310 new_Quot (ir_node *memop, ir_node *op1, ir_node *op2)
1312 return new_r_Quot (current_ir_graph, current_ir_graph->current_block,
1317 new_DivMod (ir_node *memop, ir_node *op1, ir_node *op2)
1319 return new_r_DivMod (current_ir_graph, current_ir_graph->current_block,
1324 new_Div (ir_node *memop, ir_node *op1, ir_node *op2)
1326 return new_r_Div (current_ir_graph, current_ir_graph->current_block,
1331 new_Mod (ir_node *memop, ir_node *op1, ir_node *op2)
1333 return new_r_Mod (current_ir_graph, current_ir_graph->current_block,
1338 new_And (ir_node *op1, ir_node *op2, ir_mode *mode)
1340 return new_r_And (current_ir_graph, current_ir_graph->current_block,
1345 new_Or (ir_node *op1, ir_node *op2, ir_mode *mode)
1347 return new_r_Or (current_ir_graph, current_ir_graph->current_block,
1352 new_Eor (ir_node *op1, ir_node *op2, ir_mode *mode)
1354 return new_r_Eor (current_ir_graph, current_ir_graph->current_block,
1359 new_Not (ir_node *op, ir_mode *mode)
1361 return new_r_Not (current_ir_graph, current_ir_graph->current_block,
1366 new_Shl (ir_node *op, ir_node *k, ir_mode *mode)
1368 return new_r_Shl (current_ir_graph, current_ir_graph->current_block,
1373 new_Shr (ir_node *op, ir_node *k, ir_mode *mode)
1375 return new_r_Shr (current_ir_graph, current_ir_graph->current_block,
1380 new_Shrs (ir_node *op, ir_node *k, ir_mode *mode)
1382 return new_r_Shrs (current_ir_graph, current_ir_graph->current_block,
1387 new_Rotate (ir_node *op, ir_node *k, ir_mode *mode)
1389 return new_r_Rot (current_ir_graph, current_ir_graph->current_block,
1394 new_Abs (ir_node *op, ir_mode *mode)
1396 return new_r_Abs (current_ir_graph, current_ir_graph->current_block,
1401 new_Cmp (ir_node *op1, ir_node *op2)
1403 return new_r_Cmp (current_ir_graph, current_ir_graph->current_block,
1410 return new_r_Jmp (current_ir_graph, current_ir_graph->current_block);
1414 new_Cond (ir_node *c)
1416 return new_r_Cond (current_ir_graph, current_ir_graph->current_block, c);
1420 new_Call (ir_node *store, ir_node *callee, int arity, ir_node **in,
1423 return new_r_Call (current_ir_graph, current_ir_graph->current_block,
1424 store, callee, arity, in, type);
1428 new_Return (ir_node* store, int arity, ir_node **in)
1430 return new_r_Return (current_ir_graph, current_ir_graph->current_block,
1435 new_Raise (ir_node *store, ir_node *obj)
1437 return new_r_Raise (current_ir_graph, current_ir_graph->current_block,
1442 new_Load (ir_node *store, ir_node *addr)
1444 return new_r_Load (current_ir_graph, current_ir_graph->current_block,
1449 new_Store (ir_node *store, ir_node *addr, ir_node *val)
1451 return new_r_Store (current_ir_graph, current_ir_graph->current_block,
1456 new_Alloc (ir_node *store, ir_node *size, type *alloc_type,
1459 return new_r_Alloc (current_ir_graph, current_ir_graph->current_block,
1460 store, size, alloc_type, where);
1464 new_Free (ir_node *store, ir_node *ptr, ir_node *size, type *free_type)
1466 return new_r_Free (current_ir_graph, current_ir_graph->current_block,
1467 store, ptr, size, free_type);
1471 new_simpleSel (ir_node *store, ir_node *objptr, entity *ent)
1472 /* GL: objptr was called frame before. Frame was a bad choice for the name
1473 as the operand could as well be a pointer to a dynamic object. */
1475 return new_r_Sel (current_ir_graph, current_ir_graph->current_block,
1476 store, objptr, 0, NULL, ent);
1480 new_Sel (ir_node *store, ir_node *objptr, int n_index, ir_node **index, entity *sel)
1482 return new_r_Sel (current_ir_graph, current_ir_graph->current_block,
1483 store, objptr, n_index, index, sel);
1487 new_SymConst (type_or_id_p value, symconst_kind kind)
1489 return new_r_SymConst (current_ir_graph, current_ir_graph->current_block,
1494 new_Sync (int arity, ir_node** in)
1496 return new_r_Sync (current_ir_graph, current_ir_graph->current_block,
1504 return current_ir_graph->bad;
1507 /*************************************************************************/
1508 /* Comfortable interface with automatic Phi node construction. */
1509 /* (Uses also constructors of ?? interface, except new_Block. */
1510 /*************************************************************************/
1512 /** Block construction **/
1513 /* immature Block without predecessors */
1514 ir_node *new_immBlock (void) {
1517 /* creates a new dynamic in-array as length of in is -1 */
1518 res = new_ir_node (current_ir_graph, NULL, op_Block, mode_R, -1, NULL);
1519 current_ir_graph->current_block = res;
1520 res->attr.block.matured = 0;
1521 set_Block_block_visited(res, 0);
1523 /* Create and initialize array for Phi-node construction. */
1524 res->attr.block.graph_arr = NEW_ARR_D (ir_node *, current_ir_graph->obst,
1525 current_ir_graph->n_loc);
1526 memset(res->attr.block.graph_arr, 0, sizeof(ir_node *)*current_ir_graph->n_loc);
1528 /* Immature block may not be optimized! */
1534 /* add an adge to a jmp/control flow node */
1536 add_in_edge (ir_node *block, ir_node *jmp)
1538 if (block->attr.block.matured) {
1539 printf("Error: Block already matured!\n");
1542 assert (jmp != NULL);
1543 ARR_APP1 (ir_node *, block->in, jmp);
1547 /* changing the current block */
1549 switch_block (ir_node *target)
1551 current_ir_graph->current_block = target;
1554 /****************************/
1555 /* parameter administration */
1557 /* get a value from the parameter array from the current block by its index */
1559 get_value (int pos, ir_mode *mode)
1561 inc_irg_visited(current_ir_graph);
1562 return get_r_value_internal (current_ir_graph->current_block, pos + 1, mode);
1565 /* set a value at position pos in the parameter array from the current block */
1567 set_value (int pos, ir_node *value)
1569 current_ir_graph->current_block->attr.block.graph_arr[pos + 1] = value;
1572 /* get the current store */
1576 /* GL: one could call get_value instead */
1577 inc_irg_visited(current_ir_graph);
1578 return get_r_value_internal (current_ir_graph->current_block, 0, mode_M);
1581 /* set the current store */
1583 set_store (ir_node *store)
1585 /* GL: one could call set_value instead */
1586 current_ir_graph->current_block->attr.block.graph_arr[0] = store;
1589 /*************************************************************************/
1592 /* call once for each run of the library */