+ * Gets result of nodes phi translation into block.
+ *
+ * @param node the node
+ * @param block the target block
+ *
+ * @return a phi translation of node node into block block or NULL
+ */
+static ir_node *get_translated(ir_node *node, ir_node *block)
+{
+ block_info *bi;
+ ir_node *trans;
+
+ if (is_irn_constlike(node))
+ return node;
+
+ bi = get_block_info(block);
+ trans = ir_nodehashmap_get(ir_node, bi->trans, node);
+ return trans;
+}
+
+/**
+ * Saves result of phi translation of node into predecessor
+ * at pos of block succ.
+ *
+ * @param node the node
+ * @param succ the successor of the translation target block
+ * @param pos the position of the predecessor block
+ * @param trans the translation result
+ *
+ */
+static void set_translated(ir_node *node, ir_node *succ, int pos, ir_node *trans)
+{
+ ir_node *pred = get_Block_cfgpred_block(succ, pos);
+ block_info *bi = get_block_info(pred);
+
+ ir_nodehashmap_insert(bi->trans, node, trans);
+}
+
+/**
+ * Checks if a node node is clean in block block for use in antic_in.
+ *
+ * A clean node in block block can be hoisted above block block.
+ * A node is not clean if its value is killed in block block.
+ * The node can still be hoisted into block block.
+ *
+ * @param n the phi translated or not translated node
+ * @param block the block
+ * @return non-zero value for clean node
+ */
+static int is_clean_in_block_antic(ir_node *node, ir_node *block)
+{
+ int i;
+
+ if (get_irn_mode(node) == mode_M)
+ return 0;
+
+ /* a phi only has predecessors in other blocks */
+ if (is_Phi(node))
+ return 1;
+
+ /* constants are in start block */
+ if (is_irn_constlike(node))
+ return 1;
+
+ /* what we really want to check
+ Only for node is translated case; other are clean anyway */
+ if (! is_nice_value(node)) {
+ return 0;
+ }
+
+ /* cleanliness depends on nodes predecessors
+ At least if node is translated. */
+ for (i = get_irn_arity(node) - 1; i >= 0; --i) {
+ ir_node *pred = get_irn_n(node, i);
+ ir_node *trans;
+ ir_node *value;
+
+ if (is_irn_constlike(pred))
+ continue;
+
+ /* exp_gen only contains clean nodes */
+ if (ir_valueset_lookup(get_block_info(block)->exp_gen, pred))
+ continue;
+
+ /* block of pred strictly dominates target block. pred irrelevant. */
+ if (block_strictly_dominates(get_nodes_block(pred), block))
+ continue;
+
+ /* --- pred neither in block, nor dominating -- */
+
+ /* This pred is in antic_in and such clean.
+ Not every clean pred is in antic_in though.
+ Predecessor might be translated or not */
+ value = identify(pred);
+ if (ir_valueset_lookup(get_block_info(block)->antic_in, value))
+ continue;
+
+ /* This check is not redundant for translated nodes;
+ non translated ones are already nice. */
+ if (! is_nice_value(pred)) {
+ DB((dbg, LEVEL_5, "unclean %+F because pred %+F not nice\n", node, pred));
+ return 0;
+ }
+
+ /* predecessor is not translated. This is legal if
+ predecessor is dominating or in target block (already checked). */
+ trans = get_translated(pred, block);
+ if (trans == NULL) {
+ DB((dbg, LEVEL_5, "unclean %+F because pred %+F unclean (not translated)\n", node, pred));
+ return 0;
+
+ } else {
+ /* Node and predecessor are translated, but is pred clean?
+ The value of the translated predecessor has to be in antic_in. */
+ ir_node *value = identify(trans);
+ if (! ir_valueset_lookup(get_block_info(block)->antic_in, value)) {
+ DB((dbg, LEVEL_5, "unclean %+F because pred %+F value %+F not antic\n", node, pred, value));
+ return 0;
+ }
+ }
+
+ assert(0 && "should have been catched");
+ }
+
+ /* clean */
+ return 1;
+} /* is_clean_in_block */
+
+/**
+ * Checks if a node n is clean in block block for exp_gen.
+ *
+ * @param n the node
+ * @param block the block
+ * @return non-zero value for clean node
+ */
+static int is_clean_in_block_expgen(ir_node *n, ir_node *block)
+{
+ int i;
+
+ if (get_irn_mode(n) == mode_M)
+ return 0;
+
+ if (is_Phi(n))
+ return 1;
+
+ if (! is_nice_value(n))
+ return 0;
+
+ for (i = get_irn_arity(n) - 1; i >= 0; --i) {
+ ir_node *pred = get_irn_n(n, i);
+
+ /* sufficient for exp_gen because block is always block of node */
+ if (get_nodes_block(pred) != block)
+ continue;
+
+ /* pred is in block,
+ so it needs to be clean (already in exp_gen) */
+ if (! get_irn_link(pred)) {
+ DB((dbg, LEVEL_5, "unclean %+F because pred %+F unclean\n", n, pred));
+ return 0;
+ } else {
+ continue;
+ }
+ }
+ return 1;
+} /* is_clean_in_block */
+
+/**
+ * Does blocklocal common subexpression elimination (CSE).
+ *
+ * @param irn the node
+ * @param ctx the environment
+ */
+static void cse_walker(ir_node *irn, void *ctx)
+{
+ ir_node *opt = identify_remember(irn);
+ (void) ctx;
+
+ if (opt != irn) {
+ DB((dbg, LEVEL_5, "CSE %+F to %+F\n", irn, opt));
+ exchange(irn, opt);
+ }
+}
+
+/**
+ * Bottom up walker that ensures that every block gets a block info.
+ *
+ * @param irn the node
+ * @param ctx the environment
+ */
+static void block_info_walker(ir_node *irn, void *ctx)
+{
+ if (is_Block(irn)) {
+ pre_env *env = (pre_env*)ctx;
+ alloc_block_info(irn, env);
+ }
+}
+
+/**
+ * Topological walker puts nodes in top-down topological order into exp_gen set.
+ *
+ * @param irn the node
+ * @param ctx the environment