nsz Git - libfirm/blob - ir/opt/condeval.c

   1 #ifdef HAVE_CONFIG_H
   2 #include "config.h"
   3 #endif
   4
   5 #include <assert.h>
   6 #include "array.h"
   7 #include "debug.h"
   8 #include "ircons.h"
   9 #include "irgwalk.h"
  10 #include "irnode.h"
  11 #include "iredges.h"
  12 #include "tv.h"
  13
  14 DEBUG_ONLY(static firm_dbg_module_t *dbg);
  15
  16 static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode) {
  17         int i;
  18         int n_cfgpreds;
  19         ir_graph *irg;
  20         ir_node *phi;
  21         ir_node **in;
  22
  23         assert(!is_Bad(block));
  24
  25         // already processed this block?
  26         if(irn_visited(block)) {
  27                 ir_node *value = (ir_node*) get_irn_link(block);
  28                 return value;
  29         }
  30
  31         // blocks with only 1 pred need no phi
  32         n_cfgpreds = get_Block_n_cfgpreds(block);
  33         if(n_cfgpreds == 1) {
  34                 ir_node *pred_block = get_Block_cfgpred_block(block, 0);
  35                 ir_node *value = search_def_and_create_phis(pred_block, mode);
  36
  37                 set_irn_link(block, value);
  38                 mark_irn_visited(block);
  39                 return value;
  40         }
  41
  42         // create a new phi
  43         in = alloca(sizeof(in[0]) * n_cfgpreds);
  44         for(i = 0; i < n_cfgpreds; ++i)
  45                 in[i] = new_Unknown(mode);
  46
  47         irg = get_irn_irg(block);
  48         phi = new_r_Phi(irg, block, n_cfgpreds, in, mode);
  49         set_irn_link(block, phi);
  50         mark_irn_visited(block);
  51
  52         // set phi preds
  53         for(i = 0; i < n_cfgpreds; ++i) {
  54                 ir_node *pred_block = get_Block_cfgpred_block(block, i);
  55                 ir_node *pred_val;
  56
  57                 pred_val = search_def_and_create_phis(pred_block, mode);
  58                 set_irn_n(phi, i, pred_val);
  59         }
  60
  61         return phi;
  62 }
  63
  64 /**
  65  * Given a set of values this function constructs SSA-form for all users of the
  66  * values (the user are determined through the out-edges of the values).
  67  */
  68 static void construct_ssa(ir_node * const *vals, int n_vals) {
  69         int i;
  70         ir_graph *irg;
  71         ir_mode *mode;
  72
  73         assert(n_vals > 0);
  74
  75         irg = get_irn_irg(vals[0]);
  76         inc_irg_visited(irg);
  77
  78         mode = get_irn_mode(vals[0]);
  79         for(i = 0; i < n_vals; ++i) {
  80                 ir_node *value = vals[i];
  81                 ir_node *value_block = get_nodes_block(value);
  82
  83                 assert(get_irn_mode(value) == mode);
  84
  85                 set_irn_link(value_block, value);
  86                 mark_irn_visited(value_block);
  87         }
  88
  89         for(i = 0; i < n_vals; ++i) {
  90                 const ir_edge_t *edge;
  91                 ir_node *value = vals[i];
  92
  93                 foreach_out_edge(value, edge) {
  94                         ir_node *user = get_edge_src_irn(edge);
  95                         ir_node *user_block = get_nodes_block(user);
  96                         ir_node *newval;
  97
  98                         newval = search_def_and_create_phis(user_block, mode);
  99                         set_irn_n(user, get_edge_src_pos(edge), newval);
 100                 }
 101         }
 102 }
 103
 104 /**
 105  * Block-walker:
 106  */
 107 static void cond_eval(ir_node* block, void* env)
 108 {
 109         int n_block = get_Block_n_cfgpreds(block);
 110         int i;
 111
 112         for (i = 0; i < n_block; i++) {
 113                 ir_node* pred;
 114                 ir_node* projx;
 115                 ir_node* cond;
 116                 ir_node* cmp;
 117                 ir_node* left;
 118                 ir_node* right;
 119                 ir_node* cond_block;
 120                 ir_node* phi;
 121                 ir_node* cnst;
 122                 tarval *tv_cnst;
 123                 pn_Cmp pnc;
 124                 int n_phi;
 125                 int j;
 126
 127                 pred = get_Block_cfgpred(block, i);
 128                 if (!is_Proj(pred)) continue;
 129                 projx = pred;
 130
 131                 pred = get_Proj_pred(projx);
 132                 if (!is_Cond(pred)) continue;
 133                 cond = pred;
 134
 135                 pred = get_Cond_selector(cond);
 136                 assert(is_Proj(pred));
 137                 // TODO handle switches
 138                 if (get_irn_mode(pred) != mode_b) continue;
 139                 pnc = get_Proj_proj(pred);
 140
 141                 cmp = get_Proj_pred(pred);
 142                 assert(is_Cmp(cmp));
 143
 144                 left  = get_Cmp_left(cmp);
 145                 right = get_Cmp_right(cmp);
 146
 147                 // TODO handle Const-Const and Phi-Phi
 148                 if (is_Phi(left)) {
 149                         if (!is_Const(right)) continue;
 150                         phi  = left;
 151                         cnst = right;
 152                 } else if (is_Phi(right)) {
 153                         if (!is_Const(left)) continue;
 154                         phi  = right;
 155                         cnst = left;
 156                         pnc = get_inversed_pnc(pnc);
 157                 } else {
 158                         continue;
 159                 }
 160                 tv_cnst = get_Const_tarval(cnst);
 161
 162                 cond_block = get_nodes_block(cond);
 163                 if (get_nodes_block(phi) != cond_block) continue;
 164
 165                 if (get_Proj_proj(projx) == 0) {
 166                         pnc = get_negated_pnc(pnc, get_irn_mode(cnst));
 167                 }
 168
 169                 n_phi = get_Phi_n_preds(phi);
 170                 for (j = 0; j < n_phi; j++) {
 171                         tarval* tv_phi;
 172                         ir_node** ins;
 173                         int k;
 174                         pn_Cmp cmp_val;
 175
 176                         pred = get_Phi_pred(phi, j);
 177                         // TODO handle Phi cascades
 178                         if (!is_Const(pred)) continue;
 179
 180                         tv_phi  = get_Const_tarval(pred);
 181
 182                         cmp_val = tarval_cmp(tv_phi, tv_cnst);
 183                         if (cmp_val == pn_Cmp_False)
 184                                 continue;
 185                         if ((cmp_val & pnc) != cmp_val)
 186                                 continue;
 187
 188                         DB((
 189                                 dbg, LEVEL_1,
 190                                 "> Found condition evaluation candidate %+F->%+F predecessor %d\n",
 191                                 block, cond_block, j
 192                         ));
 193
 194 #if 0 // TODO repair data flow and dominance
 195                         NEW_ARR_A(ir_node*, ins, n_block + 1);
 196                         for (k = 0; k < n_block; k++) ins[k] = get_Block_cfgpred(block, k);
 197                         ins[k] = get_Block_cfgpred(cond_block, j);
 198                         set_irn_in(block, n_block + 1, ins);
 199
 200                         set_Block_cfgpred(cond_block, j, new_Bad());
 201                         set_Phi_pred(phi, j, new_Bad());
 202 #endif
 203                 }
 204         }
 205 }
 206
 207
 208 void opt_cond_eval(ir_graph* irg)
 209 {
 210         FIRM_DBG_REGISTER(dbg, "firm.opt.condeval");
 211     firm_dbg_set_mask(dbg, SET_LEVEL_5);
 212
 213         DB((dbg, LEVEL_1, "===> Performing condition evaluation on %+F\n", irg));
 214
 215         irg_block_walk_graph(irg, NULL, cond_eval, NULL);
 216 }