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 "irnode_t.h"
  15 #include "iredges.h"
  16 #include "irtools.h"
  17 #include "tv.h"
  18
  19 DEBUG_ONLY(static firm_dbg_module_t *dbg);
  20
  21
  22 /**
  23  * Add the new predecessor x to node node, which is either a Block or a Phi
  24  */
  25 static void add_pred(ir_node* node, ir_node* x)
  26 {
  27         ir_node** ins;
  28         int n;
  29         int i;
  30
  31         assert(is_Block(node) || is_Phi(node));
  32
  33         n = get_irn_arity(node);
  34         NEW_ARR_A(ir_node*, ins, n + 1);
  35         for (i = 0; i < n; i++) ins[i] = get_irn_n(node, i);
  36         ins[n] = x;
  37         set_irn_in(node, n + 1, ins);
  38 }
  39
  40
  41 /**
  42  * Remove predecessor j from node, which is either a Block or a Phi
  43  * returns true if only one predecessor is left
  44  */
  45 static int remove_pred(ir_node* node, int j)
  46 {
  47         int n;
  48
  49         assert(is_Block(node) || is_Phi(node));
  50
  51         n = get_irn_arity(node);
  52         if (n == 2) {
  53                 ir_node* pred = get_irn_n(node, 1 - j);
  54
  55                 if (is_Block(node)) {
  56                         pred = get_nodes_block(pred);
  57                         set_irn_in(node, get_irn_arity(pred), get_irn_in(pred) + 1);
  58                         exchange(pred, node);
  59                 } else {
  60                         exchange(node, pred);
  61                 }
  62                 return 1;
  63         } else {
  64                 ir_node** ins;
  65                 int i;
  66
  67                 NEW_ARR_A(ir_node*, ins, n - 1);
  68                 for (i = 0; i < j; i++) ins[i]     = get_irn_n(node, i);
  69                 for (i++;   i < n; i++) ins[i - 1] = get_irn_n(node, i);
  70                 set_irn_in(node, n - 1, ins);
  71                 return 0;
  72         }
  73 }
  74
  75
  76 static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode)
  77 {
  78         int i;
  79         int n_cfgpreds;
  80         ir_graph *irg;
  81         ir_node *phi;
  82         ir_node **in;
  83
  84         assert(!is_Bad(block));
  85
  86         // already processed this block?
  87         if(irn_visited(block)) {
  88                 ir_node *value = (ir_node*) get_irn_link(block);
  89                 return value;
  90         }
  91
  92         // blocks with only 1 pred need no phi
  93         n_cfgpreds = get_Block_n_cfgpreds(block);
  94         if(n_cfgpreds == 1) {
  95                 ir_node *pred_block = get_Block_cfgpred_block(block, 0);
  96                 ir_node *value = search_def_and_create_phis(pred_block, mode);
  97
  98                 set_irn_link(block, value);
  99                 mark_irn_visited(block);
 100                 return value;
 101         }
 102
 103         // create a new phi
 104         in = alloca(sizeof(in[0]) * n_cfgpreds);
 105         for(i = 0; i < n_cfgpreds; ++i)
 106                 in[i] = new_Unknown(mode);
 107
 108         irg = get_irn_irg(block);
 109         phi = new_r_Phi(irg, block, n_cfgpreds, in, mode);
 110         set_irn_link(block, phi);
 111         mark_irn_visited(block);
 112
 113         // set phi preds
 114         for(i = 0; i < n_cfgpreds; ++i) {
 115                 ir_node *pred_block = get_Block_cfgpred_block(block, i);
 116                 ir_node *pred_val;
 117
 118                 pred_val = search_def_and_create_phis(pred_block, mode);
 119                 set_irn_n(phi, i, pred_val);
 120         }
 121
 122         return phi;
 123 }
 124
 125
 126 /**
 127  * Given a set of values this function constructs SSA-form for all users of the
 128  * values (the user are determined through the out-edges of the values).
 129  */
 130 static void construct_ssa(ir_node * const *blocks, ir_node * const *vals, int n_vals)
 131 {
 132         int i;
 133         ir_graph *irg;
 134         ir_mode *mode;
 135
 136         assert(n_vals > 0);
 137
 138         irg = get_irn_irg(vals[0]);
 139         inc_irg_visited(irg);
 140
 141         mode = get_irn_mode(vals[0]);
 142         for(i = 0; i < n_vals; ++i) {
 143                 ir_node *value = vals[i];
 144                 ir_node *value_block = blocks[i];
 145
 146                 assert(get_irn_mode(value) == mode);
 147
 148                 set_irn_link(value_block, value);
 149                 mark_irn_visited(value_block);
 150         }
 151
 152         for(i = 0; i < n_vals; ++i) {
 153                 const ir_edge_t *edge, *next;
 154                 ir_node *value = vals[i];
 155
 156                 // this can happen when fixing phi preds, we mustn't fix the users
 157                 if(get_nodes_block(value) != blocks[i]) {
 158                         continue;
 159                 }
 160
 161                 foreach_out_edge_safe(value, edge, next) {
 162                         ir_node *user = get_edge_src_irn(edge);
 163                         int j = get_edge_src_pos(edge);
 164                         ir_node *user_block = get_nodes_block(user);
 165                         ir_node *newval;
 166
 167                         // ignore keeps
 168                         if(get_irn_op(user) == op_End)
 169                                 continue;
 170
 171                         if(is_Phi(user)) {
 172                                 ir_node *pred_block = get_Block_cfgpred_block(user_block, j);
 173                                 newval = search_def_and_create_phis(pred_block, mode);
 174                         } else {
 175                                 newval = search_def_and_create_phis(user_block, mode);
 176                         }
 177
 178                         // don't fix newly created phis from the SSA construction
 179                         if(newval != user)
 180                                 set_irn_n(user, j, newval);
 181                 }
 182         }
 183 }
 184
 185
 186 #if 0
 187 /**
 188  * Compare node compares two Const nodes
 189  * Returns true if this direction is taken
 190  */
 191 static int handle_const_const(ir_node* cnst_left, cnst_right, pn_Cmp pnc)
 192 {
 193         // TODO
 194 }
 195 #endif
 196
 197
 198 /**
 199  *
 200  */
 201 static int handle_phi_const(ir_node* block, ir_node* cond_block, ir_node* phi, ir_node* cnst, pn_Cmp pnc)
 202 {
 203         int changed = 0;
 204         ir_graph *irg;
 205         tarval* tv_cnst;
 206         int n_phi;
 207         int j;
 208
 209         tv_cnst = get_Const_tarval(cnst);
 210         n_phi = get_Phi_n_preds(phi);
 211         for (j = 0; j < n_phi; j++) {
 212                 const ir_edge_t *edge, *next;
 213                 ir_node *pred;
 214                 ir_node *pred_block;
 215                 tarval *tv_phi;
 216                 pn_Cmp cmp_val;
 217
 218                 pred = get_Phi_pred(phi, j);
 219                 // TODO handle Phi cascades
 220                 if (!is_Const(pred))
 221                         continue;
 222
 223                 tv_phi = get_Const_tarval(pred);
 224
 225                 cmp_val = tarval_cmp(tv_phi, tv_cnst);
 226                 if (cmp_val == pn_Cmp_False) continue;
 227                 if ((cmp_val & pnc) != cmp_val) continue;
 228
 229                 DB((
 230                         dbg, LEVEL_1,
 231                         "> Found condition evaluation candidate %+F->%+F predecessor %d\n",
 232                         block, cond_block, j
 233                 ));
 234
 235                 add_pred(block, get_Block_cfgpred(cond_block, j));
 236                 // split critical edges
 237                 /*if(get_irn_arity(block) == 2)*/ {
 238                         ir_node *in[1];
 239                         ir_node *new_block;
 240                         ir_node *new_jmp;
 241
 242                         in[0] = get_Block_cfgpred(block, 0);
 243                         new_block = new_r_Block(current_ir_graph, 1, in);
 244                         new_jmp = new_r_Jmp(current_ir_graph, new_block);
 245                         set_Block_cfgpred(block, 0, new_jmp);
 246                 }
 247
 248                 pred_block = get_Block_cfgpred_block(cond_block, j);
 249
 250                 /* Look at all nodes in the cond_block and copy them into pred */
 251                 foreach_out_edge(cond_block, edge) {
 252                         ir_node *node = get_edge_src_irn(edge);
 253                         ir_node *copy;
 254
 255                         // ignore these as SSA construction would fail on ProjX
 256                         if (is_Proj(node) && get_irn_mode(node) == mode_X)
 257                                 continue;
 258
 259                         // we can evaluate Phis right now, all other nodes get copied
 260                         if (is_Phi(node)) {
 261                                 copy = get_Phi_pred(node, j);
 262                         } else {
 263                                 copy = exact_copy(node);
 264                                 set_nodes_block(copy, pred_block);
 265                         }
 266
 267                         set_irn_link(node, copy);
 268                 }
 269
 270                 /* fix data-flow (and reconstruct SSA if needed) */
 271                 foreach_out_edge(cond_block, edge) {
 272                         ir_node *vals[2];
 273                         ir_node *blocks[2];
 274
 275                         ir_node *node = get_edge_src_irn(edge);
 276                         assert(get_nodes_block(node) == cond_block);
 277                         if (is_Proj(node) && get_irn_mode(node) == mode_X)
 278                                 continue;
 279
 280                         blocks[0] = cond_block;
 281                         vals[0] = node;
 282                         blocks[1] = pred_block;
 283                         vals[1] = get_irn_link(node);
 284                         construct_ssa(blocks, vals, 2);
 285                 }
 286
 287                 /* shorten phis */
 288                 foreach_out_edge_safe(cond_block, edge, next) {
 289                         ir_node *node = get_edge_src_irn(edge);
 290
 291                         if(is_Phi(node))
 292                                 remove_pred(node, j);
 293                 }
 294
 295                 changed = 1;
 296                 remove_pred(cond_block, j);
 297 #if 0
 298                 if (remove_pred(cond_block, j))
 299                         break;
 300                 // the phi got shortened
 301                 n_phi--;
 302                 j--;
 303 #endif
 304                 break;
 305         }
 306
 307         if (changed) {
 308                 irg = get_irn_irg(block);
 309                 set_irg_doms_inconsistent(irg);
 310                 set_irg_extblk_inconsistent(irg);
 311                 set_irg_loopinfo_inconsistent(irg);
 312         }
 313         return changed;
 314 }
 315
 316
 317 /**
 318  * Block-walker:
 319  */
 320 static void cond_eval(ir_node* block, void* env)
 321 {
 322         int n_block;
 323         int i;
 324
 325         n_block = get_Block_n_cfgpreds(block);
 326         for (i = 0; i < n_block; i++) {
 327                 ir_node* pred;
 328                 ir_node* projx;
 329                 ir_node* cond;
 330                 ir_node* cmp;
 331                 ir_node* left;
 332                 ir_node* right;
 333                 ir_node* cond_block;
 334                 pn_Cmp pnc;
 335
 336                 pred = get_Block_cfgpred(block, i);
 337                 if (!is_Proj(pred)) continue;
 338                 projx = pred;
 339
 340                 pred = get_Proj_pred(projx);
 341                 if (!is_Cond(pred)) continue;
 342                 cond = pred;
 343
 344                 pred = get_Cond_selector(cond);
 345                 assert(is_Proj(pred));
 346                 // TODO handle switches
 347                 if (get_irn_mode(pred) != mode_b) continue;
 348                 pnc = get_Proj_proj(pred);
 349
 350                 cmp = get_Proj_pred(pred);
 351                 assert(is_Cmp(cmp));
 352
 353                 left  = get_Cmp_left(cmp);
 354                 right = get_Cmp_right(cmp);
 355                 assert(get_irn_mode(left) == get_irn_mode(right));
 356
 357                 if (get_Proj_proj(projx) == 0) {
 358                         pnc = get_negated_pnc(pnc, get_irn_mode(left));
 359                 }
 360
 361 #if 0 // TODO implement
 362                 if (is_Const(left) && is_Const(right)) {
 363                         if (!handle_const_const()) {
 364                                 n_block--;
 365                                 i--;
 366                         }
 367                         continue;
 368                 }
 369 #endif
 370                 cond_block = get_nodes_block(cond);
 371                 if (is_Phi(left) && is_Const(right)) {
 372                         if (get_nodes_block(left) != cond_block) continue;
 373                         handle_phi_const(block, cond_block, left, right, pnc);
 374                         continue;
 375                 }
 376                 if (is_Const(left) && is_Phi(right)) {
 377                         if (get_nodes_block(right) != cond_block) continue;
 378                         handle_phi_const(block, cond_block, right, left, get_inversed_pnc(pnc));
 379                         continue;
 380                 }
 381 #if 0
 382                 if (is_Phi(left) && is_Phi(right)) {
 383                         // TODO implement
 384                 }
 385 #endif
 386         }
 387 }
 388
 389
 390 void opt_cond_eval(ir_graph* irg)
 391 {
 392         FIRM_DBG_REGISTER(dbg, "firm.opt.condeval");
 393         firm_dbg_set_mask(dbg, SET_LEVEL_5);
 394
 395         DB((dbg, LEVEL_1, "===> Performing condition evaluation on %+F\n", irg));
 396
 397         if(edges_activated(irg))
 398                 edges_deactivate(irg);
 399         edges_assure(irg);
 400         remove_critical_cf_edges(irg);
 401
 402         normalize_proj_nodes(irg);
 403
 404         irg_block_walk_graph(irg, cond_eval, NULL, NULL);
 405 #if 0
 406         irg_block_walk_graph(irg, NULL, cond_eval, NULL);
 407         irg_block_walk_graph(irg, NULL, cond_eval, NULL);
 408         irg_block_walk_graph(irg, NULL, cond_eval, NULL);
 409 #endif
 410 }