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

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