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
12 # include "irgraph_t.h"
13 # include "irnode_t.h"
14 # include "irmode_t.h"
22 /* memset belongs to string.h */
25 #if USE_EXPICIT_PHI_IN_STACK
26 /* A stack needed for the automatic Phi node construction in constructor
27 Phi_in. Redefinition in irgraph.c!! */
32 typedef struct Phi_in_stack Phi_in_stack;
35 /*********************************************** */
36 /** privat interfaces, for professional use only */
38 /* Constructs a Block with a fixed number of predecessors.
39 Does not set current_block. Can not be used with automatic
40 Phi node construction. */
42 new_r_Block (ir_graph *irg, int arity, ir_node **in)
46 res = new_ir_node (irg, NULL, op_Block, mode_R, arity, in);
47 set_Block_matured(res, 1);
48 set_Block_block_visited(res, 0);
55 new_r_Start (ir_graph *irg, ir_node *block)
59 res = new_ir_node (irg, block, op_Start, mode_T, 0, NULL);
66 new_r_End (ir_graph *irg, ir_node *block)
70 res = new_ir_node (irg, block, op_End, mode_X, -1, NULL);
76 /* Creates a Phi node with all predecessors. Calling this constructor
77 is only allowed if the corresponding block is mature. */
79 new_r_Phi (ir_graph *irg, ir_node *block, int arity, ir_node **in, ir_mode *mode)
83 assert( get_Block_matured(block) );
84 assert( get_irn_arity(block) == arity );
86 res = new_ir_node (irg, block, op_Phi, mode, arity, in);
94 new_r_Const (ir_graph *irg, ir_node *block, ir_mode *mode, tarval *con)
97 res = new_ir_node (irg, block, op_Const, mode, 0, NULL);
103 res = local_optimize_newby (res);
110 new_r_Id (ir_graph *irg, ir_node *block, ir_node *val, ir_mode *mode)
112 ir_node *in[1] = {val};
114 res = new_ir_node (irg, block, op_Id, mode, 1, in);
115 res = optimize (res);
121 new_r_Proj (ir_graph *irg, ir_node *block, ir_node *arg, ir_mode *mode,
124 ir_node *in[1] = {arg};
126 res = new_ir_node (irg, block, op_Proj, mode, 1, in);
127 res->attr.proj = proj;
130 assert(get_Proj_pred(res));
131 assert(get_nodes_Block(get_Proj_pred(res)));
133 res = optimize (res);
141 new_r_Conv (ir_graph *irg, ir_node *block, ir_node *op, ir_mode *mode)
143 ir_node *in[1] = {op};
145 res = new_ir_node (irg, block, op_Conv, mode, 1, in);
146 res = optimize (res);
153 new_r_Tuple (ir_graph *irg, ir_node *block, int arity, ir_node **in)
157 res = new_ir_node (irg, block, op_Tuple, mode_T, arity, in);
158 res = optimize (res);
164 new_r_Add (ir_graph *irg, ir_node *block,
165 ir_node *op1, ir_node *op2, ir_mode *mode)
167 ir_node *in[2] = {op1, op2};
169 res = new_ir_node (irg, block, op_Add, mode, 2, in);
170 res = optimize (res);
176 new_r_Sub (ir_graph *irg, ir_node *block,
177 ir_node *op1, ir_node *op2, ir_mode *mode)
179 ir_node *in[2] = {op1, op2};
181 res = new_ir_node (irg, block, op_Sub, mode, 2, in);
182 res = optimize (res);
188 new_r_Minus (ir_graph *irg, ir_node *block,
189 ir_node *op, ir_mode *mode)
191 ir_node *in[1] = {op};
193 res = new_ir_node (irg, block, op_Minus, mode, 1, in);
194 res = optimize (res);
200 new_r_Mul (ir_graph *irg, ir_node *block,
201 ir_node *op1, ir_node *op2, ir_mode *mode)
203 ir_node *in[2] = {op1, op2};
205 res = new_ir_node (irg, block, op_Mul, mode, 2, in);
206 res = optimize (res);
212 new_r_Quot (ir_graph *irg, ir_node *block,
213 ir_node *memop, ir_node *op1, ir_node *op2)
215 ir_node *in[3] = {memop, op1, op2};
217 res = new_ir_node (irg, block, op_Quot, mode_T, 3, in);
218 res = optimize (res);
224 new_r_DivMod (ir_graph *irg, ir_node *block,
225 ir_node *memop, ir_node *op1, ir_node *op2)
227 ir_node *in[3] = {memop, op1, op2};
229 res = new_ir_node (irg, block, op_DivMod, mode_T, 3, in);
230 res = optimize (res);
236 new_r_Div (ir_graph *irg, ir_node *block,
237 ir_node *memop, ir_node *op1, ir_node *op2)
239 ir_node *in[3] = {memop, op1, op2};
241 res = new_ir_node (irg, block, op_Div, mode_T, 3, in);
242 res = optimize (res);
248 new_r_Mod (ir_graph *irg, ir_node *block,
249 ir_node *memop, ir_node *op1, ir_node *op2)
251 ir_node *in[3] = {memop, op1, op2};
253 res = new_ir_node (irg, block, op_Mod, mode_T, 3, in);
254 res = optimize (res);
260 new_r_And (ir_graph *irg, ir_node *block,
261 ir_node *op1, ir_node *op2, ir_mode *mode)
263 ir_node *in[2] = {op1, op2};
265 res = new_ir_node (irg, block, op_And, mode, 2, in);
266 res = optimize (res);
272 new_r_Or (ir_graph *irg, ir_node *block,
273 ir_node *op1, ir_node *op2, ir_mode *mode)
275 ir_node *in[2] = {op1, op2};
277 res = new_ir_node (irg, block, op_Or, mode, 2, in);
278 res = optimize (res);
284 new_r_Eor (ir_graph *irg, ir_node *block,
285 ir_node *op1, ir_node *op2, ir_mode *mode)
287 ir_node *in[2] = {op1, op2};
289 res = new_ir_node (irg, block, op_Eor, mode, 2, in);
290 res = optimize (res);
296 new_r_Not (ir_graph *irg, ir_node *block,
297 ir_node *op, ir_mode *mode)
299 ir_node *in[1] = {op};
301 res = new_ir_node (irg, block, op_Not, mode, 1, in);
302 res = optimize (res);
308 new_r_Shl (ir_graph *irg, ir_node *block,
309 ir_node *op, ir_node *k, ir_mode *mode)
311 ir_node *in[2] = {op, k};
313 res = new_ir_node (irg, block, op_Shl, mode, 2, in);
314 res = optimize (res);
320 new_r_Shr (ir_graph *irg, ir_node *block,
321 ir_node *op, ir_node *k, ir_mode *mode)
323 ir_node *in[2] = {op, k};
325 res = new_ir_node (irg, block, op_Shr, mode, 2, in);
326 res = optimize (res);
332 new_r_Shrs (ir_graph *irg, ir_node *block,
333 ir_node *op, ir_node *k, ir_mode *mode)
335 ir_node *in[2] = {op, k};
337 res = new_ir_node (irg, block, op_Shrs, mode, 2, in);
338 res = optimize (res);
344 new_r_Rot (ir_graph *irg, ir_node *block,
345 ir_node *op, ir_node *k, ir_mode *mode)
347 ir_node *in[2] = {op, k};
349 res = new_ir_node (irg, block, op_Rot, mode, 2, in);
350 res = optimize (res);
356 new_r_Abs (ir_graph *irg, ir_node *block,
357 ir_node *op, ir_mode *mode)
359 ir_node *in[1] = {op};
361 res = new_ir_node (irg, block, op_Abs, mode, 1, in);
362 res = optimize (res);
368 new_r_Cmp (ir_graph *irg, ir_node *block,
369 ir_node *op1, ir_node *op2)
371 ir_node *in[2] = {op1, op2};
373 res = new_ir_node (irg, block, op_Cmp, mode_T, 2, in);
374 res = optimize (res);
380 new_r_Jmp (ir_graph *irg, ir_node *block)
384 res = new_ir_node (irg, block, op_Jmp, mode_X, 0, in);
385 res = optimize (res);
391 new_r_Cond (ir_graph *irg, ir_node *block, ir_node *c)
393 ir_node *in[1] = {c};
395 res = new_ir_node (irg, block, op_Cond, mode_T, 1, in);
396 res = optimize (res);
402 new_r_Call (ir_graph *irg, ir_node *block, ir_node *store,
403 ir_node *callee, int arity, ir_node **in, type_method *type)
410 NEW_ARR_A (ir_node *, r_in, r_arity);
413 memcpy (&r_in[2], in, sizeof (ir_node *) * arity);
415 res = new_ir_node (irg, block, op_Call, mode_T, r_arity, r_in);
417 set_Call_type(res, type);
418 res = optimize (res);
424 new_r_Return (ir_graph *irg, ir_node *block,
425 ir_node *store, int arity, ir_node **in)
432 NEW_ARR_A (ir_node *, r_in, r_arity);
434 memcpy (&r_in[1], in, sizeof (ir_node *) * arity);
435 res = new_ir_node (irg, block, op_Return, mode_X, r_arity, r_in);
436 res = optimize (res);
442 new_r_Raise (ir_graph *irg, ir_node *block, ir_node *store, ir_node *obj)
444 ir_node *in[2] = {store, obj};
446 res = new_ir_node (irg, block, op_Raise, mode_X, 2, in);
448 res = optimize (res);
454 new_r_Load (ir_graph *irg, ir_node *block,
455 ir_node *store, ir_node *adr)
457 ir_node *in[2] = {store, adr};
459 res = new_ir_node (irg, block, op_Load, mode_T, 2, in);
461 res = optimize (res);
467 new_r_Store (ir_graph *irg, ir_node *block,
468 ir_node *store, ir_node *adr, ir_node *val)
470 ir_node *in[3] = {store, adr, val};
472 res = new_ir_node (irg, block, op_Store, mode_T, 3, in);
474 res = optimize (res);
480 new_r_Alloc (ir_graph *irg, ir_node *block, ir_node *store,
481 ir_node *size, type *alloc_type, where_alloc where)
483 ir_node *in[2] = {store, size};
485 res = new_ir_node (irg, block, op_Alloc, mode_T, 2, in);
487 res->attr.a.where = where;
488 res->attr.a.type = alloc_type;
490 res = optimize (res);
496 new_r_Free (ir_graph *irg, ir_node *block, ir_node *store,
497 ir_node *ptr, ir_node *size, type *free_type)
499 ir_node *in[3] = {store, ptr, size};
501 res = new_ir_node (irg, block, op_Free, mode_T, 3, in);
503 res->attr.f = free_type;
505 res = optimize (res);
511 new_r_Sel (ir_graph *irg, ir_node *block, ir_node *store, ir_node *objptr,
512 int arity, ir_node **in, entity *ent)
519 NEW_ARR_A (ir_node *, r_in, r_arity);
522 memcpy (&r_in[2], in, sizeof (ir_node *) * arity);
523 res = new_ir_node (irg, block, op_Sel, mode_p, r_arity, r_in);
525 res->attr.s.ltyp = static_linkage;
526 res->attr.s.ent = ent;
528 res = optimize (res);
534 new_r_SymConst (ir_graph *irg, ir_node *block, type_or_id_p value,
535 symconst_kind symkind)
540 if (symkind == linkage_ptr_info)
544 res = new_ir_node (irg, block, op_SymConst, mode, 0, in);
546 res->attr.i.num = symkind;
547 if (symkind == linkage_ptr_info) {
548 res->attr.i.tori.ptrinfo = (ident *)value;
550 assert ( ( (symkind == type_tag)
551 || (symkind == size))
552 && (is_type(value)));
553 res->attr.i.tori.typ = (type *)value;
555 res = optimize (res);
561 new_r_Sync (ir_graph *irg, ir_node *block, int arity, ir_node **in)
565 res = new_ir_node (irg, block, op_Sync, mode_M, arity, in);
567 res = optimize (res);
575 return current_ir_graph->bad;
578 /***********************/
579 /** public interfaces */
580 /** construction tools */
587 res = new_ir_node (current_ir_graph, current_ir_graph->current_block,
588 op_Start, mode_T, 0, NULL);
590 res = optimize (res);
600 res = new_ir_node (current_ir_graph, current_ir_graph->current_block,
601 op_End, mode_X, -1, NULL);
603 res = optimize (res);
610 /* Constructs a Block with a fixed number of predecessors.
611 Does set current_block. Can be used with automatic Phi
612 node construction. */
614 new_Block (int arity, ir_node **in)
618 res = new_r_Block (current_ir_graph, arity, in);
619 current_ir_graph->current_block = res;
621 /* Create and initialize array for Phi-node construction. */
622 res->attr.block.graph_arr = NEW_ARR_D (ir_node *, current_ir_graph->obst,
623 current_ir_graph->n_loc);
624 memset(res->attr.block.graph_arr, 0, sizeof(ir_node *)*current_ir_graph->n_loc);
626 res = optimize (res);
635 return new_immBlock();
639 /*************************************************************************/
640 /* Methods necessary for automatic Phi node creation */
642 ir_node *phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
643 ir_node *get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
644 ir_node *new_r_Phi0 (ir_graph *irg, ir_node *block, ir_mode *mode)
645 ir_node *new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode, ir_node **in, int ins)
647 Call Graph: ( A ---> B == A "calls" B)
649 get_value mature_block
657 get_r_value_internal |
661 new_r_Phi0 new_r_Phi_in
663 *****************************************************************************/
665 /* Creates a Phi node with 0 predecessors */
667 new_r_Phi0 (ir_graph *irg, ir_node *block, ir_mode *mode)
670 res = new_ir_node (irg, block, op_Phi, mode, 0, NULL);
675 /* There are two implementations of the Phi node construction. The first
676 is faster, but does not work for blocks with more than 2 predecessors.
677 The second works always but is slower and causes more unnecessary Phi
679 Select the implementations by the following preprocessor flag set in
681 #if USE_FAST_PHI_CONSTRUCTION
683 /* This is a stack used for allocating and deallocating nodes in
684 new_r_Phi_in. The original implementation used the obstack
685 to model this stack, now it is explicit. This reduces side effects.
687 #if USE_EXPICIT_PHI_IN_STACK
692 res = (Phi_in_stack *) malloc ( sizeof (Phi_in_stack));
694 res->stack = NEW_ARR_F (ir_node *, 1);
700 void free_to_Phi_in_stack(ir_node *phi) {
701 assert(get_irn_opcode(phi) == iro_Phi);
703 if (ARR_LEN(current_ir_graph->Phi_in_stack->stack) ==
704 current_ir_graph->Phi_in_stack->pos)
705 ARR_APP1 (ir_node *, current_ir_graph->Phi_in_stack->stack, phi);
707 current_ir_graph->Phi_in_stack->stack[current_ir_graph->Phi_in_stack->pos] = phi;
709 (current_ir_graph->Phi_in_stack->pos)++;
713 alloc_or_pop_from_Phi_in_stack(ir_graph *irg, ir_node *block, ir_mode *mode,
714 int arity, ir_node **in) {
716 ir_node **stack = current_ir_graph->Phi_in_stack->stack;
717 int pos = current_ir_graph->Phi_in_stack->pos;
721 /* We need to allocate a new node */
722 res = new_ir_node (irg, block, op_Phi, mode, arity, in);
724 /* reuse the old node and initialize it again. */
727 assert (res->kind == k_ir_node);
728 assert (res->op == op_Phi);
733 /* ???!!! How to free the old in array?? */
734 res->in = NEW_ARR_D (ir_node *, irg->obst, (arity+1));
736 memcpy (&res->in[1], in, sizeof (ir_node *) * arity);
738 (current_ir_graph->Phi_in_stack->pos)--;
742 #endif /* USE_EXPICIT_PHI_IN_STACK */
744 /* Creates a Phi node with a given, fixed array **in of predecessors.
745 If the Phi node is unnecessary, as the same value reaches the block
746 through all control flow paths, it is eliminated and the value
747 returned directly. This constructor is only intended for use in
748 the automatic Phi node generation triggered by get_value or mature.
749 The implementation is quite tricky and depends on the fact, that
750 the nodes are allocated on a stack:
751 The in array contains predecessors and NULLs. The NULLs appear,
752 if get_r_value_internal, that computed the predecessors, reached
753 the same block on two paths. In this case the same value reaches
754 this block on both paths, there is no definition in between. We need
755 not allocate a Phi where these path's merge, but we have to communicate
756 this fact to the caller. This happens by returning a pointer to the
757 node the caller _will_ allocate. (Yes, we predict the address. We can
758 do so because the nodes are allocated on the obstack.) The caller then
759 finds a pointer to itself and, when this routine is called again,
763 new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode,
764 ir_node **in, int ins)
767 ir_node *res, *known;
769 /* allocate a new node on the obstack.
770 This can return a node to which some of the pointers in the in-array
772 Attention: the constructor copies the in array, i.e., the later changes
773 to the array in this routine do not affect the constructed node! If
774 the in array contains NULLs, there will be missing predecessors in the
776 Is this a possible internal state of the Phi node generation? */
777 #if USE_EXPICIT_PHI_IN_STACK
778 res = known = alloc_or_pop_from_Phi_in_stack(irg, block, mode, ins, in);
780 res = known = new_ir_node (irg, block, op_Phi, mode, ins, in);
782 /* The in-array can contain NULLs. These were returned by
783 get_r_value_internal if it reached the same block/definition on a
785 The NULLs are replaced by the node itself to simplify the test in the
787 for (i=0; i < ins; ++i)
788 if (in[i] == NULL) in[i] = res;
790 /* This loop checks whether the Phi has more than one predecessor.
791 If so, it is a real Phi node and we break the loop. Else the
792 Phi node merges the same definition on several paths and therefore
794 for (i=0; i < ins; ++i)
796 if (in[i]==res || in[i]==known) continue;
804 /* i==ins: there is at most one predecessor, we don't need a phi node. */
806 #if USE_EXPICIT_PHI_IN_STACK
807 free_to_Phi_in_stack(res);
809 obstack_free (current_ir_graph->obst, res);
813 res = optimize (res);
817 /* return the pointer to the Phi node. This node might be deallocated! */
822 get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
824 /** This function computes the predecessors for a real Phi node, and then
825 allocates and returns this node. The routine called to allocate the
826 node might optimize it away and return a real value, or even a pointer
827 to a deallocated Phi node on top of the obstack!
828 This function is called with an in-array of proper size. **/
829 static inline ir_node *
830 phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
832 ir_node *prevBlock, *res;
835 /* This loop goes to all predecessor blocks of the block the Phi node is in
836 and there finds the operands of the Phi node by calling
837 get_r_value_internal. */
838 for (i = 1; i <= ins; ++i) {
839 assert (block->in[i]);
840 prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */
842 nin[i-1] = get_r_value_internal (prevBlock, pos, mode);
845 /* After collecting all predecessors into the array nin a new Phi node
846 with these predecessors is created. This constructor contains an
847 optimization: If all predecessors of the Phi node are identical it
848 returns the only operand instead of a new Phi node. If the value
849 passes two different control flow edges without being defined, and
850 this is the second path treated, a pointer to the node that will be
851 allocated for the first path (recursion) is returned. We already
852 know the address of this node, as it is the next node to be allocated
853 and will be placed on top of the obstack. (The obstack is a _stack_!) */
854 res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins);
856 /* Now we now the value for "pos" and can enter it in the array with
857 all known local variables. Attention: this might be a pointer to
858 a node, that later will be allocated!!! See new_r_Phi_in.
859 If this is called in mature, after some set_value in the same block,
860 the proper value must not be overwritten:
862 get_value (makes Phi0, put's it into graph_arr)
863 set_value (overwrites Phi0 in graph_arr)
864 mature_block (upgrades Phi0, puts it again into graph_arr, overwriting
867 if (!block->attr.block.graph_arr[pos]) {
868 block->attr.block.graph_arr[pos] = res;
870 /* printf(" value already computed by %s\n",
871 id_to_str(block->attr.block.graph_arr[pos]->op->name)); */
877 /* This function returns the last definition of a variable. In case
878 this variable was last defined in a previous block, Phi nodes are
879 inserted. If the part of the firm graph containing the definition
880 is not yet constructed, a dummy Phi node is returned. */
882 get_r_value_internal (ir_node *block, int pos, ir_mode *mode)
885 /* There are 4 cases to treat.
887 1. The block is not mature and we visit it the first time. We can not
888 create a proper Phi node, therefore a Phi0, i.e., a Phi without
889 predecessors is returned. This node is added to the linked list (field
890 "link") of the containing block to be completed when this block is
891 matured. (Comlpletion will add a new Phi and turn the Phi0 into an Id
894 2. The value is already known in this block, graph_arr[pos] is set and we
895 visit the block the first time. We can return the value without
896 creating any new nodes.
898 3. The block is mature and we visit it the first time. A Phi node needs
899 to be created (phi_merge). If the Phi is not needed, as all it's
900 operands are the same value reaching the block through different
901 paths, it's optimized away and the value itself is returned.
903 4. The block is mature, and we visit it the second time. Now two
904 subcases are possible:
905 * The value was computed completely the last time we were here. This
906 is the case if there is no loop. We can return the proper value.
907 * The recursion that visited this node and set the flag did not
908 return yet. We are computing a value in a loop and need to
909 break the recursion without knowing the result yet.
910 @@@ strange case. Straight forward we would create a Phi before
911 starting the computation of it's predecessors. In this case we will find
912 a Phi here in any case. The problem is that this implementation only
913 creates a Phi after computing the predecessors, so that it is hard to
914 compute self references of this Phi. @@@
915 There is no simple check for the second subcase. Therefore we check
916 for a second visit and treat all such cases as the second subcase.
917 Anyways, the basic situation is the same: we reached a block
918 on two paths without finding a definition of the value: No Phi
919 nodes are needed on both paths.
920 We return this information "Two paths, no Phi needed" by a very tricky
921 implementation that relies on the fact that an obstack is a stack and
922 will return a node with the same address on different allocations.
923 Look also at phi_merge and new_r_phi_in to understand this.
924 @@@ Unfortunately this does not work, see testprogram three_cfpred_example.
928 /* case 4 -- already visited. */
929 if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) return NULL;
931 /* visited the first time */
932 set_irn_visited(block, get_irg_visited(current_ir_graph));
934 /* Get the local valid value */
935 res = block->attr.block.graph_arr[pos];
937 /* case 2 -- If the value is actually computed, return it. */
938 if (res) { return res;};
940 if (block->attr.block.matured) { /* case 3 */
942 /* The Phi has the same amount of ins as the corresponding block. */
943 int ins = get_irn_arity(block);
945 NEW_ARR_A (ir_node *, nin, ins);
947 /* Phi merge collects the predecessors and then creates a node. */
948 res = phi_merge (block, pos, mode, nin, ins);
950 } else { /* case 1 */
951 /* The block is not mature, we don't know how many in's are needed. A Phi
952 with zero predecessors is created. Such a Phi node is called Phi0
953 node. (There is also an obsolete Phi0 opcode.) The Phi0 is then added
954 to the list of Phi0 nodes in this block to be matured by mature_block
956 The Phi0 has to remember the pos of it's internal value. If the real
957 Phi is computed, pos is used to update the array with the local
960 res = new_r_Phi0 (current_ir_graph, block, mode);
961 res->attr.phi0_pos = pos;
962 res->link = block->link;
966 /* If we get here, the frontend missed a use-before-definition error */
969 printf("Error: no value set. Use of undefined variable. Initializing
971 assert (mode->code >= irm_f && mode->code <= irm_p);
972 res = new_r_Const (current_ir_graph, block, mode,
973 tarval_mode_null[mode->code]);
976 /* The local valid value is available now. */
977 block->attr.block.graph_arr[pos] = res;
984 /** This is the simple algorithm. If first generates a Phi0, then
985 it starts the recursion. This causes an Id at the entry of
986 every block that has no definition of the value! **/
988 #if USE_EXPICIT_PHI_IN_STACK
990 Phi_in_stack * new_Phi_in_stack() { return NULL; }
994 new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode,
995 ir_node **in, int ins)
998 ir_node *res, *known;
1000 /* Allocate a new node on the obstack. The allocation copies the in
1002 res = new_ir_node (irg, block, op_Phi, mode, ins, in);
1004 /* This loop checks whether the Phi has more than one predecessor.
1005 If so, it is a real Phi node and we break the loop. Else the
1006 Phi node merges the same definition on several paths and therefore
1007 is not needed. Don't consider Bad nodes! */
1009 for (i=0; i < ins; ++i)
1011 if (in[i]==res || in[i]==known || is_Bad(in[i])) continue;
1019 /* i==ins: there is at most one predecessor, we don't need a phi node. */
1022 obstack_free (current_ir_graph->obst, res);
1025 /* A undefined value, e.g., in unreachable code. */
1029 res = optimize (res);
1037 get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
1039 /** This function allocates a dummy Phi node to break recursions,
1040 computes the predecessors for the real phi node, and then
1041 allocates and returns this node. The routine called to allocate the
1042 node might optimize it away and return a real value.
1043 This function is called with an in-array of proper size. **/
1044 static inline ir_node *
1045 phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
1047 ir_node *prevBlock, *res, *phi0;
1051 /* If this block has no value at pos create a Phi0 and remember it
1052 in graph_arr to break recursions. */
1054 if (!block->attr.block.graph_arr[pos]) {
1055 /* Even if all variables are defined before use, it can happen that
1056 we get to the start block, if a cond has been replaced by a tuple
1057 (bad, jmp). As the start has a self referencing control flow edge,
1058 we get a self referencing Id, which is hard to optimize away. We avoid
1059 this by defining the value as a Bad node. *
1060 if (block == get_irg_start_block(current_ir_graph)) {
1061 block->attr.block.graph_arr[pos] = new_Bad();
1064 phi0 = new_r_Phi0(current_ir_graph, block, mode);
1065 block->attr.block.graph_arr[pos] = phi0;
1069 /* This loop goes to all predecessor blocks of the block the Phi node
1070 is in and there finds the operands of the Phi node by calling
1071 get_r_value_internal. */
1072 for (i = 1; i <= ins; ++i) {
1073 assert (block->in[i]);
1074 if (is_Bad(block->in[i])) {
1075 /* In case a Cond has been optimized we would get right to the start block
1076 with an invalid definition. */
1077 nin[i-1] = new_Bad();
1080 prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */
1082 if (!is_Bad(prevBlock)) {
1083 nin[i-1] = get_r_value_internal (prevBlock, pos, mode);
1085 nin[i-1] = new_Bad();
1089 /* After collecting all predecessors into the array nin a new Phi node
1090 with these predecessors is created. This constructor contains an
1091 optimization: If all predecessors of the Phi node are identical it
1092 returns the only operand instead of a new Phi node. */
1093 res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins);
1095 /* In case we allocated a Phi0 node at the beginning of this procedure,
1096 we need to exchange this Phi0 with the real Phi. */
1098 exchange(phi0, res);
1099 block->attr.block.graph_arr[pos] = res;
1105 /* This function returns the last definition of a variable. In case
1106 this variable was last defined in a previous block, Phi nodes are
1107 inserted. If the part of the firm graph containing the definition
1108 is not yet constructed, a dummy Phi node is returned. */
1110 get_r_value_internal (ir_node *block, int pos, ir_mode *mode)
1113 /* There are 4 cases to treat.
1115 1. The block is not mature and we visit it the first time. We can not
1116 create a proper Phi node, therefore a Phi0, i.e., a Phi without
1117 predecessors is returned. This node is added to the linked list (field
1118 "link") of the containing block to be completed when this block is
1119 matured. (Comlpletion will add a new Phi and turn the Phi0 into an Id
1122 2. The value is already known in this block, graph_arr[pos] is set and we
1123 visit the block the first time. We can return the value without
1124 creating any new nodes.
1126 3. The block is mature and we visit it the first time. A Phi node needs
1127 to be created (phi_merge). If the Phi is not needed, as all it's
1128 operands are the same value reaching the block through different
1129 paths, it's optimized away and the value itself is returned.
1131 4. The block is mature, and we visit it the second time. Now two
1132 subcases are possible:
1133 * The value was computed completely the last time we were here. This
1134 is the case if there is no loop. We can return the proper value.
1135 * The recursion that visited this node and set the flag did not
1136 return yet. We are computing a value in a loop and need to
1137 break the recursion. This case only happens if we visited
1138 the same block with phi_merge before, which inserted a Phi0.
1139 So we return the Phi0.
1142 /* case 4 -- already visited. */
1143 if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) {
1144 /* As phi_merge allocates a Phi0 this value is always defined. Here
1145 is the critical difference of the two algorithms. */
1146 assert(block->attr.block.graph_arr[pos]);
1147 return block->attr.block.graph_arr[pos];
1150 /* visited the first time */
1151 set_irn_visited(block, get_irg_visited(current_ir_graph));
1153 /* Get the local valid value */
1154 res = block->attr.block.graph_arr[pos];
1156 /* case 2 -- If the value is actually computed, return it. */
1157 if (res) { return res; };
1159 if (block->attr.block.matured) { /* case 3 */
1161 /* The Phi has the same amount of ins as the corresponding block. */
1162 int ins = get_irn_arity(block);
1164 NEW_ARR_A (ir_node *, nin, ins);
1166 /* Phi merge collects the predecessors and then creates a node. */
1167 res = phi_merge (block, pos, mode, nin, ins);
1169 } else { /* case 1 */
1170 /* The block is not mature, we don't know how many in's are needed. A Phi
1171 with zero predecessors is created. Such a Phi node is called Phi0
1172 node. The Phi0 is then added to the list of Phi0 nodes in this block
1173 to be matured by mature_block later.
1174 The Phi0 has to remember the pos of it's internal value. If the real
1175 Phi is computed, pos is used to update the array with the local
1177 res = new_r_Phi0 (current_ir_graph, block, mode);
1178 res->attr.phi0_pos = pos;
1179 res->link = block->link;
1183 /* If we get here, the frontend missed a use-before-definition error */
1186 printf("Error: no value set. Use of undefined variable. Initializing
1188 assert (mode->code >= irm_f && mode->code <= irm_p);
1189 res = new_r_Const (current_ir_graph, block, mode,
1190 tarval_mode_null[mode->code]);
1193 /* The local valid value is available now. */
1194 block->attr.block.graph_arr[pos] = res;
1199 #endif /* USE_FAST_PHI_CONSTRUCTION */
1201 /****************************************************************************/
1203 /** Finalize a Block node, when all control flows are known. */
1204 /** Acceptable parameters are only Block nodes. */
1206 mature_block (ir_node *block)
1213 assert (get_irn_opcode(block) == iro_Block);
1215 if (!get_Block_matured(block)) {
1217 /* turn the dynamic in-array into a static one. */
1218 ins = ARR_LEN (block->in)-1;
1219 NEW_ARR_A (ir_node *, nin, ins);
1221 /* Traverse a chain of Phi nodes attached to this block and mature
1223 for (n = block->link; n; n=next) {
1224 inc_irg_visited(current_ir_graph);
1226 exchange (n, phi_merge (block, n->attr.phi0_pos, n->mode, nin, ins));
1229 block->attr.block.matured = 1;
1231 /* Now, as the block is a finished firm node, we can optimize it.
1232 Since other nodes have been allocated since the block was created
1233 we can not free the node on the obstack. Therefore we have to call
1235 Unfortunately the optimization does not change a lot, as all allocated
1236 nodes refer to the unoptimized node. */
1237 block = optimize_in_place(block);
1243 new_Phi (int arity, ir_node **in, ir_mode *mode)
1245 return new_r_Phi (current_ir_graph, current_ir_graph->current_block,
1250 new_Const (ir_mode *mode, tarval *con)
1252 return new_r_Const (current_ir_graph, current_ir_graph->start_block,
1257 new_Id (ir_node *val, ir_mode *mode)
1259 return new_r_Id (current_ir_graph, current_ir_graph->current_block,
1264 new_Proj (ir_node *arg, ir_mode *mode, long proj)
1266 return new_r_Proj (current_ir_graph, current_ir_graph->current_block,
1271 new_Conv (ir_node *op, ir_mode *mode)
1273 return new_r_Conv (current_ir_graph, current_ir_graph->current_block,
1278 new_Tuple (int arity, ir_node **in)
1280 return new_r_Tuple (current_ir_graph, current_ir_graph->current_block,
1285 new_Add (ir_node *op1, ir_node *op2, ir_mode *mode)
1287 return new_r_Add (current_ir_graph, current_ir_graph->current_block,
1292 new_Sub (ir_node *op1, ir_node *op2, ir_mode *mode)
1294 return new_r_Sub (current_ir_graph, current_ir_graph->current_block,
1300 new_Minus (ir_node *op, ir_mode *mode)
1302 return new_r_Minus (current_ir_graph, current_ir_graph->current_block,
1307 new_Mul (ir_node *op1, ir_node *op2, ir_mode *mode)
1309 return new_r_Mul (current_ir_graph, current_ir_graph->current_block,
1314 new_Quot (ir_node *memop, ir_node *op1, ir_node *op2)
1316 return new_r_Quot (current_ir_graph, current_ir_graph->current_block,
1321 new_DivMod (ir_node *memop, ir_node *op1, ir_node *op2)
1323 return new_r_DivMod (current_ir_graph, current_ir_graph->current_block,
1328 new_Div (ir_node *memop, ir_node *op1, ir_node *op2)
1330 return new_r_Div (current_ir_graph, current_ir_graph->current_block,
1335 new_Mod (ir_node *memop, ir_node *op1, ir_node *op2)
1337 return new_r_Mod (current_ir_graph, current_ir_graph->current_block,
1342 new_And (ir_node *op1, ir_node *op2, ir_mode *mode)
1344 return new_r_And (current_ir_graph, current_ir_graph->current_block,
1349 new_Or (ir_node *op1, ir_node *op2, ir_mode *mode)
1351 return new_r_Or (current_ir_graph, current_ir_graph->current_block,
1356 new_Eor (ir_node *op1, ir_node *op2, ir_mode *mode)
1358 return new_r_Eor (current_ir_graph, current_ir_graph->current_block,
1363 new_Not (ir_node *op, ir_mode *mode)
1365 return new_r_Not (current_ir_graph, current_ir_graph->current_block,
1370 new_Shl (ir_node *op, ir_node *k, ir_mode *mode)
1372 return new_r_Shl (current_ir_graph, current_ir_graph->current_block,
1377 new_Shr (ir_node *op, ir_node *k, ir_mode *mode)
1379 return new_r_Shr (current_ir_graph, current_ir_graph->current_block,
1384 new_Shrs (ir_node *op, ir_node *k, ir_mode *mode)
1386 return new_r_Shrs (current_ir_graph, current_ir_graph->current_block,
1391 new_Rotate (ir_node *op, ir_node *k, ir_mode *mode)
1393 return new_r_Rot (current_ir_graph, current_ir_graph->current_block,
1398 new_Abs (ir_node *op, ir_mode *mode)
1400 return new_r_Abs (current_ir_graph, current_ir_graph->current_block,
1405 new_Cmp (ir_node *op1, ir_node *op2)
1407 return new_r_Cmp (current_ir_graph, current_ir_graph->current_block,
1414 return new_r_Jmp (current_ir_graph, current_ir_graph->current_block);
1418 new_Cond (ir_node *c)
1420 return new_r_Cond (current_ir_graph, current_ir_graph->current_block, c);
1424 new_Call (ir_node *store, ir_node *callee, int arity, ir_node **in,
1427 return new_r_Call (current_ir_graph, current_ir_graph->current_block,
1428 store, callee, arity, in, type);
1432 new_Return (ir_node* store, int arity, ir_node **in)
1434 return new_r_Return (current_ir_graph, current_ir_graph->current_block,
1439 new_Raise (ir_node *store, ir_node *obj)
1441 return new_r_Raise (current_ir_graph, current_ir_graph->current_block,
1446 new_Load (ir_node *store, ir_node *addr)
1448 return new_r_Load (current_ir_graph, current_ir_graph->current_block,
1453 new_Store (ir_node *store, ir_node *addr, ir_node *val)
1455 return new_r_Store (current_ir_graph, current_ir_graph->current_block,
1460 new_Alloc (ir_node *store, ir_node *size, type *alloc_type,
1463 return new_r_Alloc (current_ir_graph, current_ir_graph->current_block,
1464 store, size, alloc_type, where);
1468 new_Free (ir_node *store, ir_node *ptr, ir_node *size, type *free_type)
1470 return new_r_Free (current_ir_graph, current_ir_graph->current_block,
1471 store, ptr, size, free_type);
1475 new_simpleSel (ir_node *store, ir_node *objptr, entity *ent)
1476 /* GL: objptr was called frame before. Frame was a bad choice for the name
1477 as the operand could as well be a pointer to a dynamic object. */
1479 return new_r_Sel (current_ir_graph, current_ir_graph->current_block,
1480 store, objptr, 0, NULL, ent);
1484 new_Sel (ir_node *store, ir_node *objptr, int n_index, ir_node **index, entity *sel)
1486 return new_r_Sel (current_ir_graph, current_ir_graph->current_block,
1487 store, objptr, n_index, index, sel);
1491 new_SymConst (type_or_id_p value, symconst_kind kind)
1493 return new_r_SymConst (current_ir_graph, current_ir_graph->current_block,
1498 new_Sync (int arity, ir_node** in)
1500 return new_r_Sync (current_ir_graph, current_ir_graph->current_block,
1508 return current_ir_graph->bad;
1511 /*************************************************************************/
1512 /* Comfortable interface with automatic Phi node construction. */
1513 /* (Uses also constructors of ?? interface, except new_Block. */
1514 /*************************************************************************/
1516 /** Block construction **/
1517 /* immature Block without predecessors */
1518 ir_node *new_immBlock (void) {
1521 /* creates a new dynamic in-array as length of in is -1 */
1522 res = new_ir_node (current_ir_graph, NULL, op_Block, mode_R, -1, NULL);
1523 current_ir_graph->current_block = res;
1524 res->attr.block.matured = 0;
1525 set_Block_block_visited(res, 0);
1527 /* Create and initialize array for Phi-node construction. */
1528 res->attr.block.graph_arr = NEW_ARR_D (ir_node *, current_ir_graph->obst,
1529 current_ir_graph->n_loc);
1530 memset(res->attr.block.graph_arr, 0, sizeof(ir_node *)*current_ir_graph->n_loc);
1532 /* Immature block may not be optimized! */
1538 /* add an adge to a jmp/control flow node */
1540 add_in_edge (ir_node *block, ir_node *jmp)
1542 if (block->attr.block.matured) {
1543 printf("Error: Block already matured!\n");
1546 assert (jmp != NULL);
1547 ARR_APP1 (ir_node *, block->in, jmp);
1551 /* changing the current block */
1553 switch_block (ir_node *target)
1555 current_ir_graph->current_block = target;
1558 /****************************/
1559 /* parameter administration */
1561 /* get a value from the parameter array from the current block by its index */
1563 get_value (int pos, ir_mode *mode)
1565 inc_irg_visited(current_ir_graph);
1566 return get_r_value_internal (current_ir_graph->current_block, pos + 1, mode);
1569 /* set a value at position pos in the parameter array from the current block */
1571 set_value (int pos, ir_node *value)
1573 current_ir_graph->current_block->attr.block.graph_arr[pos + 1] = value;
1576 /* get the current store */
1580 /* GL: one could call get_value instead */
1581 inc_irg_visited(current_ir_graph);
1582 return get_r_value_internal (current_ir_graph->current_block, 0, mode_M);
1585 /* set the current store */
1587 set_store (ir_node *store)
1589 /* GL: one could call set_value instead */
1590 current_ir_graph->current_block->attr.block.graph_arr[0] = store;
1593 /*************************************************************************/
1596 /* call once for each run of the library */