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

   1 /*
   2  * Copyright (C) 1995-2007 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   conv node optimisation
  23  * @author  Matthias Braun, Christoph Mallon
  24  * @version $Id$
  25  *
  26  * Try to minimize the number of conv nodes by changing modes of operations.
  27  * The typical example is the following structure:
  28  *    (some node mode_Hs)
  29  *            |                                       (some node_Hs)
  30  *         Conv Is                                          |
  31  *            |                                          Add Hs
  32  *          Add Is            gets transformed to           |
  33  *            |
  34  *         Conv Hs
  35  *
  36  * TODO: * try to optimize cmp modes
  37  *       * decide when it is useful to move the convs through phis
  38  */
  39 #ifdef HAVE_CONFIG_H
  40 #include "config.h"
  41 #endif
  42
  43 #include "iroptimize.h"
  44
  45 #include <assert.h>
  46 #include "debug.h"
  47 #include "ircons.h"
  48 #include "irgmod.h"
  49 #include "irgopt.h"
  50 #include "irnode_t.h"
  51 #include "iredges_t.h"
  52 #include "irgwalk.h"
  53 #include "irprintf.h"
  54
  55 DEBUG_ONLY(static firm_dbg_module_t *dbg);
  56
  57 static INLINE int imin(int a, int b) { return a < b ? a : b; }
  58
  59 static
  60 int is_optimizable_node(const ir_node *node)
  61 {
  62         switch (get_irn_opcode(node)) {
  63                 case iro_Add:
  64                 case iro_And:
  65                 case iro_Eor:
  66                 case iro_Minus:
  67                 case iro_Mul:
  68                 case iro_Not:
  69                 case iro_Or:
  70                 case iro_Phi:
  71                 case iro_Shl:
  72                 case iro_Sub:
  73                         return 1;
  74
  75                 default: return 0;
  76         }
  77 }
  78
  79 static tarval* conv_const_tv(const ir_node* cnst, ir_mode* dest_mode)
  80 {
  81         return tarval_convert_to(get_Const_tarval(cnst), dest_mode);
  82 }
  83
  84 static
  85 int is_downconv(ir_mode *src_mode, ir_mode *dest_mode)
  86 {
  87         return
  88                 mode_is_int(src_mode) &&
  89                 mode_is_int(dest_mode) &&
  90                 get_mode_size_bits(dest_mode) < get_mode_size_bits(src_mode);
  91 }
  92
  93 static
  94 int get_conv_costs(const ir_node *node, ir_mode *dest_mode)
  95 {
  96         ir_mode *mode = get_irn_mode(node);
  97         size_t arity;
  98         size_t i;
  99         int costs;
 100
 101         if (mode == dest_mode)
 102                 return 0;
 103
 104         if (is_Const(node)) {
 105                 /* TODO tarval module is incomplete and can't convert floats to ints */
 106                 return conv_const_tv(node, dest_mode) == tarval_bad ? 1 : 0;
 107         }
 108
 109         if (get_irn_n_edges(node) > 1) {
 110                 if (is_Conv(node) && is_downconv(get_irn_mode(node), dest_mode)) {
 111                         return get_conv_costs(get_Conv_op(node), dest_mode) - 1;
 112                 }
 113                 DB((dbg, LEVEL_3, "multi outs at %+F\n", node));
 114                 return 1;
 115         }
 116
 117         if (is_Conv(node) && is_downconv(get_irn_mode(node), dest_mode)) {
 118                 return get_conv_costs(get_Conv_op(node), dest_mode) - 1;
 119         }
 120
 121 #if 0 // TODO
 122         /* Take the minimum of the conversion costs for Phi predecessors as only one
 123          * branch is actually executed at a time */
 124         if (is_Phi(node)) {
 125                 size_t i;
 126                 size_t arity = get_Phi_n_preds(node);
 127                 int costs;
 128
 129                 costs = get_conv_costs(get_Phi_pred(node, 0), dest_mode);
 130                 for (i = 1; i < arity; ++i) {
 131                         ir_node *pred = get_Phi_pred(node, i);
 132                         int c = get_conv_costs(pred, dest_mode);
 133                         if (c < costs) costs = c;
 134                 }
 135
 136                 return costs;
 137         }
 138 #endif
 139
 140         if (!is_optimizable_node(node)) {
 141                 return 1;
 142         }
 143
 144         costs = 0;
 145         arity = get_irn_arity(node);
 146         for (i = 0; i < arity; ++i) {
 147                 ir_node *pred = get_irn_n(node, i);
 148                 costs += imin(get_conv_costs(pred, dest_mode), 1);
 149         }
 150
 151         return costs;
 152 }
 153
 154 static ir_node *place_conv(ir_node *node, ir_mode *dest_mode)
 155 {
 156         ir_node *block = get_nodes_block(node);
 157         ir_node *conv = new_r_Conv(current_ir_graph, block, node, dest_mode);
 158         return conv;
 159 }
 160
 161 static
 162 ir_node *conv_transform(ir_node *node, ir_mode *dest_mode)
 163 {
 164         size_t arity;
 165         size_t i;
 166
 167         if (get_irn_mode(node) == dest_mode)
 168                 return node;
 169
 170         if (is_Const(node)) {
 171                 /* TODO tarval module is incomplete and can't convert floats to ints */
 172                 tarval *tv = conv_const_tv(node, dest_mode);
 173                 if (tv == tarval_bad) {
 174                         return place_conv(node, dest_mode);
 175                 } else {
 176                         return new_Const(dest_mode, tv);
 177                 }
 178         }
 179
 180         if (get_irn_n_edges(node) > 1) {
 181                 if (is_Conv(node) && is_downconv(get_irn_mode(node), dest_mode)) {
 182                         return conv_transform(get_Conv_op(node), dest_mode);
 183                 }
 184                 return place_conv(node, dest_mode);
 185         }
 186
 187         if (is_Conv(node) && is_downconv(get_irn_mode(node), dest_mode)) {
 188                 return conv_transform(get_Conv_op(node), dest_mode);
 189         }
 190
 191         if (!is_optimizable_node(node)) {
 192                 return place_conv(node, dest_mode);
 193         }
 194
 195         arity = get_irn_arity(node);
 196         for (i = 0; i < arity; i++) {
 197                 ir_node *pred = get_irn_n(node, i);
 198                 ir_node *transformed;
 199                 if (get_conv_costs(pred, dest_mode) > 0) {
 200                         transformed = place_conv(pred, dest_mode);
 201                 } else {
 202                         transformed = conv_transform(pred, dest_mode);
 203                 }
 204                 set_irn_n(node, i, transformed);
 205         }
 206         set_irn_mode(node, dest_mode);
 207         return node;
 208 }
 209
 210 /* TODO, backends (at least ia32) can't handle it at the moment,
 211    and it's probably not more efficient on most archs */
 212 #if 0
 213 static
 214 void try_optimize_cmp(ir_node *node)
 215 {
 216         ir_node *left  = get_Cmp_left(node);
 217         ir_node *right = get_Cmp_right(node);
 218         ir_node *conv  = NULL;
 219
 220         if(is_downconv
 221 }
 222 #endif
 223
 224 static char changed;
 225
 226 static
 227 void conv_opt_walker(ir_node *node, void *data)
 228 {
 229         ir_node *transformed;
 230         ir_node *pred;
 231         ir_mode *pred_mode;
 232         ir_mode *mode;
 233         int costs;
 234         (void) data;
 235
 236 #if 0
 237         if(is_Cmp(node)) {
 238                 try_optimize_cmp(node);
 239                 return;
 240         }
 241 #endif
 242
 243         if (!is_Conv(node))
 244                 return;
 245
 246         pred      = get_Conv_op(node);
 247         mode      = get_irn_mode(node);
 248         pred_mode = get_irn_mode(pred);
 249
 250         if (!is_Phi(pred) && !is_downconv(pred_mode, mode))
 251                 return;
 252
 253         /* - 1 for the initial conv */
 254         costs = get_conv_costs(pred, mode) - 1;
 255         DB((dbg, LEVEL_2, "Costs for %+F -> %+F: %d\n", node, pred, costs));
 256         if (costs > 0) return;
 257
 258         transformed = conv_transform(pred, mode);
 259         if (node != transformed) {
 260                 exchange(node, transformed);
 261                 changed = 1;
 262         }
 263 }
 264
 265 void conv_opt(ir_graph *irg)
 266 {
 267         char invalidate = 0;
 268         FIRM_DBG_REGISTER(dbg, "firm.opt.conv");
 269
 270         DB((dbg, LEVEL_1, "===> Performing conversion optimization on %+F\n", irg));
 271
 272         edges_assure(irg);
 273         do {
 274                 changed = 0;
 275                 irg_walk_graph(irg, NULL, conv_opt_walker, NULL);
 276                 local_optimize_graph(irg);
 277                 invalidate |= changed;
 278         } while (changed);
 279
 280         if (invalidate) {
 281                 set_irg_outs_inconsistent(irg);
 282         }
 283 }