+ current_ir_graph->n_loc);
+ memset(res->attr.block.graph_arr, 0, sizeof(ir_node *)*current_ir_graph->n_loc);
+
+ res = optimize (res);
+ irn_vrfy (res);
+
+ return res;
+}
+#else
+ir_node *
+new_Block (void)
+{
+ return new_immBlock();
+}
+#endif
+
+/*************************************************************************/
+/* Methods necessary for automatic Phi node creation */
+/*
+ ir_node *phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
+ ir_node *get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
+ ir_node *new_r_Phi0 (ir_graph *irg, ir_node *block, ir_mode *mode)
+ ir_node *new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode, ir_node **in, int ins)
+
+ Call Graph: ( A ---> B == A "calls" B)
+
+ get_value mature_block
+ | |
+ | |
+ | |
+ | ---> phi_merge
+ | / / \
+ | / / \
+ \|/ / |/_ \
+ get_r_value_internal |
+ | |
+ | |
+ \|/ \|/
+ new_r_Phi0 new_r_Phi_in
+
+*****************************************************************************/
+
+/* Creates a Phi node with 0 predecessors */
+inline ir_node *
+new_r_Phi0 (ir_graph *irg, ir_node *block, ir_mode *mode)
+{
+ ir_node *res;
+ res = new_ir_node (irg, block, op_Phi, mode, 0, NULL);
+ irn_vrfy (res);
+ return res;
+}
+
+/* There are two implementations of the Phi node construction. The first
+ is faster, but does not work for blocks with more than 2 predecessors.
+ The second works always but is slower and causes more unnecessary Phi
+ nodes.
+ Select the implementations by the following preprocessor flag set in
+ common/common.h: */
+#if USE_FAST_PHI_CONSTRUCTION
+
+/* This is a stack used for allocating and deallocating nodes in
+ new_r_Phi_in. The original implementation used the obstack
+ to model this stack, now it is explicit. This reduces side effects.
+*/
+#if USE_EXPICIT_PHI_IN_STACK
+Phi_in_stack *
+new_Phi_in_stack() {
+ Phi_in_stack *res;
+
+ res = (Phi_in_stack *) malloc ( sizeof (Phi_in_stack));
+
+ res->stack = NEW_ARR_F (ir_node *, 1);
+ res->pos = 0;
+
+ return res;
+}
+
+void free_to_Phi_in_stack(ir_node *phi) {
+ assert(get_irn_opcode(phi) == iro_Phi);
+
+ if (ARR_LEN(current_ir_graph->Phi_in_stack->stack) ==
+ current_ir_graph->Phi_in_stack->pos)
+ ARR_APP1 (ir_node *, current_ir_graph->Phi_in_stack->stack, phi);
+ else
+ current_ir_graph->Phi_in_stack->stack[current_ir_graph->Phi_in_stack->pos] = phi;
+
+ (current_ir_graph->Phi_in_stack->pos)++;
+}
+
+ir_node *
+alloc_or_pop_from_Phi_in_stack(ir_graph *irg, ir_node *block, ir_mode *mode,
+ int arity, ir_node **in) {
+ ir_node *res;
+ ir_node **stack = current_ir_graph->Phi_in_stack->stack;
+ int pos = current_ir_graph->Phi_in_stack->pos;
+
+
+ if (pos == 0) {
+ /* We need to allocate a new node */
+ res = new_ir_node (irg, block, op_Phi, mode, arity, in);
+ } else {
+ /* reuse the old node and initialize it again. */
+ res = stack[pos-1];
+
+ assert (res->kind == k_ir_node);
+ assert (res->op == op_Phi);
+ res->mode = mode;
+ res->visited = 0;
+ res->link = NULL;
+ assert (arity >= 0);
+ /* ???!!! How to free the old in array?? */
+ res->in = NEW_ARR_D (ir_node *, irg->obst, (arity+1));
+ res->in[0] = block;
+ memcpy (&res->in[1], in, sizeof (ir_node *) * arity);
+
+ (current_ir_graph->Phi_in_stack->pos)--;
+ }
+ return res;
+}
+#endif /* USE_EXPICIT_PHI_IN_STACK */
+
+/* Creates a Phi node with a given, fixed array **in of predecessors.
+ If the Phi node is unnecessary, as the same value reaches the block
+ through all control flow paths, it is eliminated and the value
+ returned directly. This constructor is only intended for use in
+ the automatic Phi node generation triggered by get_value or mature.
+ The implementation is quite tricky and depends on the fact, that
+ the nodes are allocated on a stack:
+ The in array contains predecessors and NULLs. The NULLs appear,
+ if get_r_value_internal, that computed the predecessors, reached
+ the same block on two paths. In this case the same value reaches
+ this block on both paths, there is no definition in between. We need
+ not allocate a Phi where these path's merge, but we have to communicate
+ this fact to the caller. This happens by returning a pointer to the
+ node the caller _will_ allocate. (Yes, we predict the address. We can
+ do so because the nodes are allocated on the obstack.) The caller then
+ finds a pointer to itself and, when this routine is called again,
+ eliminates itself.
+ */
+inline ir_node *
+new_r_Phi_in (ir_graph *irg, ir_node *block, ir_mode *mode,
+ ir_node **in, int ins)
+{
+ int i;
+ ir_node *res, *known;
+
+ /* allocate a new node on the obstack.
+ This can return a node to which some of the pointers in the in-array
+ already point.
+ Attention: the constructor copies the in array, i.e., the later changes
+ to the array in this routine do not affect the constructed node! If
+ the in array contains NULLs, there will be missing predecessors in the
+ returned node.
+ Is this a possible internal state of the Phi node generation? */
+#if USE_EXPICIT_PHI_IN_STACK
+ res = known = alloc_or_pop_from_Phi_in_stack(irg, block, mode, ins, in);
+#else
+ res = known = new_ir_node (irg, block, op_Phi, mode, ins, in);
+#endif
+ /* The in-array can contain NULLs. These were returned by
+ get_r_value_internal if it reached the same block/definition on a
+ second path.
+ The NULLs are replaced by the node itself to simplify the test in the
+ next loop. */
+ for (i=0; i < ins; ++i)
+ if (in[i] == NULL) in[i] = res;
+
+ /* This loop checks whether the Phi has more than one predecessor.
+ If so, it is a real Phi node and we break the loop. Else the
+ Phi node merges the same definition on several paths and therefore
+ is not needed. */
+ for (i=0; i < ins; ++i)
+ {
+ if (in[i]==res || in[i]==known) continue;
+
+ if (known==res)
+ known = in[i];
+ else
+ break;
+ }
+
+ /* i==ins: there is at most one predecessor, we don't need a phi node. */
+ if (i==ins) {
+#if USE_EXPICIT_PHI_IN_STACK
+ free_to_Phi_in_stack(res);
+#else
+ obstack_free (current_ir_graph->obst, res);
+#endif
+ res = known;
+ } else {
+ res = optimize (res);
+ irn_vrfy (res);
+ }
+
+ /* return the pointer to the Phi node. This node might be deallocated! */
+ return res;
+}
+
+inline ir_node *
+get_r_value_internal (ir_node *block, int pos, ir_mode *mode);
+
+/** This function computes the predecessors for a real Phi node, and then
+ allocates and returns this node. The routine called to allocate the
+ node might optimize it away and return a real value, or even a pointer
+ to a deallocated Phi node on top of the obstack!
+ This function is called with an in-array of proper size. **/
+static inline ir_node *
+phi_merge (ir_node *block, int pos, ir_mode *mode, ir_node **nin, int ins)
+{
+ ir_node *prevBlock, *res;
+ int i;
+
+ /* This loop goes to all predecessor blocks of the block the Phi node is in
+ and there finds the operands of the Phi node by calling
+ get_r_value_internal. */
+ for (i = 1; i <= ins; ++i) {
+ assert (block->in[i]);
+ prevBlock = block->in[i]->in[0]; /* go past control flow op to prev block */
+ assert (prevBlock);
+ nin[i-1] = get_r_value_internal (prevBlock, pos, mode);
+ }
+
+ /* After collecting all predecessors into the array nin a new Phi node
+ with these predecessors is created. This constructor contains an
+ optimization: If all predecessors of the Phi node are identical it
+ returns the only operand instead of a new Phi node. If the value
+ passes two different control flow edges without being defined, and
+ this is the second path treated, a pointer to the node that will be
+ allocated for the first path (recursion) is returned. We already
+ know the address of this node, as it is the next node to be allocated
+ and will be placed on top of the obstack. (The obstack is a _stack_!) */
+ res = new_r_Phi_in (current_ir_graph, block, mode, nin, ins);
+
+ /* Now we now the value for "pos" and can enter it in the array with
+ all known local variables. Attention: this might be a pointer to
+ a node, that later will be allocated!!! See new_r_Phi_in.
+ If this is called in mature, after some set_value in the same block,
+ the proper value must not be overwritten:
+ The call order
+ get_value (makes Phi0, put's it into graph_arr)
+ set_value (overwrites Phi0 in graph_arr)
+ mature_block (upgrades Phi0, puts it again into graph_arr, overwriting
+ the proper value.)
+ fails. */
+ if (!block->attr.block.graph_arr[pos]) {
+ block->attr.block.graph_arr[pos] = res;
+ } else {
+ /* printf(" value already computed by %s\n",
+ id_to_str(block->attr.block.graph_arr[pos]->op->name)); */
+ }
+
+ return res;
+}