2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Replaces Mux nodes with control-flow
18 #include "irgraph_t.h"
24 typedef struct walk_env {
25 lower_mux_callback *cb_func;
29 static void find_mux_nodes(ir_node *mux, void *ctx)
31 walk_env_t *env = (walk_env_t*)ctx;
33 /* Skip non-mux nodes. */
37 /* Skip nodes, depending on the callback function. */
38 if (env->cb_func != NULL && !env->cb_func(mux)) {
43 ARR_APP1(ir_node*, env->muxes, mux);
46 static void lower_mux_node(ir_node* mux)
55 ir_node *mux_values[2];
59 irg = get_irn_irg(mux);
61 /* Split the block in two halfs, with the mux in the upper block. */
62 lower_block = get_nodes_block(mux);
63 assert(lower_block != 0);
65 upper_block = get_nodes_block(mux);
67 /* Create a cond node with two projs and a phi as mux replacement. The
68 * true proj jumps directly to the lower block, the false proj uses a
69 * block in-between, so that the phi can be used to select the result
70 * value from the old mux node in the lower block. */
71 cond = new_r_Cond(upper_block, get_Mux_sel(mux));
72 trueProj = new_r_Proj(cond, mode_X, pn_Cond_true);
73 falseProj = new_r_Proj(cond, mode_X, pn_Cond_false);
74 falseBlock = new_r_Block(irg, 1, &falseProj);
75 mux_jmps[0] = trueProj;
76 mux_jmps[1] = new_r_Jmp(falseBlock);
78 /* Kill the jump from upper to lower block and replace the in array. */
79 assert(get_Block_n_cfgpreds(lower_block) == 1);
80 kill_node(get_Block_cfgpred(lower_block, 0));
81 set_irn_in(lower_block, 2, mux_jmps);
83 /* Combine the two control flows with a phi to select the correct value
84 * and use it to replace the mux. */
85 mux_values[0] = get_Mux_true(mux);
86 mux_values[1] = get_Mux_false(mux);
87 phi = new_r_Phi(lower_block, 2, mux_values, get_irn_mode(mux));
90 /* Add links and update phi node lists, for the next part_block() call.
91 * lower_block and upper_block have been updated by part_block(). Link
92 * the projs with the cond. */
93 set_irn_link(trueProj, get_irn_link(cond));
94 set_irn_link(falseProj, trueProj);
95 set_irn_link(cond, falseProj);
97 add_Block_phi(lower_block, phi);
100 void lower_mux(ir_graph *irg, lower_mux_callback *cb_func)
105 /* Scan the graph for mux nodes to lower. */
106 env.cb_func = cb_func;
107 env.muxes = NEW_ARR_F(ir_node*, 0);
108 irg_walk_graph(irg, find_mux_nodes, 0, &env);
110 n_muxes = ARR_LEN(env.muxes);
112 ir_resources_t resources = IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST;
114 /* This is required by part_block() later. */
115 ir_reserve_resources(irg, resources);
116 collect_phiprojs(irg);
118 for (i = 0; i < n_muxes; ++i) {
119 lower_mux_node(env.muxes[i]);
122 /* Cleanup, verify the graph. */
123 ir_free_resources(irg, resources);
125 clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE);
127 DEL_ARR_F(env.muxes);
130 typedef struct pass_t {
131 ir_graph_pass_t pass;
132 lower_mux_callback *cb_func;
136 * Wrapper to run ir_lower_mux() as an ir_graph pass
138 static int pass_wrapper(ir_graph *irg, void *context)
140 pass_t *pass = (pass_t*)context;
142 lower_mux(irg, pass->cb_func);
146 ir_graph_pass_t *lower_mux_pass(const char *name, lower_mux_callback *cb_func)
148 pass_t *pass = XMALLOCZ(pass_t);
150 pass->cb_func = cb_func;
151 return def_graph_pass_constructor(
152 &pass->pass, name ? name : "lower_mux", pass_wrapper);