+/**
+ * Map a block to the phi[block->input] live-trough.
+ */
+static void *live_throughs(const block_t *bl, const ir_node *phi)
+{
+ ir_node *input = get_Phi_pred(phi, bl->meet_input);
+
+ /* If this input is inside our block, this
+ is a live-out and not a live trough.
+ Live-outs are tested inside propagate, so map all of
+ them to the "general" value NULL */
+ if (get_nodes_block(input) == bl->block)
+ return NULL;
+ return input;
+} /* live_throughs */
+
+/**
+ * Split partition by live-outs and live-troughs.
+ *
+ * @param part the partition
+ * @param env the environment
+ */
+static void propagate_blocks_live_troughs(partition_t *part, environment_t *env)
+{
+ const ir_node *meet_block = part->meet_block;
+ block_t *bl, *next;
+ listmap_t map;
+ listmap_entry_t *iter;
+ const ir_node *phi;
+
+ DB((dbg, LEVEL_2, " Propagate live-troughs on part%u\n", part->nr));
+
+ for (phi = get_Block_phis(meet_block); phi != NULL; phi = get_Phi_next(phi)) {
+ /* propagate on all Phis of the meet-block */
+
+ if (part->n_blocks < 2) {
+ /* zero or one block left, kill this partition */
+ list_del(&part->part_list);
+ DB((dbg, LEVEL_2, " Partition %u contains less than 2 blocks, killed\n", part->nr));
+ return;
+ }
+
+ /* Let map be an empty mapping from the range of live-troughs to (local) list of blocks. */
+ listmap_init(&map);
+ list_for_each_entry_safe(block_t, bl, next, &part->blocks, block_list) {
+ opcode_key_t *id;
+ listmap_entry_t *entry;
+
+ /* Add bl to map[live_trough(bl)]. */
+ id = (opcode_key_t*)live_throughs(bl, phi);
+ entry = listmap_find(&map, id);
+ bl->next = entry->list;
+ entry->list = bl;
+ }
+
+ /* for all sets S except one in the range of map do */
+ for (iter = map.values; iter != NULL; iter = iter->next) {
+ block_t *S;
+
+ if (iter->next == NULL) {
+ /* this is the last entry, ignore */
+ break;
+ }
+ S = iter->list;
+
+ /* Add SPLIT( X, S ) to P. */
+ split(part, S, env);
+ }
+ listmap_term(&map);
+ }
+} /* propagate_blocks_live_troughs */
+
+/**
+ * Propagate live-troughs on all partitions on the partition list.
+ *
+ * @param env the environment
+ */
+static void propagate_live_troughs(environment_t *env)
+{
+ partition_t *part, *next;
+
+ list_for_each_entry_safe(partition_t, part, next, &env->partitions, part_list) {
+ propagate_blocks_live_troughs(part, env);
+ }
+} /* propagate_live_troughs */
+