1 /* Copyright (C) 1998 - 2000 by Universitaet Karlsruhe
2 ** All rights reserved.
4 ** Authors: Martin Trapp, Christian Schaefer
6 ** ircons.c: basic and more detailed irnode constructors
7 ** store, block and parameter administration.
8 ** Adapted to extended FIRM nodes (exceptions...) and commented
9 ** by Goetz Lindenmaier
19 /* memset belongs to string.h */
23 #if USE_EXPICIT_PHI_IN_STACK
24 /* A stack needed for the automatic Phi node construction in constructor
32 /*********************************************** */
33 /** privat interfaces, for professional use only */
35 /* Constructs a Block with a fixed number of predecessors.
36 Does not set current_block. */
39 new_r_Block (ir_graph *irg, int arity, ir_node **in)
43 res = new_ir_node (current_ir_graph, NULL, op_Block, mode_R, arity, in);
50 new_r_Start (ir_graph *irg, ir_node *block)
54 res = new_ir_node (irg, block, op_Start, mode_T, 0, NULL);
61 new_r_End (ir_graph *irg, ir_node *block)
65 res = new_ir_node (irg, block, op_End, mode_X, -1, NULL);
71 /* Creates a Phi node with all predecessors. Calling this constructor
72 is only allowed if the corresponding block is mature. */
74 new_r_Phi (ir_graph *irg, ir_node *block, int arity, ir_node **in, ir_mode *mode)
78 assert( get_Block_matured(block) );
79 assert( get_irn_arity(block) == arity );
81 res = new_ir_node (irg, block, op_Phi, mode, arity, in);
89 new_r_Const (ir_graph *irg, ir_node *block, ir_mode *mode, tarval *con)
92 res = new_ir_node (irg, block, op_Const, mode, 0, NULL);
98 res = local_optimize_newby (res);
105 new_r_Id (ir_graph *irg, ir_node *block, ir_node *val, ir_mode *mode)
107 ir_node *in[1] = {val};
109 res = new_ir_node (irg, block, op_Id, mode, 1, in);
110 res = optimize (res);
116 new_r_Proj (ir_graph *irg, ir_node *block, ir_node *arg, ir_mode *mode,
119 ir_node *in[1] = {arg};
121 res = new_ir_node (irg, block, op_Proj, mode, 1, in);
122 res->attr.proj = proj;
125 assert(get_Proj_pred(res));
126 assert(get_nodes_Block(get_Proj_pred(res)));
128 res = optimize (res);
136 new_r_Conv (ir_graph *irg, ir_node *block, ir_node *op, ir_mode *mode)
138 ir_node *in[1] = {op};
140 res = new_ir_node (irg, block, op_Conv, mode, 1, in);
141 res = optimize (res);
148 new_r_Tuple (ir_graph *irg, ir_node *block, int arity, ir_node **in)
152 res = new_ir_node (irg, block, op_Tuple, mode_T, arity, in);
153 res = optimize (res);
159 new_r_Add (ir_graph *irg, ir_node *block,
160 ir_node *op1, ir_node *op2, ir_mode *mode)
162 ir_node *in[2] = {op1, op2};
164 res = new_ir_node (irg, block, op_Add, mode, 2, in);
165 res = optimize (res);
171 new_r_Sub (ir_graph *irg, ir_node *block,
172 ir_node *op1, ir_node *op2, ir_mode *mode)
174 ir_node *in[2] = {op1, op2};
176 res = new_ir_node (irg, block, op_Sub, mode, 2, in);
177 res = optimize (res);
183 new_r_Minus (ir_graph *irg, ir_node *block,
184 ir_node *op, ir_mode *mode)
186 ir_node *in[1] = {op};
188 res = new_ir_node (irg, block, op_Minus, mode, 1, in);
189 res = optimize (res);
195 new_r_Mul (ir_graph *irg, ir_node *block,
196 ir_node *op1, ir_node *op2, ir_mode *mode)
198 ir_node *in[2] = {op1, op2};
200 res = new_ir_node (irg, block, op_Mul, mode, 2, in);
201 res = optimize (res);
207 new_r_Quot (ir_graph *irg, ir_node *block,
208 ir_node *memop, ir_node *op1, ir_node *op2)
210 ir_node *in[3] = {memop, op1, op2};
212 res = new_ir_node (irg, block, op_Quot, mode_T, 3, in);
213 res = optimize (res);
219 new_r_DivMod (ir_graph *irg, ir_node *block,
220 ir_node *memop, ir_node *op1, ir_node *op2)
222 ir_node *in[3] = {memop, op1, op2};
224 res = new_ir_node (irg, block, op_DivMod, mode_T, 3, in);
225 res = optimize (res);
231 new_r_Div (ir_graph *irg, ir_node *block,
232 ir_node *memop, ir_node *op1, ir_node *op2)
234 ir_node *in[3] = {memop, op1, op2};
236 res = new_ir_node (irg, block, op_Div, mode_T, 3, in);
237 res = optimize (res);
243 new_r_Mod (ir_graph *irg, ir_node *block,
244 ir_node *memop, ir_node *op1, ir_node *op2)
246 ir_node *in[3] = {memop, op1, op2};
248 res = new_ir_node (irg, block, op_Mod, mode_T, 3, in);
249 res = optimize (res);
255 new_r_And (ir_graph *irg, ir_node *block,
256 ir_node *op1, ir_node *op2, ir_mode *mode)
258 ir_node *in[2] = {op1, op2};
260 res = new_ir_node (irg, block, op_And, mode, 2, in);
261 res = optimize (res);
267 new_r_Or (ir_graph *irg, ir_node *block,
268 ir_node *op1, ir_node *op2, ir_mode *mode)
270 ir_node *in[2] = {op1, op2};
272 res = new_ir_node (irg, block, op_Or, mode, 2, in);
273 res = optimize (res);
279 new_r_Eor (ir_graph *irg, ir_node *block,
280 ir_node *op1, ir_node *op2, ir_mode *mode)
282 ir_node *in[2] = {op1, op2};
284 res = new_ir_node (irg, block, op_Eor, mode, 2, in);
285 res = optimize (res);
291 new_r_Not (ir_graph *irg, ir_node *block,
292 ir_node *op, ir_mode *mode)
294 ir_node *in[1] = {op};
296 res = new_ir_node (irg, block, op_Not, mode, 1, in);
297 res = optimize (res);
303 new_r_Shl (ir_graph *irg, ir_node *block,
304 ir_node *op, ir_node *k, ir_mode *mode)
306 ir_node *in[2] = {op, k};
308 res = new_ir_node (irg, block, op_Shl, mode, 2, in);
309 res = optimize (res);
315 new_r_Shr (ir_graph *irg, ir_node *block,
316 ir_node *op, ir_node *k, ir_mode *mode)
318 ir_node *in[2] = {op, k};
320 res = new_ir_node (irg, block, op_Shr, mode, 2, in);
321 res = optimize (res);
327 new_r_Shrs (ir_graph *irg, ir_node *block,
328 ir_node *op, ir_node *k, ir_mode *mode)
330 ir_node *in[2] = {op, k};
332 res = new_ir_node (irg, block, op_Shrs, mode, 2, in);
333 res = optimize (res);
339 new_r_Rot (ir_graph *irg, ir_node *block,
340 ir_node *op, ir_node *k, ir_mode *mode)
342 ir_node *in[2] = {op, k};
344 res = new_ir_node (irg, block, op_Rot, mode, 2, in);
345 res = optimize (res);
351 new_r_Abs (ir_graph *irg, ir_node *block,
352 ir_node *op, ir_mode *mode)
354 ir_node *in[1] = {op};
356 res = new_ir_node (irg, block, op_Abs, mode, 1, in);
357 res = optimize (res);
363 new_r_Cmp (ir_graph *irg, ir_node *block,
364 ir_node *op1, ir_node *op2)
366 ir_node *in[2] = {op1, op2};
368 res = new_ir_node (irg, block, op_Cmp, mode_T, 2, in);
369 res = optimize (res);
375 new_r_Jmp (ir_graph *irg, ir_node *block)
379 res = new_ir_node (irg, block, op_Jmp, mode_X, 0, in);
380 res = optimize (res);
386 new_r_Cond (ir_graph *irg, ir_node *block, ir_node *c)
388 ir_node *in[1] = {c};
390 res = new_ir_node (irg, block, op_Cond, mode_T, 1, in);
391 res = optimize (res);
397 new_r_Call (ir_graph *irg, ir_node *block, ir_node *store,
398 ir_node *callee, int arity, ir_node **in, type_method *type)
405 NEW_ARR_A (ir_node *, r_in, r_arity);
408 memcpy (&r_in[2], in, sizeof (ir_node *) * arity);
410 res = new_ir_node (irg, block, op_Call, mode_T, r_arity, r_in);
412 set_Call_type(res, type);
413 res = optimize (res);
419 new_r_Return (ir_graph *irg, ir_node *block,
420 ir_node *store, int arity, ir_node **in)
427 NEW_ARR_A (ir_node *, r_in, r_arity);
429 memcpy (&r_in[1], in, sizeof (ir_node *) * arity);
430 res = new_ir_node (irg, block, op_Return, mode_X, r_arity, r_in);
431 res = optimize (res);
437 new_r_Raise (ir_graph *irg, ir_node *block, ir_node *store, ir_node *obj)
439 ir_node *in[2] = {store, obj};
441 res = new_ir_node (irg, block, op_Raise, mode_X, 2, in);
443 res = optimize (res);
449 new_r_Load (ir_graph *irg, ir_node *block,
450 ir_node *store, ir_node *adr)
452 ir_node *in[2] = {store, adr};
454 res = new_ir_node (irg, block, op_Load, mode_T, 2, in);
456 res = optimize (res);
462 new_r_Store (ir_graph *irg, ir_node *block,
463 ir_node *store, ir_node *adr, ir_node *val)
465 ir_node *in[3] = {store, adr, val};
467 res = new_ir_node (irg, block, op_Store, mode_T, 3, in);
469 res = optimize (res);
475 new_r_Alloc (ir_graph *irg, ir_node *block, ir_node *store,
476 ir_node *size, type *alloc_type, where_alloc where)
478 ir_node *in[2] = {store, size};
480 res = new_ir_node (irg, block, op_Alloc, mode_T, 2, in);
482 res->attr.a.where = where;
483 res->attr.a.type = alloc_type;
485 res = optimize (res);
491 new_r_Free (ir_graph *irg, ir_node *block, ir_node *store,
492 ir_node *ptr, ir_node *size, type *free_type)
494 ir_node *in[3] = {store, ptr, size};
496 res = new_ir_node (irg, block, op_Free, mode_T, 3, in);
498 res->attr.f = free_type;
500 res = optimize (res);
506 new_r_Sel (ir_graph *irg, ir_node *block, ir_node *store, ir_node *objptr,
507 int arity, ir_node **in, entity *ent)
514 NEW_ARR_A (ir_node *, r_in, r_arity);
517 memcpy (&r_in[2], in, sizeof (ir_node *) * arity);
518 res = new_ir_node (irg, block, op_Sel, mode_p, r_arity, r_in);
520 res->attr.s.ltyp = static_linkage;
521 res->attr.s.ent = ent;
523 res = optimize (res);
529 new_r_SymConst (ir_graph *irg, ir_node *block, type_or_id *value,
530 symconst_kind symkind)
534 res = new_ir_node (irg, block, op_SymConst, mode_I, 0, in);
536 res->attr.i.num = symkind;
537 if (symkind == linkage_ptr_info) {
538 res->attr.i.tori.ptrinfo = (ident *)value;
540 assert ( ( (symkind == type_tag)
541 || (symkind == size))
542 && (is_type(value)));
543 res->attr.i.tori.typ = (type *)value;
545 res = optimize (res);
551 new_r_Sync (ir_graph *irg, ir_node *block, int arity, ir_node **in)
555 res = new_ir_node (irg, block, op_Sync, mode_M, arity, in);
557 res = optimize (res);
565 return current_ir_graph->bad;
568 /***********************/
569 /** public interfaces */
570 /** construction tools */
577 res = new_ir_node (current_ir_graph, current_ir_graph->current_block,
578 op_Start, mode_T, 0, NULL);
580 res = optimize (res);
590 res = new_ir_node (current_ir_graph, current_ir_graph->current_block,
591 op_End, mode_X, -1, NULL);
593 res = optimize (res);
604 res = new_ir_node (current_ir_graph, NULL, op_Block, mode_R, -1, NULL);
605 current_ir_graph->current_block = res;
606 res->attr.block.matured = 0;
607 set_Block_block_visited(res, 0);
609 /* forget this optimization. use this only if mature !!!!
610 res = optimize (res); */
613 /** create a new dynamic array, which stores all parameters in irnodes */
614 /** using the same obstack as the whole irgraph */
615 res->attr.block.graph_arr = NEW_ARR_D (ir_node *, current_ir_graph->obst,
616 current_ir_graph->params);
618 /** initialize the parameter array */
619 memset(res->attr.block.graph_arr, 0, sizeof(ir_node *)*current_ir_graph->params);
624 /*************************************************************************/
625 /* Methods necessary for automatic Phi node creation */
627 ir_node *phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
628 ir_node *get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
629 ir_node *new_r_Phi0 (ir_graph *irg, ir_node *block, ir_mode *mode)
630 ir_node *new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode, ir_node **in, int ins)
632 Call Graph: ( A ---> B == A "calls" B)
634 get_value mature_block
642 get_r_value_internal |
646 new_r_Phi0 new_r_Phi_in
648 *****************************************************************************/
650 /* Creates a Phi node with 0 predecessors */
652 new_r_Phi0 (ir_graph *irg, ir_node *block, ir_mode *mode)
655 res = new_ir_node (irg, block, op_Phi, mode, 0, NULL);
660 /* There are two implementations of the Phi node construction. The first
661 is faster, but does not work for blocks with more than 2 predecessors.
662 The second works always but is slower and causes more unnecessary Phi
664 Select the implementations by the following preprocessor flag set in
666 #if USE_FAST_PHI_CONSTRUCTION
668 /* This is a stack used for allocating and deallocating nodes in
669 new_r_Phi_in. The original implementation used the obstack
670 to model this stack, now it is explicit. This reduces side effects.
672 #if USE_EXPICIT_PHI_IN_STACK
677 res = (Phi_in_stack *) malloc ( sizeof (Phi_in_stack));
679 res->stack = NEW_ARR_F (ir_node *, 1);
685 void free_to_Phi_in_stack(ir_node *phi) {
686 assert(get_irn_opcode(phi) == iro_Phi);
688 if (ARR_LEN(current_ir_graph->Phi_in_stack->stack) ==
689 current_ir_graph->Phi_in_stack->pos)
690 ARR_APP1 (ir_node *, current_ir_graph->Phi_in_stack->stack, phi);
692 current_ir_graph->Phi_in_stack->stack[current_ir_graph->Phi_in_stack->pos] = phi;
694 (current_ir_graph->Phi_in_stack->pos)++;
698 alloc_or_pop_from_Phi_in_stack(ir_graph *irg, ir_node *block, ir_mode *mode,
699 int arity, ir_node **in) {
701 ir_node **stack = current_ir_graph->Phi_in_stack->stack;
702 int pos = current_ir_graph->Phi_in_stack->pos;
706 /* We need to allocate a new node */
707 res = new_ir_node (irg, block, op_Phi, mode, arity, in);
709 /* reuse the old node and initialize it again. */
712 assert (res->kind == k_ir_node);
713 assert (res->op == op_Phi);
718 /* ???!!! How to free the old in array?? */
719 res->in = NEW_ARR_D (ir_node *, irg->obst, (arity+1));
721 memcpy (&res->in[1], in, sizeof (ir_node *) * arity);
723 (current_ir_graph->Phi_in_stack->pos)--;
727 #endif /* USE_EXPICIT_PHI_IN_STACK */
729 /* Creates a Phi node with a given, fixed array **in of predecessors.
730 If the Phi node is unnecessary, as the same value reaches the block
731 through all control flow paths, it is eliminated and the value
732 returned directly. This constructor is only intended for use in
733 the automatic Phi node generation triggered by get_value or mature.
734 The implementation is quite tricky and depends on the fact, that
735 the nodes are allocated on a stack:
736 The in array contains predecessors and NULLs. The NULLs appear,
737 if get_r_value_internal, that computed the predecessors, reached
738 the same block on two paths. In this case the same value reaches
739 this block on both paths, there is no definition in between. We need
740 not allocate a Phi where these path's merge, but we have to communicate
741 this fact to the caller. This happens by returning a pointer to the
742 node the caller _will_ allocate. (Yes, we predict the address. We can
743 do so because the nodes are allocated on the obstack.) The caller then
744 finds a pointer to itself and, when this routine is called again,
748 new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode,
749 ir_node **in, int ins)
752 ir_node *res, *known;
754 /* allocate a new node on the obstack.
755 This can return a node to which some of the pointers in the in-array
757 Attention: the constructor copies the in array, i.e., the later changes
758 to the array in this routine do not affect the constructed node! If
759 the in array contains NULLs, there will be missing predecessors in the
761 Is this a possible internal state of the Phi node generation? */
762 #if USE_EXPICIT_PHI_IN_STACK
763 res = known = alloc_or_pop_from_Phi_in_stack(irg, block, mode, ins, in);
765 res = known = new_ir_node (irg, block, op_Phi, mode, ins, in);
767 /* The in-array can contain NULLs. These were returned by
768 get_r_value_internal if it reached the same block/definition on a
770 The NULLs are replaced by the node itself to simplify the test in the
772 for (i=0; i < ins; ++i)
773 if (in[i] == NULL) in[i] = res;
775 /* This loop checks whether the Phi has more than one predecessor.
776 If so, it is a real Phi node and we break the loop. Else the
777 Phi node merges the same definition on several paths and therefore
779 for (i=0; i < ins; ++i)
781 if (in[i]==res || in[i]==known) continue;
789 /* i==ins: there is at most one predecessor, we don't need a phi node. */
791 #if USE_EXPICIT_PHI_IN_STACK
792 free_to_Phi_in_stack(res);
794 obstack_free (current_ir_graph->obst, res);
798 res = optimize (res);
802 /* return the pointer to the Phi node. This node might be deallocated! */
807 get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
809 /** This function computes the predecessors for a real Phi node, and then
810 allocates and returns this node. The routine called to allocate the
811 node might optimize it away and return a real value, or even a pointer
812 to a deallocated Phi node on top of the obstack!
813 This function is called with an in-array of proper size. **/
814 static inline ir_node *
815 phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
817 ir_node *prevBlock, *res;
820 /* This loop goes to all predecessor blocks of the block the Phi node is in
821 and there finds the operands of the Phi node by calling
822 get_r_value_internal. */
823 for (i = 1; i <= ins; ++i) {
824 assert (block->in[i]);
825 prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */
827 nin[i-1] = get_r_value_internal (prevBlock, pos, mode);
830 /* After collecting all predecessors into the array nin a new Phi node
831 with these predecessors is created. This constructor contains an
832 optimization: If all predecessors of the Phi node are identical it
833 returns the only operand instead of a new Phi node. If the value
834 passes two different control flow edges without being defined, and
835 this is the second path treated, a pointer to the node that will be
836 allocated for the first path (recursion) is returned. We already
837 know the address of this node, as it is the next node to be allocated
838 and will be placed on top of the obstack. (The obstack is a _stack_!) */
839 res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins);
841 /* Now we now the value for "pos" and can enter it in the array with
842 all known local variables. Attention: this might be a pointer to
843 a node, that later will be allocated!!! See new_r_Phi_in.
844 If this is called in mature, after some set_value in the same block,
845 the proper value must not be overwritten:
847 get_value (makes Phi0, put's it into graph_arr)
848 set_value (overwrites Phi0 in graph_arr)
849 mature_block (upgrades Phi0, puts it again into graph_arr, overwriting
852 if (!block->attr.block.graph_arr[pos]) {
853 block->attr.block.graph_arr[pos] = res;
855 /* printf(" value already computed by %s\n",
856 id_to_str(block->attr.block.graph_arr[pos]->op->name)); */
862 /* This function returns the last definition of a variable. In case
863 this variable was last defined in a previous block, Phi nodes are
864 inserted. If the part of the firm graph containing the definition
865 is not yet constructed, a dummy Phi node is returned. */
867 get_r_value_internal (ir_node *block, int pos, ir_mode *mode)
870 /* There are 4 cases to treat.
872 1. The block is not mature and we visit it the first time. We can not
873 create a proper Phi node, therefore a Phi0, i.e., a Phi without
874 predecessors is returned. This node is added to the linked list (field
875 "link") of the containing block to be completed when this block is
876 matured. (Comlpletion will add a new Phi and turn the Phi0 into an Id
879 2. The value is already known in this block, graph_arr[pos] is set and we
880 visit the block the first time. We can return the value without
881 creating any new nodes.
883 3. The block is mature and we visit it the first time. A Phi node needs
884 to be created (phi_merge). If the Phi is not needed, as all it's
885 operands are the same value reaching the block through different
886 paths, it's optimized away and the value itself is returned.
888 4. The block is mature, and we visit it the second time. Now two
889 subcases are possible:
890 * The value was computed completely the last time we were here. This
891 is the case if there is no loop. We can return the proper value.
892 * The recursion that visited this node and set the flag did not
893 return yet. We are computing a value in a loop and need to
894 break the recursion without knowing the result yet.
895 @@@ strange case. Straight forward we would create a Phi before
896 starting the computation of it's predecessors. In this case we will find
897 a Phi here in any case. The problem is that this implementation only
898 creates a Phi after computing the predecessors, so that it is hard to
899 compute self references of this Phi. @@@
900 There is no simple check for the second subcase. Therefore we check
901 for a second visit and treat all such cases as the second subcase.
902 Anyways, the basic situation is the same: we reached a block
903 on two paths without finding a definition of the value: No Phi
904 nodes are needed on both paths.
905 We return this information "Two paths, no Phi needed" by a very tricky
906 implementation that relies on the fact that an obstack is a stack and
907 will return a node with the same address on different allocations.
908 Look also at phi_merge and new_r_phi_in to understand this.
909 @@@ Unfortunately this does not work, see testprogram three_cfpred_example.
913 /* case 4 -- already visited. */
914 if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) return NULL;
916 /* visited the first time */
917 set_irn_visited(block, get_irg_visited(current_ir_graph));
919 /* Get the local valid value */
920 res = block->attr.block.graph_arr[pos];
922 /* case 2 -- If the value is actually computed, return it. */
923 if (res) { return res;};
925 if (block->attr.block.matured) { /* case 3 */
927 /* The Phi has the same amount of ins as the corresponding block. */
928 int ins = get_irn_arity(block);
930 NEW_ARR_A (ir_node *, nin, ins);
932 /* Phi merge collects the predecessors and then creates a node. */
933 res = phi_merge (block, pos, mode, nin, ins);
935 } else { /* case 1 */
936 /* The block is not mature, we don't know how many in's are needed. A Phi
937 with zero predecessors is created. Such a Phi node is called Phi0
938 node. (There is also an obsolete Phi0 opcode.) The Phi0 is then added
939 to the list of Phi0 nodes in this block to be matured by mature_block
941 The Phi0 has to remember the pos of it's internal value. If the real
942 Phi is computed, pos is used to update the array with the local
945 res = new_r_Phi0 (current_ir_graph, block, mode);
946 res->attr.phi0_pos = pos;
947 res->link = block->link;
951 /* If we get here, the frontend missed a use-before-definition error */
954 printf("Error: no value set. Use of undefined variable. Initializing
956 assert (mode->code >= irm_f && mode->code <= irm_p);
957 res = new_r_Const (current_ir_graph, block, mode,
958 tarval_mode_null[mode->code]);
961 /* The local valid value is available now. */
962 block->attr.block.graph_arr[pos] = res;
969 /** This is the simple algorithm. If first generates a Phi0, then
970 it starts the recursion. This causes an Id at the entry of
971 every block that has no definition of the value! **/
973 #if USE_EXPICIT_PHI_IN_STACK
975 Phi_in_stack * new_Phi_in_stack() { return NULL; }
979 new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode,
980 ir_node **in, int ins)
983 ir_node *res, *known;
985 /* Allocate a new node on the obstack. The allocation copies the in
987 res = new_ir_node (irg, block, op_Phi, mode, ins, in);
989 /* This loop checks whether the Phi has more than one predecessor.
990 If so, it is a real Phi node and we break the loop. Else the
991 Phi node merges the same definition on several paths and therefore
992 is not needed. Don't consider Bad nodes! */
994 for (i=0; i < ins; ++i)
996 if (in[i]==res || in[i]==known || is_Bad(in[i])) continue;
1004 /* i==ins: there is at most one predecessor, we don't need a phi node. */
1007 obstack_free (current_ir_graph->obst, res);
1010 /* A undefined value, e.g., in unreachable code. */
1014 res = optimize (res);
1022 get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
1024 /** This function allocates a dummy Phi node to break recursions,
1025 computes the predecessors for the real phi node, and then
1026 allocates and returns this node. The routine called to allocate the
1027 node might optimize it away and return a real value.
1028 This function is called with an in-array of proper size. **/
1029 static inline ir_node *
1030 phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
1032 ir_node *prevBlock, *res, *phi0;
1036 /* If this block has no value at pos create a Phi0 and remember it
1037 in graph_arr to break recursions. */
1039 if (!block->attr.block.graph_arr[pos]) {
1040 /* Even if all variables are defined before use, it can happen that
1041 we get to the start block, if a cond has been replaced by a tuple
1042 (bad, jmp). As the start has a self referencing control flow edge,
1043 we get a self referencing Id, which is hard to optimize away. We avoid
1044 this by defining the value as a Bad node. *
1045 if (block == get_irg_start_block(current_ir_graph)) {
1046 block->attr.block.graph_arr[pos] = new_Bad();
1049 phi0 = new_r_Phi0(current_ir_graph, block, mode);
1050 block->attr.block.graph_arr[pos] = phi0;
1054 /* This loop goes to all predecessor blocks of the block the Phi node
1055 is in and there finds the operands of the Phi node by calling
1056 get_r_value_internal. */
1057 for (i = 1; i <= ins; ++i) {
1058 assert (block->in[i]);
1059 if (is_Bad(block->in[i])) {
1060 /* In case a Cond has been optimized we would get right to the start block
1061 with an invalid definition. */
1062 nin[i-1] = new_Bad();
1065 prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */
1067 if (!is_Bad(prevBlock)) {
1068 nin[i-1] = get_r_value_internal (prevBlock, pos, mode);
1070 nin[i-1] = new_Bad();
1074 /* After collecting all predecessors into the array nin a new Phi node
1075 with these predecessors is created. This constructor contains an
1076 optimization: If all predecessors of the Phi node are identical it
1077 returns the only operand instead of a new Phi node. */
1078 res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins);
1080 /* In case we allocated a Phi0 node at the beginning of this procedure,
1081 we need to exchange this Phi0 with the real Phi. */
1083 exchange(phi0, res);
1084 block->attr.block.graph_arr[pos] = res;
1090 /* This function returns the last definition of a variable. In case
1091 this variable was last defined in a previous block, Phi nodes are
1092 inserted. If the part of the firm graph containing the definition
1093 is not yet constructed, a dummy Phi node is returned. */
1095 get_r_value_internal (ir_node *block, int pos, ir_mode *mode)
1098 /* There are 4 cases to treat.
1100 1. The block is not mature and we visit it the first time. We can not
1101 create a proper Phi node, therefore a Phi0, i.e., a Phi without
1102 predecessors is returned. This node is added to the linked list (field
1103 "link") of the containing block to be completed when this block is
1104 matured. (Comlpletion will add a new Phi and turn the Phi0 into an Id
1107 2. The value is already known in this block, graph_arr[pos] is set and we
1108 visit the block the first time. We can return the value without
1109 creating any new nodes.
1111 3. The block is mature and we visit it the first time. A Phi node needs
1112 to be created (phi_merge). If the Phi is not needed, as all it's
1113 operands are the same value reaching the block through different
1114 paths, it's optimized away and the value itself is returned.
1116 4. The block is mature, and we visit it the second time. Now two
1117 subcases are possible:
1118 * The value was computed completely the last time we were here. This
1119 is the case if there is no loop. We can return the proper value.
1120 * The recursion that visited this node and set the flag did not
1121 return yet. We are computing a value in a loop and need to
1122 break the recursion. This case only happens if we visited
1123 the same block with phi_merge before, which inserted a Phi0.
1124 So we return the Phi0.
1127 /* case 4 -- already visited. */
1128 if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) {
1129 /* As phi_merge allocates a Phi0 this value is always defined. Here
1130 is the critical difference of the two algorithms. */
1131 assert(block->attr.block.graph_arr[pos]);
1132 return block->attr.block.graph_arr[pos];
1135 /* visited the first time */
1136 set_irn_visited(block, get_irg_visited(current_ir_graph));
1138 /* Get the local valid value */
1139 res = block->attr.block.graph_arr[pos];
1141 /* case 2 -- If the value is actually computed, return it. */
1142 if (res) { return res; };
1144 if (block->attr.block.matured) { /* case 3 */
1146 /* The Phi has the same amount of ins as the corresponding block. */
1147 int ins = get_irn_arity(block);
1149 NEW_ARR_A (ir_node *, nin, ins);
1151 /* Phi merge collects the predecessors and then creates a node. */
1152 res = phi_merge (block, pos, mode, nin, ins);
1154 } else { /* case 1 */
1155 /* The block is not mature, we don't know how many in's are needed. A Phi
1156 with zero predecessors is created. Such a Phi node is called Phi0
1157 node. The Phi0 is then added to the list of Phi0 nodes in this block
1158 to be matured by mature_block later.
1159 The Phi0 has to remember the pos of it's internal value. If the real
1160 Phi is computed, pos is used to update the array with the local
1162 res = new_r_Phi0 (current_ir_graph, block, mode);
1163 res->attr.phi0_pos = pos;
1164 res->link = block->link;
1168 /* If we get here, the frontend missed a use-before-definition error */
1171 printf("Error: no value set. Use of undefined variable. Initializing
1173 assert (mode->code >= irm_f && mode->code <= irm_p);
1174 res = new_r_Const (current_ir_graph, block, mode,
1175 tarval_mode_null[mode->code]);
1178 /* The local valid value is available now. */
1179 block->attr.block.graph_arr[pos] = res;
1184 #endif /* USE_FAST_PHI_CONSTRUCTION */
1186 /****************************************************************************/
1188 /** Finalize a Block node, when all control flows are known. */
1189 /** Acceptable parameters are only Block nodes. */
1191 mature_block (ir_node *block)
1198 assert (get_irn_opcode(block) == iro_Block);
1200 if (!get_Block_matured(block)) {
1202 /* turn the dynamic in-array into a static one. */
1203 ins = ARR_LEN (block->in)-1;
1204 NEW_ARR_A (ir_node *, nin, ins);
1206 /* Traverse a chain of Phi nodes attached to this block and mature
1208 for (n = block->link; n; n=next) {
1209 inc_irg_visited(current_ir_graph);
1211 exchange (n, phi_merge (block, n->attr.phi0_pos, n->mode, nin, ins));
1214 block->attr.block.matured = 1;
1216 /* Now, as the block is a finished firm node, we can optimize it.
1217 Since other nodes have been allocated since the block was created
1218 we can not free the node on the obstack. Therefore we have to call
1220 Unfortunately the optimization does not change a lot, as all allocated
1221 nodes refer to the unoptimized node. */
1222 block = optimize_in_place(block);
1228 new_Phi (int arity, ir_node **in, ir_mode *mode)
1230 return new_r_Phi (current_ir_graph, current_ir_graph->current_block,
1235 new_Const (ir_mode *mode, tarval *con)
1237 return new_r_Const (current_ir_graph, current_ir_graph->start_block,
1242 new_Id (ir_node *val, ir_mode *mode)
1244 return new_r_Id (current_ir_graph, current_ir_graph->current_block,
1249 new_Proj (ir_node *arg, ir_mode *mode, long proj)
1251 return new_r_Proj (current_ir_graph, current_ir_graph->current_block,
1256 new_Conv (ir_node *op, ir_mode *mode)
1258 return new_r_Conv (current_ir_graph, current_ir_graph->current_block,
1263 new_Tuple (int arity, ir_node **in)
1265 return new_r_Tuple (current_ir_graph, current_ir_graph->current_block,
1270 new_Add (ir_node *op1, ir_node *op2, ir_mode *mode)
1272 return new_r_Add (current_ir_graph, current_ir_graph->current_block,
1277 new_Sub (ir_node *op1, ir_node *op2, ir_mode *mode)
1279 return new_r_Sub (current_ir_graph, current_ir_graph->current_block,
1285 new_Minus (ir_node *op, ir_mode *mode)
1287 return new_r_Minus (current_ir_graph, current_ir_graph->current_block,
1292 new_Mul (ir_node *op1, ir_node *op2, ir_mode *mode)
1294 return new_r_Mul (current_ir_graph, current_ir_graph->current_block,
1299 new_Quot (ir_node *memop, ir_node *op1, ir_node *op2)
1301 return new_r_Quot (current_ir_graph, current_ir_graph->current_block,
1306 new_DivMod (ir_node *memop, ir_node *op1, ir_node *op2)
1308 return new_r_DivMod (current_ir_graph, current_ir_graph->current_block,
1313 new_Div (ir_node *memop, ir_node *op1, ir_node *op2)
1315 return new_r_Div (current_ir_graph, current_ir_graph->current_block,
1320 new_Mod (ir_node *memop, ir_node *op1, ir_node *op2)
1322 return new_r_Mod (current_ir_graph, current_ir_graph->current_block,
1327 new_And (ir_node *op1, ir_node *op2, ir_mode *mode)
1329 return new_r_And (current_ir_graph, current_ir_graph->current_block,
1334 new_Or (ir_node *op1, ir_node *op2, ir_mode *mode)
1336 return new_r_Or (current_ir_graph, current_ir_graph->current_block,
1341 new_Eor (ir_node *op1, ir_node *op2, ir_mode *mode)
1343 return new_r_Eor (current_ir_graph, current_ir_graph->current_block,
1348 new_Not (ir_node *op, ir_mode *mode)
1350 return new_r_Not (current_ir_graph, current_ir_graph->current_block,
1355 new_Shl (ir_node *op, ir_node *k, ir_mode *mode)
1357 return new_r_Shl (current_ir_graph, current_ir_graph->current_block,
1362 new_Shr (ir_node *op, ir_node *k, ir_mode *mode)
1364 return new_r_Shr (current_ir_graph, current_ir_graph->current_block,
1369 new_Shrs (ir_node *op, ir_node *k, ir_mode *mode)
1371 return new_r_Shrs (current_ir_graph, current_ir_graph->current_block,
1376 new_Rotate (ir_node *op, ir_node *k, ir_mode *mode)
1378 return new_r_Rot (current_ir_graph, current_ir_graph->current_block,
1383 new_Abs (ir_node *op, ir_mode *mode)
1385 return new_r_Abs (current_ir_graph, current_ir_graph->current_block,
1390 new_Cmp (ir_node *op1, ir_node *op2)
1392 return new_r_Cmp (current_ir_graph, current_ir_graph->current_block,
1399 return new_r_Jmp (current_ir_graph, current_ir_graph->current_block);
1403 new_Cond (ir_node *c)
1405 return new_r_Cond (current_ir_graph, current_ir_graph->current_block, c);
1409 new_Call (ir_node *store, ir_node *callee, int arity, ir_node **in,
1412 return new_r_Call (current_ir_graph, current_ir_graph->current_block,
1413 store, callee, arity, in, type);
1417 new_Return (ir_node* store, int arity, ir_node **in)
1419 return new_r_Return (current_ir_graph, current_ir_graph->current_block,
1424 new_Raise (ir_node *store, ir_node *obj)
1426 return new_r_Raise (current_ir_graph, current_ir_graph->current_block,
1431 new_Load (ir_node *store, ir_node *addr)
1433 return new_r_Load (current_ir_graph, current_ir_graph->current_block,
1438 new_Store (ir_node *store, ir_node *addr, ir_node *val)
1440 return new_r_Store (current_ir_graph, current_ir_graph->current_block,
1445 new_Alloc (ir_node *store, ir_node *size, type *alloc_type,
1448 return new_r_Alloc (current_ir_graph, current_ir_graph->current_block,
1449 store, size, alloc_type, where);
1453 new_Free (ir_node *store, ir_node *ptr, ir_node *size, type *free_type)
1455 return new_r_Free (current_ir_graph, current_ir_graph->current_block,
1456 store, ptr, size, free_type);
1460 new_simpleSel (ir_node *store, ir_node *objptr, entity *ent)
1461 /* GL: objptr was called frame before. Frame was a bad choice for the name
1462 as the operand could as well be a pointer to a dynamic object. */
1464 return new_r_Sel (current_ir_graph, current_ir_graph->current_block,
1465 store, objptr, 0, NULL, ent);
1469 new_Sel (ir_node *store, ir_node *objptr, int n_index, ir_node **index, entity *sel)
1471 return new_r_Sel (current_ir_graph, current_ir_graph->current_block,
1472 store, objptr, n_index, index, sel);
1476 new_SymConst (type_or_id *value, symconst_kind kind)
1478 return new_r_SymConst (current_ir_graph, current_ir_graph->current_block,
1483 new_Sync (int arity, ir_node** in)
1485 return new_r_Sync (current_ir_graph, current_ir_graph->current_block,
1493 return current_ir_graph->bad;
1496 /*************************************************************************/
1497 /* Comfortable interface with automatic Phi node construction. */
1498 /* (Uses also constructors of ?? interface, except new_Block. */
1499 /* add an adge to a jmp node */
1501 add_in_edge (ir_node *block, ir_node *jmp)
1503 if (block->attr.block.matured) {
1504 printf("Error: Block already matured!\n");
1507 assert (jmp != NULL);
1508 ARR_APP1 (ir_node *, block->in, jmp);
1512 /* changing the current block */
1514 switch_block (ir_node *target)
1516 current_ir_graph->current_block = target;
1519 /****************************/
1520 /* parameter administration */
1522 /* get a value from the parameter array from the current block by its index */
1524 get_value (int pos, ir_mode *mode)
1526 inc_irg_visited(current_ir_graph);
1527 return get_r_value_internal (current_ir_graph->current_block, pos + 1, mode);
1530 /* set a value at position pos in the parameter array from the current block */
1532 set_value (int pos, ir_node *value)
1534 current_ir_graph->current_block->attr.block.graph_arr[pos + 1] = value;
1537 /* get the current store */
1541 /* GL: one could call get_value instead */
1542 inc_irg_visited(current_ir_graph);
1543 return get_r_value_internal (current_ir_graph->current_block, 0, mode_M);
1546 /* set the current store */
1548 set_store (ir_node *store)
1550 /* GL: one could call set_value instead */
1551 current_ir_graph->current_block->attr.block.graph_arr[0] = store;
1554 /*************************************************************************/
1557 /* call once for each run of the library */