- 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 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_rd_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_rd_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_immBlock (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",
- get_id_str(block->attr.block.graph_arr[pos]->op->name)); */
- }
-
- return res;
-}
-
-/* This function returns the last definition of a variable. In case
- this variable was last defined in a previous block, Phi nodes are
- inserted. If the part of the firm graph containing the definition
- is not yet constructed, a dummy Phi node is returned. */
-static ir_node *
-get_r_value_internal (ir_node *block, int pos, ir_mode *mode)
-{
- ir_node *res;
- /* There are 4 cases to treat.
-
- 1. The block is not mature and we visit it the first time. We can not
- create a proper Phi node, therefore a Phi0, i.e., a Phi without
- predecessors is returned. This node is added to the linked list (field
- "link") of the containing block to be completed when this block is
- matured. (Completion will add a new Phi and turn the Phi0 into an Id
- node.)
-
- 2. The value is already known in this block, graph_arr[pos] is set and we
- visit the block the first time. We can return the value without
- creating any new nodes.
-
- 3. The block is mature and we visit it the first time. A Phi node needs
- to be created (phi_merge). If the Phi is not needed, as all it's
- operands are the same value reaching the block through different
- paths, it's optimized away and the value itself is returned.
-
- 4. The block is mature, and we visit it the second time. Now two
- subcases are possible:
- * The value was computed completely the last time we were here. This
- is the case if there is no loop. We can return the proper value.
- * The recursion that visited this node and set the flag did not
- return yet. We are computing a value in a loop and need to
- break the recursion without knowing the result yet.
- @@@ strange case. Straight forward we would create a Phi before
- starting the computation of it's predecessors. In this case we will
- find a Phi here in any case. The problem is that this implementation
- only creates a Phi after computing the predecessors, so that it is
- hard to compute self references of this Phi. @@@
- There is no simple check for the second subcase. Therefore we check
- for a second visit and treat all such cases as the second subcase.
- Anyways, the basic situation is the same: we reached a block
- on two paths without finding a definition of the value: No Phi
- nodes are needed on both paths.
- We return this information "Two paths, no Phi needed" by a very tricky
- implementation that relies on the fact that an obstack is a stack and
- will return a node with the same address on different allocations.
- Look also at phi_merge and new_rd_phi_in to understand this.
- @@@ Unfortunately this does not work, see testprogram
- three_cfpred_example.
-
- */
-
- /* case 4 -- already visited. */
- if (get_irn_visited(block) == get_irg_visited(current_ir_graph)) return NULL;
-
- /* visited the first time */
- set_irn_visited(block, get_irg_visited(current_ir_graph));
-
- /* Get the local valid value */
- res = block->attr.block.graph_arr[pos];
-
- /* case 2 -- If the value is actually computed, return it. */
- if (res) return res;
-
- if (block->attr.block.matured) { /* case 3 */
-
- /* The Phi has the same amount of ins as the corresponding block. */
- int ins = get_irn_arity(block);
- ir_node **nin;
- NEW_ARR_A (ir_node *, nin, ins);
-
- /* Phi merge collects the predecessors and then creates a node. */
- res = phi_merge (block, pos, mode, nin, ins);
-
- } else { /* case 1 */
- /* The block is not mature, we don't know how many in's are needed. A Phi
- with zero predecessors is created. Such a Phi node is called Phi0
- node. (There is also an obsolete Phi0 opcode.) The Phi0 is then added
- to the list of Phi0 nodes in this block to be matured by mature_immBlock
- later.
- The Phi0 has to remember the pos of it's internal value. If the real
- Phi is computed, pos is used to update the array with the local
- values. */
-
- res = new_rd_Phi0 (current_ir_graph, block, mode);
- res->attr.phi0_pos = pos;
- res->link = block->link;
- block->link = res;
- }
-
- /* If we get here, the frontend missed a use-before-definition error */
- if (!res) {
- /* Error Message */
- printf("Error: no value set. Use of undefined variable. Initializing to zero.\n");
- assert (mode->code >= irm_F && mode->code <= irm_P);
- res = new_rd_Const (NULL, current_ir_graph, block, mode,
- tarval_mode_null[mode->code]);
- }
-
- /* The local valid value is available now. */
- block->attr.block.graph_arr[pos] = res;
-
- return res;
-}
-
-#else /* if 0 */
-
-/**
- it starts the recursion. This causes an Id at the entry of
- every block that has no definition of the value! **/
-
-#if USE_EXPLICIT_PHI_IN_STACK
-/* Just dummies */
-Phi_in_stack * new_Phi_in_stack() { return NULL; }
-void free_Phi_in_stack(Phi_in_stack *s) { }
-#endif
-