-/* Inserts phi nodes for all variables marked lower_to_ssa
- *
- * This is the same algorithm as presented in "Efficiently Computing Static
- * Single Assignment Form and the Control Dependence Graph" by Cytron et.
- * al.
- */
-static void
-insert_phi_nodes(struct lower_variables_state *state)
-{
- NIR_VLA_ZERO(unsigned, work, state->impl->num_blocks);
- NIR_VLA_ZERO(unsigned, has_already, state->impl->num_blocks);
-
- /*
- * Since the work flags already prevent us from inserting a node that has
- * ever been inserted into W, we don't need to use a set to represent W.
- * Also, since no block can ever be inserted into W more than once, we know
- * that the maximum size of W is the number of basic blocks in the
- * function. So all we need to handle W is an array and a pointer to the
- * next element to be inserted and the next element to be removed.
- */
- NIR_VLA(nir_block *, W, state->impl->num_blocks);
-
- unsigned w_start, w_end;
- unsigned iter_count = 0;
-
- foreach_list_typed(struct deref_node, node, direct_derefs_link,
- &state->direct_deref_nodes) {
- if (node->stores == NULL)
- continue;
-
- if (!node->lower_to_ssa)
- continue;
-
- w_start = w_end = 0;
- iter_count++;
-
- struct set_entry *store_entry;
- set_foreach(node->stores, store_entry) {
- nir_intrinsic_instr *store = (nir_intrinsic_instr *)store_entry->key;
- if (work[store->instr.block->index] < iter_count)
- W[w_end++] = store->instr.block;
- work[store->instr.block->index] = iter_count;
- }
-
- while (w_start != w_end) {
- nir_block *cur = W[w_start++];
- struct set_entry *dom_entry;
- set_foreach(cur->dom_frontier, dom_entry) {
- nir_block *next = (nir_block *) dom_entry->key;
-
- /*
- * If there's more than one return statement, then the end block
- * can be a join point for some definitions. However, there are
- * no instructions in the end block, so nothing would use those
- * phi nodes. Of course, we couldn't place those phi nodes
- * anyways due to the restriction of having no instructions in the
- * end block...
- */
- if (next == state->impl->end_block)
- continue;
-
- if (has_already[next->index] < iter_count) {
- nir_phi_instr *phi = nir_phi_instr_create(state->shader);
- nir_ssa_dest_init(&phi->instr, &phi->dest,
- glsl_get_vector_elements(node->type), NULL);
- nir_instr_insert_before_block(next, &phi->instr);
-
- _mesa_hash_table_insert(state->phi_table, phi, node);
-
- has_already[next->index] = iter_count;
- if (work[next->index] < iter_count) {
- work[next->index] = iter_count;
- W[w_end++] = next;
- }
- }
- }
- }
- }
-}
-
-