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 *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 assert(is_method_type(type));
422 set_Call_type(res, type);
423 res = optimize (res);
429 new_r_Return (ir_graph *irg, ir_node *block,
430 ir_node *store, int arity, ir_node **in)
437 NEW_ARR_A (ir_node *, r_in, r_arity);
439 memcpy (&r_in[1], in, sizeof (ir_node *) * arity);
440 res = new_ir_node (irg, block, op_Return, mode_X, r_arity, r_in);
441 res = optimize (res);
447 new_r_Raise (ir_graph *irg, ir_node *block, ir_node *store, ir_node *obj)
449 ir_node *in[2] = {store, obj};
451 res = new_ir_node (irg, block, op_Raise, mode_X, 2, in);
453 res = optimize (res);
459 new_r_Load (ir_graph *irg, ir_node *block,
460 ir_node *store, ir_node *adr)
462 ir_node *in[2] = {store, adr};
464 res = new_ir_node (irg, block, op_Load, mode_T, 2, in);
466 res = optimize (res);
472 new_r_Store (ir_graph *irg, ir_node *block,
473 ir_node *store, ir_node *adr, ir_node *val)
475 ir_node *in[3] = {store, adr, val};
477 res = new_ir_node (irg, block, op_Store, mode_T, 3, in);
479 res = optimize (res);
485 new_r_Alloc (ir_graph *irg, ir_node *block, ir_node *store,
486 ir_node *size, type *alloc_type, where_alloc where)
488 ir_node *in[2] = {store, size};
490 res = new_ir_node (irg, block, op_Alloc, mode_T, 2, in);
492 res->attr.a.where = where;
493 res->attr.a.type = alloc_type;
495 res = optimize (res);
501 new_r_Free (ir_graph *irg, ir_node *block, ir_node *store,
502 ir_node *ptr, ir_node *size, type *free_type)
504 ir_node *in[3] = {store, ptr, size};
506 res = new_ir_node (irg, block, op_Free, mode_T, 3, in);
508 res->attr.f = free_type;
510 res = optimize (res);
516 new_r_Sel (ir_graph *irg, ir_node *block, ir_node *store, ir_node *objptr,
517 int arity, ir_node **in, entity *ent)
524 NEW_ARR_A (ir_node *, r_in, r_arity);
527 memcpy (&r_in[2], in, sizeof (ir_node *) * arity);
528 res = new_ir_node (irg, block, op_Sel, mode_p, r_arity, r_in);
530 res->attr.s.ltyp = static_linkage;
531 res->attr.s.ent = ent;
533 res = optimize (res);
539 new_r_SymConst (ir_graph *irg, ir_node *block, type_or_id_p value,
540 symconst_kind symkind)
545 if (symkind == linkage_ptr_info)
549 res = new_ir_node (irg, block, op_SymConst, mode, 0, in);
551 res->attr.i.num = symkind;
552 if (symkind == linkage_ptr_info) {
553 res->attr.i.tori.ptrinfo = (ident *)value;
555 assert ( ( (symkind == type_tag)
556 || (symkind == size))
557 && (is_type(value)));
558 res->attr.i.tori.typ = (type *)value;
560 res = optimize (res);
566 new_r_Sync (ir_graph *irg, ir_node *block, int arity, ir_node **in)
570 res = new_ir_node (irg, block, op_Sync, mode_M, arity, in);
572 res = optimize (res);
580 return current_ir_graph->bad;
583 /** ********************/
584 /** public interfaces */
585 /** construction tools */
587 /****f* ircons/new_Start
590 * new_Start -- create a new Start node in the current block
593 * s = new_Start(void);
594 * ir_node* new_Start(void);
597 * s - pointer to the created Start node
606 res = new_ir_node (current_ir_graph, current_ir_graph->current_block,
607 op_Start, mode_T, 0, NULL);
609 res = optimize (res);
619 res = new_ir_node (current_ir_graph, current_ir_graph->current_block,
620 op_End, mode_X, -1, NULL);
622 res = optimize (res);
628 /* Constructs a Block with a fixed number of predecessors.
629 Does set current_block. Can be used with automatic Phi
630 node construction. */
632 new_Block (int arity, ir_node **in)
636 res = new_r_Block (current_ir_graph, arity, in);
637 current_ir_graph->current_block = res;
639 /* Create and initialize array for Phi-node construction. */
640 res->attr.block.graph_arr = NEW_ARR_D (ir_node *, current_ir_graph->obst,
641 current_ir_graph->n_loc);
642 memset(res->attr.block.graph_arr, 0, sizeof(ir_node *)*current_ir_graph->n_loc);
644 res = optimize (res);
650 /* ***********************************************************************/
651 /* Methods necessary for automatic Phi node creation */
653 ir_node *phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
654 ir_node *get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
655 ir_node *new_r_Phi0 (ir_graph *irg, ir_node *block, ir_mode *mode)
656 ir_node *new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode, ir_node **in, int ins)
658 Call Graph: ( A ---> B == A "calls" B)
660 get_value mature_block
668 get_r_value_internal |
672 new_r_Phi0 new_r_Phi_in
674 * *************************************************************************** */
676 /* Creates a Phi node with 0 predecessors */
678 new_r_Phi0 (ir_graph *irg, ir_node *block, ir_mode *mode)
681 res = new_ir_node (irg, block, op_Phi, mode, 0, NULL);
686 /* There are two implementations of the Phi node construction. The first
687 is faster, but does not work for blocks with more than 2 predecessors.
688 The second works always but is slower and causes more unnecessary Phi
690 Select the implementations by the following preprocessor flag set in
692 #if USE_FAST_PHI_CONSTRUCTION
694 /* This is a stack used for allocating and deallocating nodes in
695 new_r_Phi_in. The original implementation used the obstack
696 to model this stack, now it is explicit. This reduces side effects.
698 #if USE_EXPICIT_PHI_IN_STACK
703 res = (Phi_in_stack *) malloc ( sizeof (Phi_in_stack));
705 res->stack = NEW_ARR_F (ir_node *, 1);
711 void free_to_Phi_in_stack(ir_node *phi) {
712 assert(get_irn_opcode(phi) == iro_Phi);
714 if (ARR_LEN(current_ir_graph->Phi_in_stack->stack) ==
715 current_ir_graph->Phi_in_stack->pos)
716 ARR_APP1 (ir_node *, current_ir_graph->Phi_in_stack->stack, phi);
718 current_ir_graph->Phi_in_stack->stack[current_ir_graph->Phi_in_stack->pos] = phi;
720 (current_ir_graph->Phi_in_stack->pos)++;
724 alloc_or_pop_from_Phi_in_stack(ir_graph *irg, ir_node *block, ir_mode *mode,
725 int arity, ir_node **in) {
727 ir_node **stack = current_ir_graph->Phi_in_stack->stack;
728 int pos = current_ir_graph->Phi_in_stack->pos;
732 /* We need to allocate a new node */
733 res = new_ir_node (irg, block, op_Phi, mode, arity, in);
735 /* reuse the old node and initialize it again. */
738 assert (res->kind == k_ir_node);
739 assert (res->op == op_Phi);
744 /* ???!!! How to free the old in array?? */
745 res->in = NEW_ARR_D (ir_node *, irg->obst, (arity+1));
747 memcpy (&res->in[1], in, sizeof (ir_node *) * arity);
749 (current_ir_graph->Phi_in_stack->pos)--;
753 #endif /* USE_EXPICIT_PHI_IN_STACK */
755 /* Creates a Phi node with a given, fixed array **in of predecessors.
756 If the Phi node is unnecessary, as the same value reaches the block
757 through all control flow paths, it is eliminated and the value
758 returned directly. This constructor is only intended for use in
759 the automatic Phi node generation triggered by get_value or mature.
760 The implementation is quite tricky and depends on the fact, that
761 the nodes are allocated on a stack:
762 The in array contains predecessors and NULLs. The NULLs appear,
763 if get_r_value_internal, that computed the predecessors, reached
764 the same block on two paths. In this case the same value reaches
765 this block on both paths, there is no definition in between. We need
766 not allocate a Phi where these path's merge, but we have to communicate
767 this fact to the caller. This happens by returning a pointer to the
768 node the caller _will_ allocate. (Yes, we predict the address. We can
769 do so because the nodes are allocated on the obstack.) The caller then
770 finds a pointer to itself and, when this routine is called again,
774 new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode,
775 ir_node **in, int ins)
778 ir_node *res, *known;
780 /* allocate a new node on the obstack.
781 This can return a node to which some of the pointers in the in-array
783 Attention: the constructor copies the in array, i.e., the later changes
784 to the array in this routine do not affect the constructed node! If
785 the in array contains NULLs, there will be missing predecessors in the
787 Is this a possible internal state of the Phi node generation? */
788 #if USE_EXPICIT_PHI_IN_STACK
789 res = known = alloc_or_pop_from_Phi_in_stack(irg, block, mode, ins, in);
791 res = known = new_ir_node (irg, block, op_Phi, mode, ins, in);
793 /* The in-array can contain NULLs. These were returned by
794 get_r_value_internal if it reached the same block/definition on a
796 The NULLs are replaced by the node itself to simplify the test in the
798 for (i=0; i < ins; ++i)
799 if (in[i] == NULL) in[i] = res;
801 /* This loop checks whether the Phi has more than one predecessor.
802 If so, it is a real Phi node and we break the loop. Else the
803 Phi node merges the same definition on several paths and therefore
805 for (i=0; i < ins; ++i)
807 if (in[i]==res || in[i]==known) continue;
815 /* i==ins: there is at most one predecessor, we don't need a phi node. */
817 #if USE_EXPICIT_PHI_IN_STACK
818 free_to_Phi_in_stack(res);
820 obstack_free (current_ir_graph->obst, res);
824 res = optimize (res);
828 /* return the pointer to the Phi node. This node might be deallocated! */
833 get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
835 /** This function computes the predecessors for a real Phi node, and then
836 allocates and returns this node. The routine called to allocate the
837 node might optimize it away and return a real value, or even a pointer
838 to a deallocated Phi node on top of the obstack!
839 This function is called with an in-array of proper size. **/
840 static inline ir_node *
841 phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
843 ir_node *prevBlock, *res;
846 /* This loop goes to all predecessor blocks of the block the Phi node is in
847 and there finds the operands of the Phi node by calling
848 get_r_value_internal. */
849 for (i = 1; i <= ins; ++i) {
850 assert (block->in[i]);
851 prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */
853 nin[i-1] = get_r_value_internal (prevBlock, pos, mode);
856 /* After collecting all predecessors into the array nin a new Phi node
857 with these predecessors is created. This constructor contains an
858 optimization: If all predecessors of the Phi node are identical it
859 returns the only operand instead of a new Phi node. If the value
860 passes two different control flow edges without being defined, and
861 this is the second path treated, a pointer to the node that will be
862 allocated for the first path (recursion) is returned. We already
863 know the address of this node, as it is the next node to be allocated
864 and will be placed on top of the obstack. (The obstack is a _stack_!) */
865 res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins);
867 /* Now we now the value for "pos" and can enter it in the array with
868 all known local variables. Attention: this might be a pointer to
869 a node, that later will be allocated!!! See new_r_Phi_in.
870 If this is called in mature, after some set_value in the same block,
871 the proper value must not be overwritten:
873 get_value (makes Phi0, put's it into graph_arr)
874 set_value (overwrites Phi0 in graph_arr)
875 mature_block (upgrades Phi0, puts it again into graph_arr, overwriting
878 if (!block->attr.block.graph_arr[pos]) {
879 block->attr.block.graph_arr[pos] = res;
881 /* printf(" value already computed by %s\n",
882 id_to_str(block->attr.block.graph_arr[pos]->op->name)); */
888 /* This function returns the last definition of a variable. In case
889 this variable was last defined in a previous block, Phi nodes are
890 inserted. If the part of the firm graph containing the definition
891 is not yet constructed, a dummy Phi node is returned. */
893 get_r_value_internal (ir_node *block, int pos, ir_mode *mode)
896 /* There are 4 cases to treat.
898 1. The block is not mature and we visit it the first time. We can not
899 create a proper Phi node, therefore a Phi0, i.e., a Phi without
900 predecessors is returned. This node is added to the linked list (field
901 "link") of the containing block to be completed when this block is
902 matured. (Comlpletion will add a new Phi and turn the Phi0 into an Id
905 2. The value is already known in this block, graph_arr[pos] is set and we
906 visit the block the first time. We can return the value without
907 creating any new nodes.
909 3. The block is mature and we visit it the first time. A Phi node needs
910 to be created (phi_merge). If the Phi is not needed, as all it's
911 operands are the same value reaching the block through different
912 paths, it's optimized away and the value itself is returned.
914 4. The block is mature, and we visit it the second time. Now two
915 subcases are possible:
916 * The value was computed completely the last time we were here. This
917 is the case if there is no loop. We can return the proper value.
918 * The recursion that visited this node and set the flag did not
919 return yet. We are computing a value in a loop and need to
920 break the recursion without knowing the result yet.
921 @@@ strange case. Straight forward we would create a Phi before
922 starting the computation of it's predecessors. In this case we will find
923 a Phi here in any case. The problem is that this implementation only
924 creates a Phi after computing the predecessors, so that it is hard to
925 compute self references of this Phi. @@@
926 There is no simple check for the second subcase. Therefore we check
927 for a second visit and treat all such cases as the second subcase.
928 Anyways, the basic situation is the same: we reached a block
929 on two paths without finding a definition of the value: No Phi
930 nodes are needed on both paths.
931 We return this information "Two paths, no Phi needed" by a very tricky
932 implementation that relies on the fact that an obstack is a stack and
933 will return a node with the same address on different allocations.
934 Look also at phi_merge and new_r_phi_in to understand this.
935 @@@ Unfortunately this does not work, see testprogram three_cfpred_example.
939 /* case 4 -- already visited. */
940 if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) return NULL;
942 /* visited the first time */
943 set_irn_visited(block, get_irg_visited(current_ir_graph));
945 /* Get the local valid value */
946 res = block->attr.block.graph_arr[pos];
948 /* case 2 -- If the value is actually computed, return it. */
949 if (res) { return res;};
951 if (block->attr.block.matured) { /* case 3 */
953 /* The Phi has the same amount of ins as the corresponding block. */
954 int ins = get_irn_arity(block);
956 NEW_ARR_A (ir_node *, nin, ins);
958 /* Phi merge collects the predecessors and then creates a node. */
959 res = phi_merge (block, pos, mode, nin, ins);
961 } else { /* case 1 */
962 /* The block is not mature, we don't know how many in's are needed. A Phi
963 with zero predecessors is created. Such a Phi node is called Phi0
964 node. (There is also an obsolete Phi0 opcode.) The Phi0 is then added
965 to the list of Phi0 nodes in this block to be matured by mature_block
967 The Phi0 has to remember the pos of it's internal value. If the real
968 Phi is computed, pos is used to update the array with the local
971 res = new_r_Phi0 (current_ir_graph, block, mode);
972 res->attr.phi0_pos = pos;
973 res->link = block->link;
977 /* If we get here, the frontend missed a use-before-definition error */
980 printf("Error: no value set. Use of undefined variable. Initializing
982 assert (mode->code >= irm_f && mode->code <= irm_p);
983 res = new_r_Const (current_ir_graph, block, mode,
984 tarval_mode_null[mode->code]);
987 /* The local valid value is available now. */
988 block->attr.block.graph_arr[pos] = res;
995 /** This is the simple algorithm. If first generates a Phi0, then
996 it starts the recursion. This causes an Id at the entry of
997 every block that has no definition of the value! **/
999 #if USE_EXPICIT_PHI_IN_STACK
1001 Phi_in_stack * new_Phi_in_stack() { return NULL; }
1005 new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode,
1006 ir_node **in, int ins)
1009 ir_node *res, *known;
1011 /* Allocate a new node on the obstack. The allocation copies the in
1013 res = new_ir_node (irg, block, op_Phi, mode, ins, in);
1015 /* This loop checks whether the Phi has more than one predecessor.
1016 If so, it is a real Phi node and we break the loop. Else the
1017 Phi node merges the same definition on several paths and therefore
1018 is not needed. Don't consider Bad nodes! */
1020 for (i=0; i < ins; ++i)
1022 if (in[i]==res || in[i]==known || is_Bad(in[i])) continue;
1030 /* i==ins: there is at most one predecessor, we don't need a phi node. */
1033 obstack_free (current_ir_graph->obst, res);
1036 /* A undefined value, e.g., in unreachable code. */
1040 res = optimize (res);
1048 get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
1050 /** This function allocates a dummy Phi node to break recursions,
1051 computes the predecessors for the real phi node, and then
1052 allocates and returns this node. The routine called to allocate the
1053 node might optimize it away and return a real value.
1054 This function is called with an in-array of proper size. **/
1055 static inline ir_node *
1056 phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
1058 ir_node *prevBlock, *res, *phi0;
1062 /* If this block has no value at pos create a Phi0 and remember it
1063 in graph_arr to break recursions. */
1065 if (!block->attr.block.graph_arr[pos]) {
1066 /* Even if all variables are defined before use, it can happen that
1067 we get to the start block, if a cond has been replaced by a tuple
1068 (bad, jmp). As the start has a self referencing control flow edge,
1069 we get a self referencing Id, which is hard to optimize away. We avoid
1070 this by defining the value as a Bad node. *
1071 if (block == get_irg_start_block(current_ir_graph)) {
1072 block->attr.block.graph_arr[pos] = new_Bad();
1075 phi0 = new_r_Phi0(current_ir_graph, block, mode);
1076 block->attr.block.graph_arr[pos] = phi0;
1080 /* This loop goes to all predecessor blocks of the block the Phi node
1081 is in and there finds the operands of the Phi node by calling
1082 get_r_value_internal. */
1083 for (i = 1; i <= ins; ++i) {
1084 assert (block->in[i]);
1085 if (is_Bad(block->in[i])) {
1086 /* In case a Cond has been optimized we would get right to the start block
1087 with an invalid definition. */
1088 nin[i-1] = new_Bad();
1091 prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */
1093 if (!is_Bad(prevBlock)) {
1094 nin[i-1] = get_r_value_internal (prevBlock, pos, mode);
1096 nin[i-1] = new_Bad();
1100 /* After collecting all predecessors into the array nin a new Phi node
1101 with these predecessors is created. This constructor contains an
1102 optimization: If all predecessors of the Phi node are identical it
1103 returns the only operand instead of a new Phi node. */
1104 res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins);
1106 /* In case we allocated a Phi0 node at the beginning of this procedure,
1107 we need to exchange this Phi0 with the real Phi. */
1109 exchange(phi0, res);
1110 block->attr.block.graph_arr[pos] = res;
1116 /* This function returns the last definition of a variable. In case
1117 this variable was last defined in a previous block, Phi nodes are
1118 inserted. If the part of the firm graph containing the definition
1119 is not yet constructed, a dummy Phi node is returned. */
1121 get_r_value_internal (ir_node *block, int pos, ir_mode *mode)
1124 /* There are 4 cases to treat.
1126 1. The block is not mature and we visit it the first time. We can not
1127 create a proper Phi node, therefore a Phi0, i.e., a Phi without
1128 predecessors is returned. This node is added to the linked list (field
1129 "link") of the containing block to be completed when this block is
1130 matured. (Comlpletion will add a new Phi and turn the Phi0 into an Id
1133 2. The value is already known in this block, graph_arr[pos] is set and we
1134 visit the block the first time. We can return the value without
1135 creating any new nodes.
1137 3. The block is mature and we visit it the first time. A Phi node needs
1138 to be created (phi_merge). If the Phi is not needed, as all it's
1139 operands are the same value reaching the block through different
1140 paths, it's optimized away and the value itself is returned.
1142 4. The block is mature, and we visit it the second time. Now two
1143 subcases are possible:
1144 * The value was computed completely the last time we were here. This
1145 is the case if there is no loop. We can return the proper value.
1146 * The recursion that visited this node and set the flag did not
1147 return yet. We are computing a value in a loop and need to
1148 break the recursion. This case only happens if we visited
1149 the same block with phi_merge before, which inserted a Phi0.
1150 So we return the Phi0.
1153 /* case 4 -- already visited. */
1154 if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) {
1155 /* As phi_merge allocates a Phi0 this value is always defined. Here
1156 is the critical difference of the two algorithms. */
1157 assert(block->attr.block.graph_arr[pos]);
1158 return block->attr.block.graph_arr[pos];
1161 /* visited the first time */
1162 set_irn_visited(block, get_irg_visited(current_ir_graph));
1164 /* Get the local valid value */
1165 res = block->attr.block.graph_arr[pos];
1167 /* case 2 -- If the value is actually computed, return it. */
1168 if (res) { return res; };
1170 if (block->attr.block.matured) { /* case 3 */
1172 /* The Phi has the same amount of ins as the corresponding block. */
1173 int ins = get_irn_arity(block);
1175 NEW_ARR_A (ir_node *, nin, ins);
1177 /* Phi merge collects the predecessors and then creates a node. */
1178 res = phi_merge (block, pos, mode, nin, ins);
1180 } else { /* case 1 */
1181 /* The block is not mature, we don't know how many in's are needed. A Phi
1182 with zero predecessors is created. Such a Phi node is called Phi0
1183 node. The Phi0 is then added to the list of Phi0 nodes in this block
1184 to be matured by mature_block later.
1185 The Phi0 has to remember the pos of it's internal value. If the real
1186 Phi is computed, pos is used to update the array with the local
1188 res = new_r_Phi0 (current_ir_graph, block, mode);
1189 res->attr.phi0_pos = pos;
1190 res->link = block->link;
1194 /* If we get here, the frontend missed a use-before-definition error */
1197 printf("Error: no value set. Use of undefined variable. Initializing
1199 assert (mode->code >= irm_f && mode->code <= irm_p);
1200 res = new_r_Const (current_ir_graph, block, mode,
1201 tarval_mode_null[mode->code]);
1204 /* The local valid value is available now. */
1205 block->attr.block.graph_arr[pos] = res;
1210 #endif /* USE_FAST_PHI_CONSTRUCTION */
1212 /* ************************************************************************** */
1214 /** Finalize a Block node, when all control flows are known. */
1215 /** Acceptable parameters are only Block nodes. */
1217 mature_block (ir_node *block)
1224 assert (get_irn_opcode(block) == iro_Block);
1226 if (!get_Block_matured(block)) {
1228 /* turn the dynamic in-array into a static one. */
1229 ins = ARR_LEN (block->in)-1;
1230 NEW_ARR_A (ir_node *, nin, ins);
1231 /* @@@ something is strange here... why isn't the array copied? */
1233 /* Traverse a chain of Phi nodes attached to this block and mature
1235 for (n = block->link; n; n=next) {
1236 inc_irg_visited(current_ir_graph);
1238 exchange (n, phi_merge (block, n->attr.phi0_pos, n->mode, nin, ins));
1241 block->attr.block.matured = 1;
1243 /* Now, as the block is a finished firm node, we can optimize it.
1244 Since other nodes have been allocated since the block was created
1245 we can not free the node on the obstack. Therefore we have to call
1247 Unfortunately the optimization does not change a lot, as all allocated
1248 nodes refer to the unoptimized node. */
1249 block = optimize_in_place(block);
1255 new_Phi (int arity, ir_node **in, ir_mode *mode)
1257 return new_r_Phi (current_ir_graph, current_ir_graph->current_block,
1262 new_Const (ir_mode *mode, tarval *con)
1264 return new_r_Const (current_ir_graph, current_ir_graph->start_block,
1269 new_Id (ir_node *val, ir_mode *mode)
1271 return new_r_Id (current_ir_graph, current_ir_graph->current_block,
1276 new_Proj (ir_node *arg, ir_mode *mode, long proj)
1278 return new_r_Proj (current_ir_graph, current_ir_graph->current_block,
1283 new_Conv (ir_node *op, ir_mode *mode)
1285 return new_r_Conv (current_ir_graph, current_ir_graph->current_block,
1290 new_Tuple (int arity, ir_node **in)
1292 return new_r_Tuple (current_ir_graph, current_ir_graph->current_block,
1297 new_Add (ir_node *op1, ir_node *op2, ir_mode *mode)
1299 return new_r_Add (current_ir_graph, current_ir_graph->current_block,
1304 new_Sub (ir_node *op1, ir_node *op2, ir_mode *mode)
1306 return new_r_Sub (current_ir_graph, current_ir_graph->current_block,
1312 new_Minus (ir_node *op, ir_mode *mode)
1314 return new_r_Minus (current_ir_graph, current_ir_graph->current_block,
1319 new_Mul (ir_node *op1, ir_node *op2, ir_mode *mode)
1321 return new_r_Mul (current_ir_graph, current_ir_graph->current_block,
1326 new_Quot (ir_node *memop, ir_node *op1, ir_node *op2)
1328 return new_r_Quot (current_ir_graph, current_ir_graph->current_block,
1333 new_DivMod (ir_node *memop, ir_node *op1, ir_node *op2)
1335 return new_r_DivMod (current_ir_graph, current_ir_graph->current_block,
1340 new_Div (ir_node *memop, ir_node *op1, ir_node *op2)
1342 return new_r_Div (current_ir_graph, current_ir_graph->current_block,
1347 new_Mod (ir_node *memop, ir_node *op1, ir_node *op2)
1349 return new_r_Mod (current_ir_graph, current_ir_graph->current_block,
1354 new_And (ir_node *op1, ir_node *op2, ir_mode *mode)
1356 return new_r_And (current_ir_graph, current_ir_graph->current_block,
1361 new_Or (ir_node *op1, ir_node *op2, ir_mode *mode)
1363 return new_r_Or (current_ir_graph, current_ir_graph->current_block,
1368 new_Eor (ir_node *op1, ir_node *op2, ir_mode *mode)
1370 return new_r_Eor (current_ir_graph, current_ir_graph->current_block,
1375 new_Not (ir_node *op, ir_mode *mode)
1377 return new_r_Not (current_ir_graph, current_ir_graph->current_block,
1382 new_Shl (ir_node *op, ir_node *k, ir_mode *mode)
1384 return new_r_Shl (current_ir_graph, current_ir_graph->current_block,
1389 new_Shr (ir_node *op, ir_node *k, ir_mode *mode)
1391 return new_r_Shr (current_ir_graph, current_ir_graph->current_block,
1396 new_Shrs (ir_node *op, ir_node *k, ir_mode *mode)
1398 return new_r_Shrs (current_ir_graph, current_ir_graph->current_block,
1403 new_Rotate (ir_node *op, ir_node *k, ir_mode *mode)
1405 return new_r_Rot (current_ir_graph, current_ir_graph->current_block,
1410 new_Abs (ir_node *op, ir_mode *mode)
1412 return new_r_Abs (current_ir_graph, current_ir_graph->current_block,
1417 new_Cmp (ir_node *op1, ir_node *op2)
1419 return new_r_Cmp (current_ir_graph, current_ir_graph->current_block,
1426 return new_r_Jmp (current_ir_graph, current_ir_graph->current_block);
1430 new_Cond (ir_node *c)
1432 return new_r_Cond (current_ir_graph, current_ir_graph->current_block, c);
1436 new_Call (ir_node *store, ir_node *callee, int arity, ir_node **in,
1439 return new_r_Call (current_ir_graph, current_ir_graph->current_block,
1440 store, callee, arity, in, type);
1444 new_Return (ir_node* store, int arity, ir_node **in)
1446 return new_r_Return (current_ir_graph, current_ir_graph->current_block,
1451 new_Raise (ir_node *store, ir_node *obj)
1453 return new_r_Raise (current_ir_graph, current_ir_graph->current_block,
1458 new_Load (ir_node *store, ir_node *addr)
1460 return new_r_Load (current_ir_graph, current_ir_graph->current_block,
1465 new_Store (ir_node *store, ir_node *addr, ir_node *val)
1467 return new_r_Store (current_ir_graph, current_ir_graph->current_block,
1472 new_Alloc (ir_node *store, ir_node *size, type *alloc_type,
1475 return new_r_Alloc (current_ir_graph, current_ir_graph->current_block,
1476 store, size, alloc_type, where);
1480 new_Free (ir_node *store, ir_node *ptr, ir_node *size, type *free_type)
1482 return new_r_Free (current_ir_graph, current_ir_graph->current_block,
1483 store, ptr, size, free_type);
1487 new_simpleSel (ir_node *store, ir_node *objptr, entity *ent)
1488 /* GL: objptr was called frame before. Frame was a bad choice for the name
1489 as the operand could as well be a pointer to a dynamic object. */
1491 return new_r_Sel (current_ir_graph, current_ir_graph->current_block,
1492 store, objptr, 0, NULL, ent);
1496 new_Sel (ir_node *store, ir_node *objptr, int n_index, ir_node **index, entity *sel)
1498 return new_r_Sel (current_ir_graph, current_ir_graph->current_block,
1499 store, objptr, n_index, index, sel);
1503 new_SymConst (type_or_id_p value, symconst_kind kind)
1505 return new_r_SymConst (current_ir_graph, current_ir_graph->current_block,
1510 new_Sync (int arity, ir_node** in)
1512 return new_r_Sync (current_ir_graph, current_ir_graph->current_block,
1520 return current_ir_graph->bad;
1523 /* ********************************************************************* */
1524 /* Comfortable interface with automatic Phi node construction. */
1525 /* (Uses also constructors of ?? interface, except new_Block. */
1526 /* ********************************************************************* */
1528 /** Block construction **/
1529 /* immature Block without predecessors */
1530 ir_node *new_immBlock (void) {
1533 /* creates a new dynamic in-array as length of in is -1 */
1534 res = new_ir_node (current_ir_graph, NULL, op_Block, mode_R, -1, NULL);
1535 current_ir_graph->current_block = res;
1536 res->attr.block.matured = 0;
1537 set_Block_block_visited(res, 0);
1539 /* Create and initialize array for Phi-node construction. */
1540 res->attr.block.graph_arr = NEW_ARR_D (ir_node *, current_ir_graph->obst,
1541 current_ir_graph->n_loc);
1542 memset(res->attr.block.graph_arr, 0, sizeof(ir_node *)*current_ir_graph->n_loc);
1544 /* Immature block may not be optimized! */
1550 /* add an adge to a jmp/control flow node */
1552 add_in_edge (ir_node *block, ir_node *jmp)
1554 if (block->attr.block.matured) {
1555 printf("Error: Block already matured!\n");
1558 assert (jmp != NULL);
1559 ARR_APP1 (ir_node *, block->in, jmp);
1563 /* changing the current block */
1565 switch_block (ir_node *target)
1567 current_ir_graph->current_block = target;
1570 /* ************************ */
1571 /* parameter administration */
1573 /* get a value from the parameter array from the current block by its index */
1575 get_value (int pos, ir_mode *mode)
1577 inc_irg_visited(current_ir_graph);
1578 return get_r_value_internal (current_ir_graph->current_block, pos + 1, mode);
1582 /* set a value at position pos in the parameter array from the current block */
1584 set_value (int pos, ir_node *value)
1586 current_ir_graph->current_block->attr.block.graph_arr[pos + 1] = value;
1589 /* get the current store */
1593 /* GL: one could call get_value instead */
1594 inc_irg_visited(current_ir_graph);
1595 return get_r_value_internal (current_ir_graph->current_block, 0, mode_M);
1598 /* set the current store */
1600 set_store (ir_node *store)
1602 /* GL: one could call set_value instead */
1603 current_ir_graph->current_block->attr.block.graph_arr[0] = store;
1606 /* ********************************************************************* */
1609 /* call once for each run of the library */