nsz Git - libfirm/blob - ir/lower/lower_mux.c

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief   Replaces Mux nodes with control-flow
  23  * @author  Olaf Liebe
  24  * @version $Id$
  25  */
  26 #include "config.h"
  27
  28 #include <assert.h>
  29
  30 #include "lowering.h"
  31 #include "array.h"
  32 #include "irnode_t.h"
  33 #include "irgraph_t.h"
  34 #include "irgwalk.h"
  35 #include "irgmod.h"
  36 #include "ircons.h"
  37 #include "irvrfy.h"
  38 #include "irpass_t.h"
  39
  40 typedef struct walk_env {
  41         lower_mux_callback *cb_func;
  42         ir_node            **muxes;
  43 } walk_env_t;
  44
  45 static void find_mux_nodes(ir_node *mux, void *ctx)
  46 {
  47         walk_env_t *env = ctx;
  48
  49         /* Skip non-mux nodes. */
  50         if (!is_Mux(mux))
  51                 return;
  52
  53         /* Skip nodes, depending on the callback function. */
  54         if (env->cb_func != NULL && !env->cb_func(mux)) {
  55                 return;
  56         }
  57
  58         /* Store the node. */
  59         ARR_APP1(ir_node*, env->muxes, mux);
  60 }
  61
  62 static void lower_mux_node(ir_node* mux)
  63 {
  64         ir_node  *upper_block;
  65         ir_node  *lower_block;
  66         ir_node  *cond;
  67         ir_node  *trueProj;
  68         ir_node  *falseProj;
  69         ir_node  *falseBlock;
  70         ir_node  *mux_jmps[2];
  71         ir_node  *mux_values[2];
  72         ir_node  *phi;
  73         ir_graph *irg;
  74
  75         irg = get_irn_irg(mux);
  76
  77         /* Split the block in two halfs, with the mux in the upper block. */
  78         lower_block = get_nodes_block(mux);
  79         assert(lower_block != 0);
  80         part_block(mux);
  81         upper_block = get_nodes_block(mux);
  82
  83         /* Create a cond node with two projs and a phi as mux replacement. The
  84          * true proj jumps directly to the lower block, the false proj uses a
  85          * block in-between, so that the phi can be used to select the result
  86          * value from the old mux node in the lower block. */
  87         cond        = new_r_Cond(upper_block, get_Mux_sel(mux));
  88         trueProj    = new_r_Proj(upper_block, cond, mode_X, pn_Cond_true);
  89         falseProj   = new_r_Proj(upper_block, cond, mode_X, pn_Cond_false);
  90         falseBlock  = new_r_Block(irg, 1, &falseProj);
  91         mux_jmps[0] = trueProj;
  92         mux_jmps[1] = new_r_Jmp(falseBlock);
  93
  94         /* Kill the jump from upper to lower block and replace the in array. */
  95         assert(get_Block_n_cfgpreds(lower_block) == 1);
  96         kill_node(get_Block_cfgpred(lower_block, 0));
  97         set_irn_in(lower_block, 2, mux_jmps);
  98
  99         /* Combine the two control flows with a phi to select the correct value
 100          * and use it to replace the mux. */
 101         mux_values[0] = get_Mux_true(mux);
 102         mux_values[1] = get_Mux_false(mux);
 103         phi = new_r_Phi(lower_block, 2, mux_values, get_irn_mode(mux));
 104         exchange(mux, phi);
 105
 106         /* Add links and update phi node lists, for the next part_block() call.
 107          * lower_block and upper_block have been updated by part_block(). Link
 108          * the projs with the cond. */
 109         set_irn_link(trueProj,   get_irn_link(cond));
 110         set_irn_link(falseProj,  trueProj);
 111         set_irn_link(cond,       falseProj);
 112
 113         add_Block_phi(lower_block, phi);
 114 }
 115
 116 void lower_mux(ir_graph *irg, lower_mux_callback *cb_func)
 117 {
 118         int        i, n_muxes;
 119         walk_env_t env;
 120
 121         /* Scan the graph for mux nodes to lower. */
 122         env.cb_func = cb_func;
 123         env.muxes   = NEW_ARR_F(ir_node*, 0);
 124         irg_walk_graph(irg, find_mux_nodes, 0, &env);
 125
 126         n_muxes = ARR_LEN(env.muxes);
 127         if (n_muxes > 0) {
 128                 ir_resources_t resources = IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST;
 129
 130                 /* This is required by part_block() later. */
 131                 ir_reserve_resources(irg, resources);
 132                 collect_phiprojs(irg);
 133
 134                 for (i = 0; i < n_muxes; ++i) {
 135                         lower_mux_node(env.muxes[i]);
 136                 }
 137
 138                 /* Cleanup, verify the graph. */
 139                 ir_free_resources(irg, resources);
 140
 141                 set_irg_outs_inconsistent(irg);
 142                 set_irg_doms_inconsistent(irg);
 143                 set_irg_extblk_inconsistent(irg);
 144                 set_irg_loopinfo_inconsistent(irg);
 145         }
 146         DEL_ARR_F(env.muxes);
 147 }
 148
 149 struct pass_t {
 150         ir_graph_pass_t    pass;
 151         lower_mux_callback *cb_func;
 152 };
 153
 154 /**
 155  * Wrapper to run ir_lower_mux() as an ir_graph pass
 156  */
 157 static int pass_wrapper(ir_graph *irg, void *context)
 158 {
 159         struct pass_t *pass = context;
 160
 161         lower_mux(irg, pass->cb_func);
 162         return 0;
 163 }
 164
 165 ir_graph_pass_t *lower_mux_pass(const char *name, lower_mux_callback *cb_func) {
 166         struct pass_t *pass = XMALLOCZ(struct pass_t);
 167
 168         pass->cb_func = cb_func;
 169         return def_graph_pass_constructor(
 170                 &pass->pass, name ? name : "lower_mux", pass_wrapper);
 171 }