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

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief   Replaces Mux nodes with control-flow
   9  * @author  Olaf Liebe
  10  */
  11 #include "config.h"
  12
  13 #include <assert.h>
  14
  15 #include "lowering.h"
  16 #include "array.h"
  17 #include "irnode_t.h"
  18 #include "irgraph_t.h"
  19 #include "irgwalk.h"
  20 #include "irgmod.h"
  21 #include "ircons.h"
  22 #include "irpass_t.h"
  23
  24 typedef struct walk_env {
  25         lower_mux_callback *cb_func;
  26         ir_node            **muxes;
  27 } walk_env_t;
  28
  29 static void find_mux_nodes(ir_node *mux, void *ctx)
  30 {
  31         walk_env_t *env = (walk_env_t*)ctx;
  32
  33         /* Skip non-mux nodes. */
  34         if (!is_Mux(mux))
  35                 return;
  36
  37         /* Skip nodes, depending on the callback function. */
  38         if (env->cb_func != NULL && !env->cb_func(mux)) {
  39                 return;
  40         }
  41
  42         /* Store the node. */
  43         ARR_APP1(ir_node*, env->muxes, mux);
  44 }
  45
  46 static void lower_mux_node(ir_node* mux)
  47 {
  48         ir_node  *upper_block;
  49         ir_node  *lower_block;
  50         ir_node  *cond;
  51         ir_node  *trueProj;
  52         ir_node  *falseProj;
  53         ir_node  *falseBlock;
  54         ir_node  *mux_jmps[2];
  55         ir_node  *mux_values[2];
  56         ir_node  *phi;
  57         ir_graph *irg;
  58
  59         irg = get_irn_irg(mux);
  60
  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);
  64         part_block(mux);
  65         upper_block = get_nodes_block(mux);
  66
  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);
  77
  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);
  82
  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));
  88         exchange(mux, phi);
  89
  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);
  96
  97         add_Block_phi(lower_block, phi);
  98 }
  99
 100 void lower_mux(ir_graph *irg, lower_mux_callback *cb_func)
 101 {
 102         size_t     i, n_muxes;
 103         walk_env_t env;
 104
 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);
 109
 110         n_muxes = ARR_LEN(env.muxes);
 111         if (n_muxes > 0) {
 112                 ir_resources_t resources = IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST;
 113
 114                 /* This is required by part_block() later. */
 115                 ir_reserve_resources(irg, resources);
 116                 collect_phiprojs(irg);
 117
 118                 for (i = 0; i < n_muxes; ++i) {
 119                         lower_mux_node(env.muxes[i]);
 120                 }
 121
 122                 /* Cleanup, verify the graph. */
 123                 ir_free_resources(irg, resources);
 124
 125                 clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE);
 126         }
 127         DEL_ARR_F(env.muxes);
 128 }
 129
 130 typedef struct pass_t {
 131         ir_graph_pass_t    pass;
 132         lower_mux_callback *cb_func;
 133 } pass_t;
 134
 135 /**
 136  * Wrapper to run ir_lower_mux() as an ir_graph pass
 137  */
 138 static int pass_wrapper(ir_graph *irg, void *context)
 139 {
 140         pass_t *pass = (pass_t*)context;
 141
 142         lower_mux(irg, pass->cb_func);
 143         return 0;
 144 }
 145
 146 ir_graph_pass_t *lower_mux_pass(const char *name, lower_mux_callback *cb_func)
 147 {
 148         pass_t *pass = XMALLOCZ(pass_t);
 149
 150         pass->cb_func = cb_func;
 151         return def_graph_pass_constructor(
 152                 &pass->pass, name ? name : "lower_mux", pass_wrapper);
 153 }