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);
662 /* This is a stack used for allocating and deallocating nodes in
663 new_r_Phi_in. The original implementation used the obstack
664 to model this stack, now it is explicit. This reduces side effects.
666 #if USE_EXPICIT_PHI_IN_STACK
671 res = (Phi_in_stack *) malloc ( sizeof (Phi_in_stack));
673 res->stack = NEW_ARR_F (ir_node *, 1);
679 void free_to_Phi_in_stack(ir_node *phi) {
680 assert(get_irn_opcode(phi) == iro_Phi);
682 if (ARR_LEN(current_ir_graph->Phi_in_stack->stack) ==
683 current_ir_graph->Phi_in_stack->pos)
684 ARR_APP1 (ir_node *, current_ir_graph->Phi_in_stack->stack, phi);
686 current_ir_graph->Phi_in_stack->stack[current_ir_graph->Phi_in_stack->pos] = phi;
688 (current_ir_graph->Phi_in_stack->pos)++;
692 alloc_or_pop_from_Phi_in_stack(ir_graph *irg, ir_node *block, ir_mode *mode,
693 int arity, ir_node **in) {
695 ir_node **stack = current_ir_graph->Phi_in_stack->stack;
696 int pos = current_ir_graph->Phi_in_stack->pos;
700 /* We need to allocate a new node */
701 res = new_ir_node (irg, block, op_Phi, mode, arity, in);
703 /* reuse the old node and initialize it again. */
706 assert (res->kind == k_ir_node);
707 assert (res->op == op_Phi);
712 /* ???!!! How to free the old in array?? */
713 res->in = NEW_ARR_D (ir_node *, irg->obst, (arity+1));
715 memcpy (&res->in[1], in, sizeof (ir_node *) * arity);
717 (current_ir_graph->Phi_in_stack->pos)--;
721 #endif /* USE_EXPICIT_PHI_IN_STACK */
723 /* Creates a Phi node with a given, fixed array **in of predecessors.
724 If the Phi node is unnecessary, as the same value reaches the block
725 through all control flow paths, it is eliminated and the value
726 returned directly. This constructor is only intended for use in
727 the automatic Phi node generation triggered by get_value or mature.
728 The implementation is quite tricky and depends on the fact, that
729 the nodes are allocated on a stack:
730 The in array contains predecessors and NULLs. The NULLs appear,
731 if get_r_value_internal, that computed the predecessors, reached
732 the same block on two paths. In this case the same value reaches
733 this block on both paths, there is no definition in between. We need
734 not allocate a Phi where these path's merge, but we have to communicate
735 this fact to the caller. This happens by returning a pointer to the
736 node the caller _will_ allocate. (Yes, we predict the address. We can
737 do so because the nodes are allocated on the obstack.) The caller then
738 finds a pointer to itself and, when this routine is called again,
742 new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode,
743 ir_node **in, int ins)
746 ir_node *res, *known;
748 /* allocate a new node on the obstack.
749 This can return a node to which some of the pointers in the in-array
751 Attention: the constructor copies the in array, i.e., the later changes
752 to the array in this routine do not affect the constructed node! If
753 the in array contains NULLs, there will be missing predecessors in the
755 Is this a possible internal state of the Phi node generation? */
756 #if USE_EXPICIT_PHI_IN_STACK
757 res = known = alloc_or_pop_from_Phi_in_stack(irg, block, mode, ins, in);
759 res = known = new_ir_node (irg, block, op_Phi, mode, ins, in);
761 /* The in-array can contain NULLs. These were returned by
762 get_r_value_internal if it reached the same block/definition on a
764 The NULLs are replaced by the node itself to simplify the test in the
766 for (i=0; i < ins; ++i)
767 if (in[i] == NULL) in[i] = res;
769 /* This loop checks whether the Phi has more than one predecessor.
770 If so, it is a real Phi node and we break the loop. Else the
771 Phi node merges the same definition on several paths and therefore
773 for (i=0; i < ins; ++i)
775 if (in[i]==res || in[i]==known) continue;
783 /* i==ins: there is at most one predecessor, we don't need a phi node. */
785 #if USE_EXPICIT_PHI_IN_STACK
786 free_to_Phi_in_stack(res);
788 obstack_free (current_ir_graph->obst, res);
792 res = optimize (res);
796 /* return the pointer to the Phi node. This node might be deallocated! */
801 get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
803 /** This function computes the predecessors for a real Phi node, and then
804 allocates and returns this node. The routine called to allocate the
805 node might optimize it away and return a real value, or even a pointer
806 to a deallocated Phi node on top of the obstack!
807 This function is called with an in-array of proper size. **/
808 static inline ir_node *
809 phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
811 ir_node *prevBlock, *res;
814 /* This loop goes to all predecessor blocks of the block the Phi node is in
815 and there finds the operands of the Phi node by calling
816 get_r_value_internal. */
817 for (i = 1; i <= ins; ++i) {
818 assert (block->in[i]);
819 prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */
821 nin[i-1] = get_r_value_internal (prevBlock, pos, mode);
824 /* After collecting all predecessors into the array nin a new Phi node
825 with these predecessors is created. This constructor contains an
826 optimization: If all predecessors of the Phi node are identical it
827 returns the only operand instead of a new Phi node. If the value
828 passes two different control flow edges without being defined, and
829 this is the second path treated, a pointer to the node that will be
830 allocated for the first path (recursion) is returned. We already
831 know the address of this node, as it is the next node to be allocated
832 and will be placed on top of the obstack. (The obstack is a _stack_!) */
833 res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins);
835 /* Now we now the value for "pos" and can enter it in the array with
836 all known local variables. Attention: this might be a pointer to
837 a node, that later will be allocated!!! See new_r_Phi_in.
838 If this is called in mature, after some set_value in the same block,
839 the proper value must not be overwritten:
841 get_value (makes Phi0, put's it into graph_arr)
842 set_value (overwrites Phi0 in graph_arr)
843 mature_block (upgrades Phi0, puts it again into graph_arr, overwriting
846 if (!block->attr.block.graph_arr[pos]) {
847 block->attr.block.graph_arr[pos] = res;
849 /* printf(" value already computed by %s\n",
850 id_to_str(block->attr.block.graph_arr[pos]->op->name)); */
856 /* This function returns the last definition of a variable. In case
857 this variable was last defined in a previous block, Phi nodes are
858 inserted. If the part of the firm graph containing the definition
859 is not yet constructed, a dummy Phi node is returned. */
861 get_r_value_internal (ir_node *block, int pos, ir_mode *mode)
864 /* There are 4 cases to treat.
866 1. The block is not mature and we visit it the first time. We can not
867 create a proper Phi node, therefore a Phi0, i.e., a Phi without
868 predecessors is returned. This node is added to the linked list (field
869 "link") of the containing block to be completed when this block is
870 matured. (Comlpletion will add a new Phi and turn the Phi0 into an Id
873 2. The value is already known in this block, graph_arr[pos] is set and we
874 visit the block the first time. We can return the value without
875 creating any new nodes.
877 3. The block is mature and we visit it the first time. A Phi node needs
878 to be created (phi_merge). If the Phi is not needed, as all it's
879 operands are the same value reaching the block through different
880 paths, it's optimized away and the value itself is returned.
882 4. The block is mature, and we visit it the second time. Now two
883 subcases are possible:
884 * The value was computed completely the last time we were here. This
885 is the case if there is no loop. We can return the proper value.
886 * The recursion that visited this node and set the flag did not
887 return yet. We are computing a value in a loop and need to
888 break the recursion without knowing the result yet.
889 @@@ strange case. Straight forward we would create a Phi before
890 starting the computation of it's predecessors. In this case we will find
891 a Phi here in any case. The problem is that this implementation only
892 creates a Phi after computing the predecessors, so that it is hard to
893 compute self references of this Phi. @@@
894 There is no simple check for the second subcase. Therefore we check
895 for a second visit and treat all such cases as the second subcase.
896 Anyways, the basic situation is the same: we reached a block
897 on two paths without finding a definition of the value: No Phi
898 nodes are needed on both paths.
899 We return this information "Two paths, no Phi needed" by a very tricky
900 implementation that relies on the fact that an obstack is a stack and
901 will return a node with the same address on different allocations.
902 Look also at phi_merge and new_r_phi_in to understand this.
903 @@@ Unfortunately this does not work, see testprogram three_cfpred_example.
907 /* case 4 -- already visited. */
908 if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) return NULL;
910 /* visited the first time */
911 set_irn_visited(block, get_irg_visited(current_ir_graph));
913 /* Get the local valid value */
914 res = block->attr.block.graph_arr[pos];
916 /* case 2 -- If the value is actually computed, return it. */
917 if (res) { return res;};
919 if (block->attr.block.matured) { /* case 3 */
921 /* The Phi has the same amount of ins as the corresponding block. */
922 int ins = get_irn_arity(block);
924 NEW_ARR_A (ir_node *, nin, ins);
926 /* Phi merge collects the predecessors and then creates a node. */
927 res = phi_merge (block, pos, mode, nin, ins);
929 } else { /* case 1 */
930 /* The block is not mature, we don't know how many in's are needed. A Phi
931 with zero predecessors is created. Such a Phi node is called Phi0
932 node. (There is also an obsolete Phi0 opcode.) The Phi0 is then added
933 to the list of Phi0 nodes in this block to be matured by mature_block
935 The Phi0 has to remember the pos of it's internal value. If the real
936 Phi is computed, pos is used to update the array with the local
939 res = new_r_Phi0 (current_ir_graph, block, mode);
940 res->attr.phi0_pos = pos;
941 res->link = block->link;
945 /* If we get here, the frontend missed a use-before-definition error */
948 printf("Error: no value set. Use of undefined variable. Initializing
950 assert (mode->code >= irm_f && mode->code <= irm_p);
951 res = new_r_Const (current_ir_graph, block, mode,
952 tarval_mode_null[mode->code]);
955 /* The local valid value is available now. */
956 block->attr.block.graph_arr[pos] = res;
963 /** This is the simple algorithm. If first generates a Phi0, then
964 it starts the recursion. This causes an Id at the entry of
965 every block that has no definition of the value! **/
968 Phi_in_stack * new_Phi_in_stack() { return NULL; }
971 new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode,
972 ir_node **in, int ins)
975 ir_node *res, *known;
977 /* Allocate a new node on the obstack. The allocation copies the in
979 res = new_ir_node (irg, block, op_Phi, mode, ins, in);
981 /* @@@GL The in-array should not contain NULLS with this algorithm.
982 Remove this test if it never is true. Just to make sure the algorithm runs. */
983 for (i=0; i < ins; ++i)
984 if (in[i] == NULL) assert(0);
986 /* This loop checks whether the Phi has more than one predecessor.
987 If so, it is a real Phi node and we break the loop. Else the
988 Phi node merges the same definition on several paths and therefore
989 is not needed. Don't consider Bad nodes! */
991 for (i=0; i < ins; ++i)
993 if (in[i]==res || in[i]==known || is_Bad(in[i])) continue;
1001 /* i==ins: there is at most one predecessor, we don't need a phi node. */
1004 obstack_free (current_ir_graph->obst, res);
1007 /* A undefined value, e.g., in unreachable code. */
1011 res = optimize (res);
1019 get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
1021 /** This function allocates a dummy Phi node to break recursions,
1022 computes the predecessors for the real phi node, and then
1023 allocates and returns this node. The routine called to allocate the
1024 node might optimize it away and return a real value.
1025 This function is called with an in-array of proper size. **/
1026 static inline ir_node *
1027 phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
1029 ir_node *prevBlock, *res, *phi0;
1033 /* If this block has no value at pos create a Phi0 and remember it
1034 in graph_arr to break recursions. */
1036 if (!block->attr.block.graph_arr[pos]) {
1037 /* Even if all variables are defined before use, it can happen that
1038 we get to the start block, if a cond has been replaced by a tuple
1039 (bad, jmp). As the start has a self referencing control flow edge,
1040 we get a self referencing Id, which is hard to optimize away. We avoid
1041 this by defining the value as a Bad node. *
1042 if (block == get_irg_start_block(current_ir_graph)) {
1043 block->attr.block.graph_arr[pos] = new_Bad();
1046 phi0 = new_r_Phi0(current_ir_graph, block, mode);
1047 block->attr.block.graph_arr[pos] = phi0;
1051 /* This loop goes to all predecessor blocks of the block the Phi node is in
1052 and there finds the operands of the Phi node by calling
1053 get_r_value_internal. */
1054 for (i = 1; i <= ins; ++i) {
1055 assert (block->in[i]);
1056 if (is_Bad(block->in[i])) {
1057 /* In case a Cond has been optimized we would get right to the start block
1058 with an invalid definition. */
1059 nin[i-1] = new_Bad();
1062 prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */
1064 if (!is_Bad(prevBlock)) {
1065 nin[i-1] = get_r_value_internal (prevBlock, pos, mode);
1067 nin[i-1] = new_Bad();
1071 /* After collecting all predecessors into the array nin a new Phi node
1072 with these predecessors is created. This constructor contains an
1073 optimization: If all predecessors of the Phi node are identical it
1074 returns the only operand instead of a new Phi node. */
1075 res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins);
1077 /* In case we allocated a Phi0 node at the beginning of this procedure,
1078 we need to exchange this Phi0 with the real Phi. */
1080 exchange(phi0, res);
1081 block->attr.block.graph_arr[pos] = res;
1087 /* This function returns the last definition of a variable. In case
1088 this variable was last defined in a previous block, Phi nodes are
1089 inserted. If the part of the firm graph containing the definition
1090 is not yet constructed, a dummy Phi node is returned. */
1092 get_r_value_internal (ir_node *block, int pos, ir_mode *mode)
1095 /* There are 4 cases to treat.
1097 1. The block is not mature and we visit it the first time. We can not
1098 create a proper Phi node, therefore a Phi0, i.e., a Phi without
1099 predecessors is returned. This node is added to the linked list (field
1100 "link") of the containing block to be completed when this block is
1101 matured. (Comlpletion will add a new Phi and turn the Phi0 into an Id
1104 2. The value is already known in this block, graph_arr[pos] is set and we
1105 visit the block the first time. We can return the value without
1106 creating any new nodes.
1108 3. The block is mature and we visit it the first time. A Phi node needs
1109 to be created (phi_merge). If the Phi is not needed, as all it's
1110 operands are the same value reaching the block through different
1111 paths, it's optimized away and the value itself is returned.
1113 4. The block is mature, and we visit it the second time. Now two
1114 subcases are possible:
1115 * The value was computed completely the last time we were here. This
1116 is the case if there is no loop. We can return the proper value.
1117 * The recursion that visited this node and set the flag did not
1118 return yet. We are computing a value in a loop and need to
1119 break the recursion. This case only happens if we visited
1120 the same block with phi_merge before, which inserted a Phi0.
1121 So we return the Phi0.
1124 /* case 4 -- already visited. */
1125 if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) {
1126 assert(block->attr.block.graph_arr[pos]);
1127 return block->attr.block.graph_arr[pos];
1130 /* visited the first time */
1131 set_irn_visited(block, get_irg_visited(current_ir_graph));
1133 /* Get the local valid value */
1134 res = block->attr.block.graph_arr[pos];
1136 /* case 2 -- If the value is actually computed, return it. */
1137 if (res) { return res;};
1139 if (block->attr.block.matured) { /* case 3 */
1141 /* The Phi has the same amount of ins as the corresponding block. */
1142 int ins = get_irn_arity(block);
1144 NEW_ARR_A (ir_node *, nin, ins);
1146 /* Phi merge collects the predecessors and then creates a node. */
1147 res = phi_merge (block, pos, mode, nin, ins);
1149 } else { /* case 1 */
1150 /* The block is not mature, we don't know how many in's are needed. A Phi
1151 with zero predecessors is created. Such a Phi node is called Phi0
1152 node. The Phi0 is then added to the list of Phi0 nodes in this block
1153 to be matured by mature_block later.
1154 The Phi0 has to remember the pos of it's internal value. If the real
1155 Phi is computed, pos is used to update the array with the local
1157 res = new_r_Phi0 (current_ir_graph, block, mode);
1158 res->attr.phi0_pos = pos;
1159 res->link = block->link;
1163 /* If we get here, the frontend missed a use-before-definition error */
1166 printf("Error: no value set. Use of undefined variable. Initializing
1168 assert (mode->code >= irm_f && mode->code <= irm_p);
1169 res = new_r_Const (current_ir_graph, block, mode,
1170 tarval_mode_null[mode->code]);
1173 /* The local valid value is available now. */
1174 block->attr.block.graph_arr[pos] = res;
1181 /****************************************************************************/
1183 /** Finalize a Block node, when all control flows are known. */
1184 /** Acceptable parameters are only Block nodes. */
1186 mature_block (ir_node *block)
1193 assert (get_irn_opcode(block) == iro_Block);
1195 if (!get_Block_matured(block)) {
1197 /* turn the dynamic in-array into a static one. */
1198 ins = ARR_LEN (block->in)-1;
1199 NEW_ARR_A (ir_node *, nin, ins);
1201 /* Traverse a chain of Phi nodes attached to this block and mature
1203 for (n = block->link; n; n=next) {
1204 inc_irg_visited(current_ir_graph);
1206 exchange (n, phi_merge (block, n->attr.phi0_pos, n->mode, nin, ins));
1209 block->attr.block.matured = 1;
1211 /* Now, as the block is a finished firm node, we can optimize it.
1212 Since other nodes have been allocated since the block was created
1213 we can not free the node on the obstack. Therefore we have to call
1215 Unfortunately the optimization does not change a lot, as all allocated
1216 nodes refer to the unoptimized node. */
1217 block = optimize_in_place(block);
1223 new_Phi (int arity, ir_node **in, ir_mode *mode)
1225 return new_r_Phi (current_ir_graph, current_ir_graph->current_block,
1230 new_Const (ir_mode *mode, tarval *con)
1232 return new_r_Const (current_ir_graph, current_ir_graph->start_block,
1237 new_Id (ir_node *val, ir_mode *mode)
1239 return new_r_Id (current_ir_graph, current_ir_graph->current_block,
1244 new_Proj (ir_node *arg, ir_mode *mode, long proj)
1246 return new_r_Proj (current_ir_graph, current_ir_graph->current_block,
1251 new_Conv (ir_node *op, ir_mode *mode)
1253 return new_r_Conv (current_ir_graph, current_ir_graph->current_block,
1258 new_Tuple (int arity, ir_node **in)
1260 return new_r_Tuple (current_ir_graph, current_ir_graph->current_block,
1265 new_Add (ir_node *op1, ir_node *op2, ir_mode *mode)
1267 return new_r_Add (current_ir_graph, current_ir_graph->current_block,
1272 new_Sub (ir_node *op1, ir_node *op2, ir_mode *mode)
1274 return new_r_Sub (current_ir_graph, current_ir_graph->current_block,
1280 new_Minus (ir_node *op, ir_mode *mode)
1282 return new_r_Minus (current_ir_graph, current_ir_graph->current_block,
1287 new_Mul (ir_node *op1, ir_node *op2, ir_mode *mode)
1289 return new_r_Mul (current_ir_graph, current_ir_graph->current_block,
1294 new_Quot (ir_node *memop, ir_node *op1, ir_node *op2)
1296 return new_r_Quot (current_ir_graph, current_ir_graph->current_block,
1301 new_DivMod (ir_node *memop, ir_node *op1, ir_node *op2)
1303 return new_r_DivMod (current_ir_graph, current_ir_graph->current_block,
1308 new_Div (ir_node *memop, ir_node *op1, ir_node *op2)
1310 return new_r_Div (current_ir_graph, current_ir_graph->current_block,
1315 new_Mod (ir_node *memop, ir_node *op1, ir_node *op2)
1317 return new_r_Mod (current_ir_graph, current_ir_graph->current_block,
1322 new_And (ir_node *op1, ir_node *op2, ir_mode *mode)
1324 return new_r_And (current_ir_graph, current_ir_graph->current_block,
1329 new_Or (ir_node *op1, ir_node *op2, ir_mode *mode)
1331 return new_r_Or (current_ir_graph, current_ir_graph->current_block,
1336 new_Eor (ir_node *op1, ir_node *op2, ir_mode *mode)
1338 return new_r_Eor (current_ir_graph, current_ir_graph->current_block,
1343 new_Not (ir_node *op, ir_mode *mode)
1345 return new_r_Not (current_ir_graph, current_ir_graph->current_block,
1350 new_Shl (ir_node *op, ir_node *k, ir_mode *mode)
1352 return new_r_Shl (current_ir_graph, current_ir_graph->current_block,
1357 new_Shr (ir_node *op, ir_node *k, ir_mode *mode)
1359 return new_r_Shr (current_ir_graph, current_ir_graph->current_block,
1364 new_Shrs (ir_node *op, ir_node *k, ir_mode *mode)
1366 return new_r_Shrs (current_ir_graph, current_ir_graph->current_block,
1371 new_Rotate (ir_node *op, ir_node *k, ir_mode *mode)
1373 return new_r_Rot (current_ir_graph, current_ir_graph->current_block,
1378 new_Abs (ir_node *op, ir_mode *mode)
1380 return new_r_Abs (current_ir_graph, current_ir_graph->current_block,
1385 new_Cmp (ir_node *op1, ir_node *op2)
1387 return new_r_Cmp (current_ir_graph, current_ir_graph->current_block,
1394 return new_r_Jmp (current_ir_graph, current_ir_graph->current_block);
1398 new_Cond (ir_node *c)
1400 return new_r_Cond (current_ir_graph, current_ir_graph->current_block, c);
1404 new_Call (ir_node *store, ir_node *callee, int arity, ir_node **in,
1407 return new_r_Call (current_ir_graph, current_ir_graph->current_block,
1408 store, callee, arity, in, type);
1412 new_Return (ir_node* store, int arity, ir_node **in)
1414 return new_r_Return (current_ir_graph, current_ir_graph->current_block,
1419 new_Raise (ir_node *store, ir_node *obj)
1421 return new_r_Raise (current_ir_graph, current_ir_graph->current_block,
1426 new_Load (ir_node *store, ir_node *addr)
1428 return new_r_Load (current_ir_graph, current_ir_graph->current_block,
1433 new_Store (ir_node *store, ir_node *addr, ir_node *val)
1435 return new_r_Store (current_ir_graph, current_ir_graph->current_block,
1440 new_Alloc (ir_node *store, ir_node *size, type *alloc_type,
1443 return new_r_Alloc (current_ir_graph, current_ir_graph->current_block,
1444 store, size, alloc_type, where);
1448 new_Free (ir_node *store, ir_node *ptr, ir_node *size, type *free_type)
1450 return new_r_Free (current_ir_graph, current_ir_graph->current_block,
1451 store, ptr, size, free_type);
1455 new_simpleSel (ir_node *store, ir_node *objptr, entity *ent)
1456 /* GL: objptr was called frame before. Frame was a bad choice for the name
1457 as the operand could as well be a pointer to a dynamic object. */
1459 return new_r_Sel (current_ir_graph, current_ir_graph->current_block,
1460 store, objptr, 0, NULL, ent);
1464 new_Sel (ir_node *store, ir_node *objptr, int n_index, ir_node **index, entity *sel)
1466 return new_r_Sel (current_ir_graph, current_ir_graph->current_block,
1467 store, objptr, n_index, index, sel);
1471 new_SymConst (type_or_id *value, symconst_kind kind)
1473 return new_r_SymConst (current_ir_graph, current_ir_graph->current_block,
1478 new_Sync (int arity, ir_node** in)
1480 return new_r_Sync (current_ir_graph, current_ir_graph->current_block,
1488 return current_ir_graph->bad;
1491 /*************************************************************************/
1492 /* Comfortable interface with automatic Phi node construction. */
1493 /* (Uses also constructors of ?? interface, except new_Block. */
1494 /* add an adge to a jmp node */
1496 add_in_edge (ir_node *block, ir_node *jmp)
1498 if (block->attr.block.matured) {
1499 printf("Error: Block already matured!\n");
1502 assert (jmp != NULL);
1503 ARR_APP1 (ir_node *, block->in, jmp);
1507 /* changing the current block */
1509 switch_block (ir_node *target)
1511 current_ir_graph->current_block = target;
1514 /****************************/
1515 /* parameter administration */
1517 /* get a value from the parameter array from the current block by its index */
1519 get_value (int pos, ir_mode *mode)
1521 inc_irg_visited(current_ir_graph);
1522 return get_r_value_internal (current_ir_graph->current_block, pos + 1, mode);
1525 /* set a value at position pos in the parameter array from the current block */
1527 set_value (int pos, ir_node *value)
1529 current_ir_graph->current_block->attr.block.graph_arr[pos + 1] = value;
1532 /* get the current store */
1536 /* GL: one could call get_value instead */
1537 inc_irg_visited(current_ir_graph);
1538 return get_r_value_internal (current_ir_graph->current_block, 0, mode_M);
1541 /* set the current store */
1543 set_store (ir_node *store)
1545 /* GL: one could call set_value instead */
1546 current_ir_graph->current_block->attr.block.graph_arr[0] = store;
1549 /*************************************************************************/
1552 /* call once for each run of the library */