nsz Git - libfirm/blob - ir/ana/irconsconfirm.c

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief    Construction of Confirm nodes
  23  * @author   Michael Beck
  24  * @date     6.2005
  25  * @version  $Id$
  26  */
  27 #ifdef HAVE_CONFIG_H
  28 # include "config.h"
  29 #endif
  30
  31 #include "irgraph_t.h"
  32 #include "irnode_t.h"
  33 #include "ircons_t.h"
  34 #include "irgmod.h"
  35 #include "iropt_dbg.h"
  36 #include "iredges_t.h"
  37 #include "irgwalk.h"
  38 #include "irprintf.h"
  39 #include "irtools.h"
  40
  41 /**
  42  * Walker environment.
  43  */
  44 typedef struct _env_t {
  45   unsigned num_confirms;  /**< number of inserted Confirm nodes */
  46   unsigned num_consts;    /**< number of constants placed */
  47   unsigned num_eq;        /**< number of equalities placed */
  48 } env_t;
  49
  50 /**
  51  * Return the effective use block of a node and it's predecessor on
  52  * position pos.
  53  *
  54  * @param node  the node
  55  * @param pos   the position of the used input
  56  *
  57  * This handles correctly Phi nodes.
  58  */
  59 static ir_node *get_effective_use_block(ir_node *node, int pos) {
  60         /* the effective use of a Phi is in its predecessor block */
  61         if (is_Phi(node))
  62                 return get_nodes_block(get_irn_n(node, pos));
  63         else
  64                 return get_nodes_block(node);
  65 }
  66
  67 /**
  68  * Handle a CASE-branch.
  69  *
  70  * @param block   the block which is entered by the branch
  71  * @param irn     the node expressing the switch value
  72  * @param nr      the branch label
  73  * @param env     statistical environment
  74  *
  75  * Branch labels are a simple case. We can replace the value
  76  * by a Const with the branch label.
  77  */
  78 static void handle_case(ir_node *block, ir_node *irn, long nr, env_t *env) {
  79         const ir_edge_t *edge, *next;
  80         ir_node *c = NULL;
  81
  82         if (is_Bad(irn))
  83                 return;
  84
  85         for (edge = get_irn_out_edge_first(irn); edge; edge = next) {
  86                 ir_node *succ = get_edge_src_irn(edge);
  87                 int     pos   = get_edge_src_pos(edge);
  88                 ir_node *blk  = get_effective_use_block(succ, pos);
  89
  90                 next = get_irn_out_edge_next(irn, edge);
  91
  92                 if (block_dominates(block, blk)) {
  93                         /*
  94                          * Ok, we found a user of irn that is placed
  95                          * in a block dominated by the branch block.
  96                          * We can replace the input with the Constant
  97                          * branch label.
  98                          */
  99
 100                         if (! c) {
 101                                 ir_mode *mode = get_irn_mode(irn);
 102                                 ir_type *tp   = get_irn_type(irn);
 103                                 tarval *tv    = new_tarval_from_long(nr, mode);
 104                                 c = new_r_Const_type(current_ir_graph, block, mode, tv, tp);
 105                         }
 106
 107                         set_irn_n(succ, pos, c);
 108                         DBG_OPT_CONFIRM_C(irn, c);
 109 //                      ir_printf("1 Replacing input %d of node %n with %n\n", pos, succ, c);
 110
 111                         env->num_consts += 1;
 112                 }
 113         }
 114 }  /* handle_case */
 115
 116 /**
 117  * Handle an IF-branch.
 118  *
 119  * @param block   the block which is entered by the branch
 120  * @param cmp     the Cmp node expressing the branch condition
 121  * @param pnc     the Compare relation for taking this branch
 122  * @param env     statistical environment
 123  */
 124 static void handle_if(ir_node *block, ir_node *cmp, pn_Cmp pnc, env_t *env) {
 125         ir_node *left  = get_Cmp_left(cmp);
 126         ir_node *right = get_Cmp_right(cmp);
 127         ir_node *cond_block;
 128         ir_op *op;
 129         const ir_edge_t *edge, *next;
 130
 131         /* Beware of Bads */
 132         if (is_Bad(left) ||is_Bad(right))
 133                 return;
 134
 135         op = get_irn_op(left);
 136
 137         /* Do not create Confirm nodes for Cmp(Const, Const) constructs.
 138            These are removed anyway */
 139         if (op == op_Const && is_Const(right))
 140                 return;
 141
 142         /* try to place the constant on the right side for a Confirm */
 143         if (op == op_Const || op == op_SymConst) {
 144                 ir_node *t = left;
 145
 146                 left  = right;
 147                 right = t;
 148
 149                 pnc = get_inversed_pnc(pnc);
 150         }
 151
 152         /*
 153          * First case: both values are identical.
 154          * replace the left one by the right (potentially const) one.
 155          */
 156         if (pnc == pn_Cmp_Eq) {
 157                 cond_block = get_Block_cfgpred_block(block, 0);
 158                 for (edge = get_irn_out_edge_first(left); edge; edge = next) {
 159                         ir_node *user = get_edge_src_irn(edge);
 160                         int     pos   = get_edge_src_pos(edge);
 161                         ir_node *blk  = get_effective_use_block(user, pos);
 162
 163                         next = get_irn_out_edge_next(left, edge);
 164                         if (block_dominates(block, blk)) {
 165                                 /*
 166                                  * Ok, we found a usage of left in a block
 167                                  * dominated by the branch block.
 168                                  * We can replace the input with right.
 169                                  */
 170                                 set_irn_n(user, pos, right);
 171                                 DBG_OPT_CONFIRM(left, right);
 172
 173 //                              ir_printf("2 Replacing input %d of node %n with %n\n", pos, user, right);
 174
 175                                 env->num_eq += 1;
 176                         } else if (block_dominates(blk, cond_block)) {
 177                                 if (is_Const(right) && get_irn_pinned(user) == op_pin_state_floats) {
 178                                         /*
 179                                          * left == Const and we found a movable user of left in a
 180                                          * dominator of the Cond block
 181                                          */
 182                                         const ir_edge_t *edge, *next;
 183                                         for (edge = get_irn_out_edge_first(user); edge; edge = next) {
 184                                                 ir_node *usr_of_usr = get_edge_src_irn(edge);
 185                                                 int      npos = get_edge_src_pos(edge);
 186                                                 ir_node *blk  = get_effective_use_block(usr_of_usr, npos);
 187
 188                                                 next = get_irn_out_edge_next(user, edge);
 189                                                 if (block_dominates(block, blk)) {
 190                                                         /*
 191                                                          * The user of the user is dominated by our true/false
 192                                                          * block. So, create a copy of user WITH the constant
 193                                                          * replacing it's pos'th input.
 194                                                          *
 195                                                          * This is always good for unop's and might be good
 196                                                          * for binops.
 197                                                          *
 198                                                          * If user has other user in the false/true block, code
 199                                                          * placement will move it down.
 200                                                          * If there are users in cond block or upper, we create
 201                                                          * "redundant ops", because one will have a const op,
 202                                                          * the other no const ...
 203                                                          */
 204                                                         ir_node *new_op = exact_copy(user);
 205                                                         set_nodes_block(new_op, block);
 206                                                         set_irn_n(new_op, pos, right);
 207                                                         set_irn_n(usr_of_usr, npos, new_op);
 208                                                 }
 209                                         }
 210                                 }
 211                         }
 212                 }
 213         } else { /* not pn_Cmp_Eq cases */
 214                 ir_node *c = NULL;
 215
 216                 for (edge = get_irn_out_edge_first(left); edge; edge = next) {
 217                         ir_node *succ = get_edge_src_irn(edge);
 218                         int     pos   = get_edge_src_pos(edge);
 219                         ir_node *blk  = get_effective_use_block(succ, pos);
 220
 221                         next = get_irn_out_edge_next(left, edge);
 222                         if (block_dominates(block, blk)) {
 223                                 /*
 224                                  * Ok, we found a usage of left in a block
 225                                  * dominated by the branch block.
 226                                  * We can replace the input with a Confirm(left, pnc, right).
 227                                  */
 228                                 if (! c)
 229                                         c = new_r_Confirm(current_ir_graph, block, left, right, pnc);
 230
 231                                 pos = get_edge_src_pos(edge);
 232                                 set_irn_n(succ, pos, c);
 233 //                              ir_printf("3 Replacing input %d of node %n with %n\n", pos, user, c);
 234
 235                                 env->num_confirms += 1;
 236                         }
 237                 }
 238         }
 239 }  /* handle_if */
 240
 241 /**
 242  * Pre-walker: Called for every block to insert Confirm nodes
 243  */
 244 static void insert_Confirm(ir_node *block, void *env) {
 245         ir_node *cond, *proj, *selector;
 246         ir_mode *mode;
 247
 248         /*
 249          * we can only handle blocks with only ONE control flow
 250          * predecessor yet.
 251          */
 252         if (get_Block_n_cfgpreds(block) != 1)
 253                 return;
 254
 255         proj = get_Block_cfgpred(block, 0);
 256         if (get_irn_op(proj) != op_Proj)
 257                 return;
 258
 259         cond = get_Proj_pred(proj);
 260         if (get_irn_op(cond) != op_Cond)
 261                 return;
 262
 263         selector = get_Cond_selector(cond);
 264         mode = get_irn_mode(selector);
 265
 266         if (mode == mode_b) {
 267                 ir_node *cmp;
 268                 pn_Cmp pnc;
 269
 270                 /* this should be an IF, check this */
 271                 if (get_irn_op(selector) != op_Proj)
 272                         return;
 273
 274                 cmp = get_Proj_pred(selector);
 275                 if (get_irn_op(cmp) != op_Cmp)
 276                         return;
 277
 278                 pnc = get_Proj_proj(selector);
 279
 280                 if (get_Proj_proj(proj) != pn_Cond_true) {
 281                         /* it's the false branch */
 282                         pnc = get_negated_pnc(pnc, mode);
 283                 }
 284 //              ir_printf("At %n using %n Confirm %=\n", block, cmp, pnc);
 285
 286                 handle_if(block, cmp, pnc, env);
 287         } else if (mode_is_int(mode)) {
 288                 long proj_nr = get_Proj_proj(proj);
 289
 290                 /* this is a CASE, but we cannot handle the default case */
 291                 if (proj_nr == get_Cond_defaultProj(cond))
 292                         return;
 293
 294                 handle_case(block, get_Cond_selector(cond), proj_nr, env);
 295         }
 296 }  /* insert_Confirm */
 297
 298 /*
 299  * Construct Confirm nodes
 300  */
 301 void construct_confirms(ir_graph *irg) {
 302         env_t env;
 303         int edges_active = edges_activated(irg);
 304
 305         /* we need dominance info */
 306         assure_doms(irg);
 307
 308         assert(get_irg_pinned(irg) == op_pin_state_pinned &&
 309                "Nodes must be placed to insert Confirms");
 310
 311         if (! edges_active) {
 312                 /* We need edges */
 313                 edges_activate(irg);
 314         }
 315
 316         env.num_confirms = 0;
 317         env.num_consts   = 0;
 318         env.num_eq       = 0;
 319
 320         /* now, visit all blocks and add Confirms where possible */
 321         irg_block_walk_graph(irg, insert_Confirm, NULL, &env);
 322
 323         if (env.num_confirms | env.num_consts | env.num_eq) {
 324                 /* we have add nodes or changed DF edges */
 325                 set_irg_outs_inconsistent(irg);
 326
 327                 /* the new nodes are not in the loop info */
 328                 set_irg_loopinfo_inconsistent(irg);
 329         }
 330
 331 #if 0
 332         printf("# Confirms inserted : %u\n", env.num_confirms);
 333         printf("# Const replacements: %u\n", env.num_consts);
 334         printf("# node equalities   : %u\n", env.num_eq);
 335 #endif
 336
 337         /* deactivate edges if they where off */
 338         if (! edges_active)
 339                 edges_deactivate(irg);
 340 }  /* construct_confirms */
 341
 342 /**
 343  * Post-walker: Remove Confirm nodes
 344  */
 345 static void rem_Confirm(ir_node *n, void *env) {
 346         (void) env;
 347         if (get_irn_op(n) == op_Confirm) {
 348                 ir_node *value = get_Confirm_value(n);
 349                 if (value != n)
 350                         exchange(n, value);
 351                 else {
 352                         /*
 353                          * Strange: a Confirm is it's own bound. This can happen
 354                          * in dead blocks when Phi nodes are already removed.
 355                          */
 356                         exchange(n, new_Bad());
 357                 }
 358         }
 359 }  /* rem_Confirm */
 360
 361 /*
 362  * Remove all Confirm nodes from a graph.
 363  */
 364 void remove_confirms(ir_graph *irg) {
 365         irg_walk_graph(irg, NULL, rem_Confirm, NULL);
 366 }  /* remove_confirms */