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 "condeval.h"
   8 #include "debug.h"
   9 #include "ircons.h"
  10 #include "irgmod.h"
  11 #include "irgopt.h"
  12 #include "irgwalk.h"
  13 #include "irnode.h"
  14 #include "iredges.h"
  15 #include "tv.h"
  16
  17 DEBUG_ONLY(static firm_dbg_module_t *dbg);
  18
  19
  20 /**
  21  * Add the new predecessor x to node node, which is either a Block or a Phi
  22  */
  23 static void add_pred(ir_node* node, ir_node* x)
  24 {
  25         ir_node** ins;
  26         int n;
  27         int i;
  28
  29         assert(is_Block(node) || is_Phi(node));
  30
  31         n = get_irn_arity(node);
  32         NEW_ARR_A(ir_node*, ins, n + 1);
  33         for (i = 0; i < n; i++) ins[i] = get_irn_n(node, i);
  34         ins[n] = x;
  35         set_irn_in(node, n + 1, ins);
  36 }
  37
  38
  39 /**
  40  * Remove predecessor j from node, which is either a Block or a Phi
  41  * returns true if only one predecessor is left
  42  */
  43 static int remove_pred(ir_node* node, int j)
  44 {
  45         int n;
  46
  47         assert(is_Block(node) || is_Phi(node));
  48
  49         n = get_irn_arity(node);
  50         if (n == 2) {
  51                 ir_node* pred = get_irn_n(node, 1 - j);
  52
  53                 if (is_Block(node)) pred = get_nodes_block(pred);
  54                 exchange(node, pred);
  55                 return 1;
  56         } else {
  57                 ir_node** ins;
  58                 int i;
  59
  60                 NEW_ARR_A(ir_node*, ins, n - 1);
  61                 for (i = 0; i < j; i++) ins[i]     = get_irn_n(node, i);
  62                 for (i++;   i < n; i++) ins[i - 1] = get_irn_n(node, i);
  63                 set_irn_in(node, n - 1, ins);
  64                 return 0;
  65         }
  66 }
  67
  68
  69 static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode)
  70 {
  71         int i;
  72         int n_cfgpreds;
  73         ir_graph *irg;
  74         ir_node *phi;
  75         ir_node **in;
  76
  77         assert(!is_Bad(block));
  78
  79         // already processed this block?
  80         if(irn_visited(block)) {
  81                 ir_node *value = (ir_node*) get_irn_link(block);
  82                 return value;
  83         }
  84
  85         // blocks with only 1 pred need no phi
  86         n_cfgpreds = get_Block_n_cfgpreds(block);
  87         if(n_cfgpreds == 1) {
  88                 ir_node *pred_block = get_Block_cfgpred_block(block, 0);
  89                 ir_node *value = search_def_and_create_phis(pred_block, mode);
  90
  91                 set_irn_link(block, value);
  92                 mark_irn_visited(block);
  93                 return value;
  94         }
  95
  96         // create a new phi
  97         in = alloca(sizeof(in[0]) * n_cfgpreds);
  98         for(i = 0; i < n_cfgpreds; ++i)
  99                 in[i] = new_Unknown(mode);
 100
 101         irg = get_irn_irg(block);
 102         phi = new_r_Phi(irg, block, n_cfgpreds, in, mode);
 103         set_irn_link(block, phi);
 104         mark_irn_visited(block);
 105
 106         // set phi preds
 107         for(i = 0; i < n_cfgpreds; ++i) {
 108                 ir_node *pred_block = get_Block_cfgpred_block(block, i);
 109                 ir_node *pred_val;
 110
 111                 pred_val = search_def_and_create_phis(pred_block, mode);
 112                 set_irn_n(phi, i, pred_val);
 113         }
 114
 115         return phi;
 116 }
 117
 118
 119 /**
 120  * Given a set of values this function constructs SSA-form for all users of the
 121  * values (the user are determined through the out-edges of the values).
 122  */
 123 static void construct_ssa(ir_node * const *vals, int n_vals)
 124 {
 125         int i;
 126         ir_graph *irg;
 127         ir_mode *mode;
 128
 129         assert(n_vals > 0);
 130
 131         irg = get_irn_irg(vals[0]);
 132         inc_irg_visited(irg);
 133
 134         mode = get_irn_mode(vals[0]);
 135         for(i = 0; i < n_vals; ++i) {
 136                 ir_node *value = vals[i];
 137                 ir_node *value_block = get_nodes_block(value);
 138
 139                 assert(get_irn_mode(value) == mode);
 140
 141                 set_irn_link(value_block, value);
 142                 mark_irn_visited(value_block);
 143         }
 144
 145         for(i = 0; i < n_vals; ++i) {
 146                 const ir_edge_t *edge;
 147                 ir_node *value = vals[i];
 148
 149                 foreach_out_edge(value, edge) {
 150                         ir_node *user = get_edge_src_irn(edge);
 151                         ir_node *user_block = get_nodes_block(user);
 152                         ir_node *newval;
 153
 154                         newval = search_def_and_create_phis(user_block, mode);
 155                         set_irn_n(user, get_edge_src_pos(edge), newval);
 156                 }
 157         }
 158 }
 159
 160
 161 #if 0
 162 /**
 163  * Compare node compares two Const nodes
 164  * Returns true if this direction is taken
 165  */
 166 static int handle_const_const(ir_node* cnst_left, cnst_right, pn_Cmp pnc)
 167 {
 168         // TODO
 169 }
 170 #endif
 171
 172
 173 /**
 174  *
 175  */
 176 static void handle_phi_const(ir_node* block, ir_node* cond_block, ir_node* phi, ir_node* cnst, pn_Cmp pnc)
 177 {
 178         tarval* tv_cnst;
 179         int n_phi;
 180         int j;
 181
 182         tv_cnst = get_Const_tarval(cnst);
 183         n_phi = get_Phi_n_preds(phi);
 184         for (j = 0; j < n_phi; j++) {
 185                 ir_node* pred;
 186                 tarval* tv_phi;
 187                 pn_Cmp cmp_val;
 188
 189                 pred = get_Phi_pred(phi, j);
 190                 // TODO handle Phi cascades
 191                 if (!is_Const(pred)) continue;
 192
 193                 tv_phi  = get_Const_tarval(pred);
 194
 195                 cmp_val = tarval_cmp(tv_phi, tv_cnst);
 196                 if (cmp_val == pn_Cmp_False) continue;
 197                 if ((cmp_val & pnc) != cmp_val) continue;
 198
 199                 DB((
 200                         dbg, LEVEL_1,
 201                         "> Found condition evaluation candidate %+F->%+F predecessor %d\n",
 202                         block, cond_block, j
 203                 ));
 204
 205 #if 0 // TODO repair data flow and dominance
 206                 add_pred(block, get_Block_cfgpred(cond_block, j));
 207
 208                 remove_pred(phi, j);
 209                 if (remove_pred(cond_block, j)) break;
 210 #endif
 211         }
 212 }
 213
 214
 215 /**
 216  * Block-walker:
 217  */
 218 static void cond_eval(ir_node* block, void* env)
 219 {
 220         int n_block = get_Block_n_cfgpreds(block);
 221         int i;
 222
 223         for (i = 0; i < n_block; i++) {
 224                 ir_node* pred;
 225                 ir_node* projx;
 226                 ir_node* cond;
 227                 ir_node* cmp;
 228                 ir_node* left;
 229                 ir_node* right;
 230                 ir_node* cond_block;
 231                 pn_Cmp pnc;
 232
 233                 pred = get_Block_cfgpred(block, i);
 234                 if (!is_Proj(pred)) continue;
 235                 projx = pred;
 236
 237                 pred = get_Proj_pred(projx);
 238                 if (!is_Cond(pred)) continue;
 239                 cond = pred;
 240
 241                 pred = get_Cond_selector(cond);
 242                 assert(is_Proj(pred));
 243                 // TODO handle switches
 244                 if (get_irn_mode(pred) != mode_b) continue;
 245                 pnc = get_Proj_proj(pred);
 246
 247                 cmp = get_Proj_pred(pred);
 248                 assert(is_Cmp(cmp));
 249
 250                 left  = get_Cmp_left(cmp);
 251                 right = get_Cmp_right(cmp);
 252                 assert(get_irn_mode(left) == get_irn_mode(right));
 253
 254                 if (get_Proj_proj(projx) == 0) {
 255                         pnc = get_negated_pnc(pnc, get_irn_mode(left));
 256                 }
 257
 258 #if 0 // TODO implement
 259                 if (is_Const(left) && is_Const(right)) {
 260                         if (!handle_const_const()) {
 261                                 n_block--;
 262                                 i--;
 263                         }
 264                         continue;
 265                 }
 266 #endif
 267                 cond_block = get_nodes_block(cond);
 268                 if (is_Phi(left) && is_Const(right)) {
 269                         if (get_nodes_block(left) != cond_block) continue;
 270                         handle_phi_const(block, cond_block, left, right, pnc);
 271                         continue;
 272                 }
 273                 if (is_Const(left) && is_Phi(right)) {
 274                         if (get_nodes_block(right) != cond_block) continue;
 275                         handle_phi_const(block, cond_block, right, left, get_inversed_pnc(pnc));
 276                         continue;
 277                 }
 278 #if 0
 279                 if (is_Phi(left) && is_Phi(right)) {
 280                         // TODO implement
 281                 }
 282 #endif
 283         }
 284 }
 285
 286
 287 void opt_cond_eval(ir_graph* irg)
 288 {
 289         FIRM_DBG_REGISTER(dbg, "firm.opt.condeval");
 290         firm_dbg_set_mask(dbg, SET_LEVEL_5);
 291
 292         DB((dbg, LEVEL_1, "===> Performing condition evaluation on %+F\n", irg));
 293
 294         remove_critical_cf_edges(irg);
 295
 296         irg_block_walk_graph(irg, NULL, cond_eval, NULL);
 297 }