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
923 find a Phi here in any case. The problem is that this implementation
924 only creates a Phi after computing the predecessors, so that it is
925 hard to 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
936 three_cfpred_example.
940 /* case 4 -- already visited. */
941 if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) return NULL;
943 /* visited the first time */
944 set_irn_visited(block, get_irg_visited(current_ir_graph));
946 /* Get the local valid value */
947 res = block->attr.block.graph_arr[pos];
949 /* case 2 -- If the value is actually computed, return it. */
950 if (res) { return res;};
952 if (block->attr.block.matured) { /* case 3 */
954 /* The Phi has the same amount of ins as the corresponding block. */
955 int ins = get_irn_arity(block);
957 NEW_ARR_A (ir_node *, nin, ins);
959 /* Phi merge collects the predecessors and then creates a node. */
960 res = phi_merge (block, pos, mode, nin, ins);
962 } else { /* case 1 */
963 /* The block is not mature, we don't know how many in's are needed. A Phi
964 with zero predecessors is created. Such a Phi node is called Phi0
965 node. (There is also an obsolete Phi0 opcode.) The Phi0 is then added
966 to the list of Phi0 nodes in this block to be matured by mature_block
968 The Phi0 has to remember the pos of it's internal value. If the real
969 Phi is computed, pos is used to update the array with the local
972 res = new_r_Phi0 (current_ir_graph, block, mode);
973 res->attr.phi0_pos = pos;
974 res->link = block->link;
978 /* If we get here, the frontend missed a use-before-definition error */
981 printf("Error: no value set. Use of undefined variable. Initializing
983 assert (mode->code >= irm_f && mode->code <= irm_p);
984 res = new_r_Const (current_ir_graph, block, mode,
985 tarval_mode_null[mode->code]);
988 /* The local valid value is available now. */
989 block->attr.block.graph_arr[pos] = res;
996 /** This is the simple algorithm. If first generates a Phi0, then
997 it starts the recursion. This causes an Id at the entry of
998 every block that has no definition of the value! **/
1000 #if USE_EXPICIT_PHI_IN_STACK
1002 Phi_in_stack * new_Phi_in_stack() { return NULL; }
1006 new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode,
1007 ir_node **in, int ins)
1010 ir_node *res, *known;
1012 /* Allocate a new node on the obstack. The allocation copies the in
1014 res = new_ir_node (irg, block, op_Phi, mode, ins, in);
1016 /* This loop checks whether the Phi has more than one predecessor.
1017 If so, it is a real Phi node and we break the loop. Else the
1018 Phi node merges the same definition on several paths and therefore
1019 is not needed. Don't consider Bad nodes! */
1021 for (i=0; i < ins; ++i)
1023 if (in[i]==res || in[i]==known || is_Bad(in[i])) continue;
1031 /* i==ins: there is at most one predecessor, we don't need a phi node. */
1034 obstack_free (current_ir_graph->obst, res);
1037 /* A undefined value, e.g., in unreachable code. */
1041 res = optimize (res);
1049 get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
1051 /** This function allocates a dummy Phi node to break recursions,
1052 computes the predecessors for the real phi node, and then
1053 allocates and returns this node. The routine called to allocate the
1054 node might optimize it away and return a real value.
1055 This function is called with an in-array of proper size. **/
1056 static inline ir_node *
1057 phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
1059 ir_node *prevBlock, *res, *phi0;
1063 /* If this block has no value at pos create a Phi0 and remember it
1064 in graph_arr to break recursions. */
1066 if (!block->attr.block.graph_arr[pos]) {
1067 /* This is commented out as collapsing to Bads is no good idea.
1068 Either we need an assert here, or we need to call a routine
1069 that deals with this case as appropriate for the given language.
1070 Right now a self referencing Id is created which will crash irg_vryfy().
1072 Even if all variables are defined before use, it can happen that
1073 we get to the start block, if a cond has been replaced by a tuple
1074 (bad, jmp). As the start has a self referencing control flow edge,
1075 we get a self referencing Id, which is hard to optimize away. We avoid
1076 this by defining the value as a Bad node. *
1077 if (block == get_irg_start_block(current_ir_graph)) {
1078 block->attr.block.graph_arr[pos] = new_Bad();
1081 phi0 = new_r_Phi0(current_ir_graph, block, mode);
1082 block->attr.block.graph_arr[pos] = phi0;
1086 /* This loop goes to all predecessor blocks of the block the Phi node
1087 is in and there finds the operands of the Phi node by calling
1088 get_r_value_internal. */
1089 for (i = 1; i <= ins; ++i) {
1090 assert (block->in[i]);
1091 if (is_Bad(block->in[i])) {
1092 /* In case a Cond has been optimized we would get right to the start block
1093 with an invalid definition. */
1094 nin[i-1] = new_Bad();
1097 prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */
1099 if (!is_Bad(prevBlock)) {
1100 nin[i-1] = get_r_value_internal (prevBlock, pos, mode);
1102 nin[i-1] = new_Bad();
1106 /* After collecting all predecessors into the array nin a new Phi node
1107 with these predecessors is created. This constructor contains an
1108 optimization: If all predecessors of the Phi node are identical it
1109 returns the only operand instead of a new Phi node. */
1110 res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins);
1112 /* In case we allocated a Phi0 node at the beginning of this procedure,
1113 we need to exchange this Phi0 with the real Phi. */
1115 exchange(phi0, res);
1116 block->attr.block.graph_arr[pos] = res;
1122 /* This function returns the last definition of a variable. In case
1123 this variable was last defined in a previous block, Phi nodes are
1124 inserted. If the part of the firm graph containing the definition
1125 is not yet constructed, a dummy Phi node is returned. */
1127 get_r_value_internal (ir_node *block, int pos, ir_mode *mode)
1130 /* There are 4 cases to treat.
1132 1. The block is not mature and we visit it the first time. We can not
1133 create a proper Phi node, therefore a Phi0, i.e., a Phi without
1134 predecessors is returned. This node is added to the linked list (field
1135 "link") of the containing block to be completed when this block is
1136 matured. (Comlpletion will add a new Phi and turn the Phi0 into an Id
1139 2. The value is already known in this block, graph_arr[pos] is set and we
1140 visit the block the first time. We can return the value without
1141 creating any new nodes.
1143 3. The block is mature and we visit it the first time. A Phi node needs
1144 to be created (phi_merge). If the Phi is not needed, as all it's
1145 operands are the same value reaching the block through different
1146 paths, it's optimized away and the value itself is returned.
1148 4. The block is mature, and we visit it the second time. Now two
1149 subcases are possible:
1150 * The value was computed completely the last time we were here. This
1151 is the case if there is no loop. We can return the proper value.
1152 * The recursion that visited this node and set the flag did not
1153 return yet. We are computing a value in a loop and need to
1154 break the recursion. This case only happens if we visited
1155 the same block with phi_merge before, which inserted a Phi0.
1156 So we return the Phi0.
1159 /* case 4 -- already visited. */
1160 if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) {
1161 /* As phi_merge allocates a Phi0 this value is always defined. Here
1162 is the critical difference of the two algorithms. */
1163 assert(block->attr.block.graph_arr[pos]);
1164 return block->attr.block.graph_arr[pos];
1167 /* visited the first time */
1168 set_irn_visited(block, get_irg_visited(current_ir_graph));
1170 /* Get the local valid value */
1171 res = block->attr.block.graph_arr[pos];
1173 /* case 2 -- If the value is actually computed, return it. */
1174 if (res) { return res; };
1176 if (block->attr.block.matured) { /* case 3 */
1178 /* The Phi has the same amount of ins as the corresponding block. */
1179 int ins = get_irn_arity(block);
1181 NEW_ARR_A (ir_node *, nin, ins);
1183 /* Phi merge collects the predecessors and then creates a node. */
1184 res = phi_merge (block, pos, mode, nin, ins);
1186 } else { /* case 1 */
1187 /* The block is not mature, we don't know how many in's are needed. A Phi
1188 with zero predecessors is created. Such a Phi node is called Phi0
1189 node. The Phi0 is then added to the list of Phi0 nodes in this block
1190 to be matured by mature_block later.
1191 The Phi0 has to remember the pos of it's internal value. If the real
1192 Phi is computed, pos is used to update the array with the local
1194 res = new_r_Phi0 (current_ir_graph, block, mode);
1195 res->attr.phi0_pos = pos;
1196 res->link = block->link;
1200 /* If we get here, the frontend missed a use-before-definition error */
1203 printf("Error: no value set. Use of undefined variable. Initializing
1205 assert (mode->code >= irm_f && mode->code <= irm_p);
1206 res = new_r_Const (current_ir_graph, block, mode,
1207 tarval_mode_null[mode->code]);
1210 /* The local valid value is available now. */
1211 block->attr.block.graph_arr[pos] = res;
1216 #endif /* USE_FAST_PHI_CONSTRUCTION */
1218 /* ************************************************************************** */
1220 /** Finalize a Block node, when all control flows are known. */
1221 /** Acceptable parameters are only Block nodes. */
1223 mature_block (ir_node *block)
1230 assert (get_irn_opcode(block) == iro_Block);
1232 if (!get_Block_matured(block)) {
1234 /* turn the dynamic in-array into a static one. */
1235 ins = ARR_LEN (block->in)-1;
1236 NEW_ARR_A (ir_node *, nin, ins);
1237 /* @@@ something is strange here... why isn't the array copied? */
1239 /* Traverse a chain of Phi nodes attached to this block and mature
1241 for (n = block->link; n; n=next) {
1242 inc_irg_visited(current_ir_graph);
1244 exchange (n, phi_merge (block, n->attr.phi0_pos, n->mode, nin, ins));
1247 block->attr.block.matured = 1;
1249 /* Now, as the block is a finished firm node, we can optimize it.
1250 Since other nodes have been allocated since the block was created
1251 we can not free the node on the obstack. Therefore we have to call
1253 Unfortunately the optimization does not change a lot, as all allocated
1254 nodes refer to the unoptimized node. */
1255 block = optimize_in_place(block);
1261 new_Phi (int arity, ir_node **in, ir_mode *mode)
1263 return new_r_Phi (current_ir_graph, current_ir_graph->current_block,
1268 new_Const (ir_mode *mode, tarval *con)
1270 return new_r_Const (current_ir_graph, current_ir_graph->start_block,
1275 new_Id (ir_node *val, ir_mode *mode)
1277 return new_r_Id (current_ir_graph, current_ir_graph->current_block,
1282 new_Proj (ir_node *arg, ir_mode *mode, long proj)
1284 return new_r_Proj (current_ir_graph, current_ir_graph->current_block,
1289 new_Conv (ir_node *op, ir_mode *mode)
1291 return new_r_Conv (current_ir_graph, current_ir_graph->current_block,
1296 new_Tuple (int arity, ir_node **in)
1298 return new_r_Tuple (current_ir_graph, current_ir_graph->current_block,
1303 new_Add (ir_node *op1, ir_node *op2, ir_mode *mode)
1305 return new_r_Add (current_ir_graph, current_ir_graph->current_block,
1310 new_Sub (ir_node *op1, ir_node *op2, ir_mode *mode)
1312 return new_r_Sub (current_ir_graph, current_ir_graph->current_block,
1318 new_Minus (ir_node *op, ir_mode *mode)
1320 return new_r_Minus (current_ir_graph, current_ir_graph->current_block,
1325 new_Mul (ir_node *op1, ir_node *op2, ir_mode *mode)
1327 return new_r_Mul (current_ir_graph, current_ir_graph->current_block,
1332 new_Quot (ir_node *memop, ir_node *op1, ir_node *op2)
1334 return new_r_Quot (current_ir_graph, current_ir_graph->current_block,
1339 new_DivMod (ir_node *memop, ir_node *op1, ir_node *op2)
1341 return new_r_DivMod (current_ir_graph, current_ir_graph->current_block,
1346 new_Div (ir_node *memop, ir_node *op1, ir_node *op2)
1348 return new_r_Div (current_ir_graph, current_ir_graph->current_block,
1353 new_Mod (ir_node *memop, ir_node *op1, ir_node *op2)
1355 return new_r_Mod (current_ir_graph, current_ir_graph->current_block,
1360 new_And (ir_node *op1, ir_node *op2, ir_mode *mode)
1362 return new_r_And (current_ir_graph, current_ir_graph->current_block,
1367 new_Or (ir_node *op1, ir_node *op2, ir_mode *mode)
1369 return new_r_Or (current_ir_graph, current_ir_graph->current_block,
1374 new_Eor (ir_node *op1, ir_node *op2, ir_mode *mode)
1376 return new_r_Eor (current_ir_graph, current_ir_graph->current_block,
1381 new_Not (ir_node *op, ir_mode *mode)
1383 return new_r_Not (current_ir_graph, current_ir_graph->current_block,
1388 new_Shl (ir_node *op, ir_node *k, ir_mode *mode)
1390 return new_r_Shl (current_ir_graph, current_ir_graph->current_block,
1395 new_Shr (ir_node *op, ir_node *k, ir_mode *mode)
1397 return new_r_Shr (current_ir_graph, current_ir_graph->current_block,
1402 new_Shrs (ir_node *op, ir_node *k, ir_mode *mode)
1404 return new_r_Shrs (current_ir_graph, current_ir_graph->current_block,
1409 new_Rotate (ir_node *op, ir_node *k, ir_mode *mode)
1411 return new_r_Rot (current_ir_graph, current_ir_graph->current_block,
1416 new_Abs (ir_node *op, ir_mode *mode)
1418 return new_r_Abs (current_ir_graph, current_ir_graph->current_block,
1423 new_Cmp (ir_node *op1, ir_node *op2)
1425 return new_r_Cmp (current_ir_graph, current_ir_graph->current_block,
1432 return new_r_Jmp (current_ir_graph, current_ir_graph->current_block);
1436 new_Cond (ir_node *c)
1438 return new_r_Cond (current_ir_graph, current_ir_graph->current_block, c);
1442 new_Call (ir_node *store, ir_node *callee, int arity, ir_node **in,
1445 return new_r_Call (current_ir_graph, current_ir_graph->current_block,
1446 store, callee, arity, in, type);
1450 new_Return (ir_node* store, int arity, ir_node **in)
1452 return new_r_Return (current_ir_graph, current_ir_graph->current_block,
1457 new_Raise (ir_node *store, ir_node *obj)
1459 return new_r_Raise (current_ir_graph, current_ir_graph->current_block,
1464 new_Load (ir_node *store, ir_node *addr)
1466 return new_r_Load (current_ir_graph, current_ir_graph->current_block,
1471 new_Store (ir_node *store, ir_node *addr, ir_node *val)
1473 return new_r_Store (current_ir_graph, current_ir_graph->current_block,
1478 new_Alloc (ir_node *store, ir_node *size, type *alloc_type,
1481 return new_r_Alloc (current_ir_graph, current_ir_graph->current_block,
1482 store, size, alloc_type, where);
1486 new_Free (ir_node *store, ir_node *ptr, ir_node *size, type *free_type)
1488 return new_r_Free (current_ir_graph, current_ir_graph->current_block,
1489 store, ptr, size, free_type);
1493 new_simpleSel (ir_node *store, ir_node *objptr, entity *ent)
1494 /* GL: objptr was called frame before. Frame was a bad choice for the name
1495 as the operand could as well be a pointer to a dynamic object. */
1497 return new_r_Sel (current_ir_graph, current_ir_graph->current_block,
1498 store, objptr, 0, NULL, ent);
1502 new_Sel (ir_node *store, ir_node *objptr, int n_index, ir_node **index, entity *sel)
1504 return new_r_Sel (current_ir_graph, current_ir_graph->current_block,
1505 store, objptr, n_index, index, sel);
1509 new_SymConst (type_or_id_p value, symconst_kind kind)
1511 return new_r_SymConst (current_ir_graph, current_ir_graph->current_block,
1516 new_Sync (int arity, ir_node** in)
1518 return new_r_Sync (current_ir_graph, current_ir_graph->current_block,
1526 return current_ir_graph->bad;
1529 /* ********************************************************************* */
1530 /* Comfortable interface with automatic Phi node construction. */
1531 /* (Uses also constructors of ?? interface, except new_Block. */
1532 /* ********************************************************************* */
1534 /** Block construction **/
1535 /* immature Block without predecessors */
1536 ir_node *new_immBlock (void) {
1539 /* creates a new dynamic in-array as length of in is -1 */
1540 res = new_ir_node (current_ir_graph, NULL, op_Block, mode_R, -1, NULL);
1541 current_ir_graph->current_block = res;
1542 res->attr.block.matured = 0;
1543 set_Block_block_visited(res, 0);
1545 /* Create and initialize array for Phi-node construction. */
1546 res->attr.block.graph_arr = NEW_ARR_D (ir_node *, current_ir_graph->obst,
1547 current_ir_graph->n_loc);
1548 memset(res->attr.block.graph_arr, 0, sizeof(ir_node *)*current_ir_graph->n_loc);
1550 /* Immature block may not be optimized! */
1556 /* add an adge to a jmp/control flow node */
1558 add_in_edge (ir_node *block, ir_node *jmp)
1560 if (block->attr.block.matured) {
1561 printf("Error: Block already matured!\n");
1564 assert (jmp != NULL);
1565 ARR_APP1 (ir_node *, block->in, jmp);
1569 /* changing the current block */
1571 switch_block (ir_node *target)
1573 current_ir_graph->current_block = target;
1576 /* ************************ */
1577 /* parameter administration */
1579 /* get a value from the parameter array from the current block by its index */
1581 get_value (int pos, ir_mode *mode)
1583 inc_irg_visited(current_ir_graph);
1584 return get_r_value_internal (current_ir_graph->current_block, pos + 1, mode);
1588 /* set a value at position pos in the parameter array from the current block */
1590 set_value (int pos, ir_node *value)
1592 current_ir_graph->current_block->attr.block.graph_arr[pos + 1] = value;
1595 /* get the current store */
1599 /* GL: one could call get_value instead */
1600 inc_irg_visited(current_ir_graph);
1601 return get_r_value_internal (current_ir_graph->current_block, 0, mode_M);
1604 /* set the current store */
1606 set_store (ir_node *store)
1608 /* GL: one could call set_value instead */
1609 current_ir_graph->current_block->attr.block.graph_arr[0] = store;
1612 /* ********************************************************************* */
1615 /* call once for each run of the library */