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

   1 /*
   2  * Copyright (C) 1995-2011 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 #include "config.h"
  40
  41 #include "iroptimize.h"
  42
  43 #include <assert.h>
  44 #include <stdbool.h>
  45 #include "debug.h"
  46 #include "ircons.h"
  47 #include "irgmod.h"
  48 #include "irgopt.h"
  49 #include "irnode_t.h"
  50 #include "iropt_t.h"
  51 #include "iredges_t.h"
  52 #include "irgwalk.h"
  53 #include "irprintf.h"
  54 #include "irpass_t.h"
  55 #include "tv.h"
  56 #include "vrp.h"
  57 #include "opt_manage.h"
  58
  59 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
  60
  61 static inline int imin(int a, int b) { return a < b ? a : b; }
  62
  63 static bool is_optimizable_node(const ir_node *node, ir_mode *dest_mode)
  64 {
  65         switch (get_irn_opcode(node)) {
  66         case iro_Add:
  67         case iro_And:
  68         case iro_Eor:
  69         case iro_Minus:
  70         case iro_Mul:
  71         case iro_Not:
  72         case iro_Or:
  73         case iro_Phi:
  74         case iro_Sub:
  75                 return true;
  76         case iro_Shl: {
  77                 int modulo_shift = get_mode_modulo_shift(dest_mode);
  78                 int old_shift    = get_mode_modulo_shift(get_irn_mode(node));
  79                 /* bail out if modulo shift changes */
  80                 if (modulo_shift != old_shift)
  81                         return false;
  82                 return true;
  83         }
  84
  85         default:
  86                 return false;
  87         }
  88 }
  89
  90 static ir_tarval* conv_const_tv(const ir_node* cnst, ir_mode* dest_mode)
  91 {
  92         return tarval_convert_to(get_Const_tarval(cnst), dest_mode);
  93 }
  94
  95 static int is_downconv(ir_mode *src_mode, ir_mode *dest_mode)
  96 {
  97         return
  98                 mode_is_int(src_mode) &&
  99                 mode_is_int(dest_mode) &&
 100                 get_mode_size_bits(dest_mode) <= get_mode_size_bits(src_mode);
 101 }
 102
 103 static int get_conv_costs(const ir_node *node, ir_mode *dest_mode)
 104 {
 105         ir_mode *mode = get_irn_mode(node);
 106         int arity;
 107         int i;
 108         int costs;
 109
 110         if (mode == dest_mode)
 111                 return 0;
 112
 113         if (is_Const(node)) {
 114                 /* TODO tarval module is incomplete and can't convert floats to ints */
 115                 return conv_const_tv(node, dest_mode) == tarval_bad ? 1 : 0;
 116         }
 117
 118         if (is_Conv(node) &&
 119                         is_downconv(mode, dest_mode) &&
 120                         get_irn_mode(get_Conv_op(node)) == dest_mode) {
 121                 return -1;
 122         }
 123
 124         if (get_irn_n_edges(node) > 1) {
 125                 DB((dbg, LEVEL_3, "multi outs at %+F\n", node));
 126                 return 1;
 127         }
 128
 129         if (ir_zero_when_converted(node, dest_mode)) {
 130                 return -1;
 131         }
 132
 133 #if 0 // TODO
 134         /* Take the minimum of the conversion costs for Phi predecessors as only one
 135          * branch is actually executed at a time */
 136         if (is_Phi(node)) {
 137                 int i;
 138                 int arity = get_Phi_n_preds(node);
 139                 int costs;
 140
 141                 costs = get_conv_costs(get_Phi_pred(node, 0), dest_mode);
 142                 for (i = 1; i < arity; ++i) {
 143                         ir_node *pred = get_Phi_pred(node, i);
 144                         int c = get_conv_costs(pred, dest_mode);
 145                         if (c < costs) costs = c;
 146                 }
 147
 148                 return costs;
 149         }
 150 #endif
 151
 152         if (!is_downconv(mode, dest_mode)) {
 153                 return 1;
 154         }
 155
 156         if (is_Conv(node)) {
 157                 ir_node *pred      = get_Conv_op(node);
 158                 ir_mode *pred_mode = get_irn_mode(pred);
 159
 160                 if (!values_in_mode(dest_mode, pred_mode)) {
 161                         return 1;
 162                 }
 163                 return get_conv_costs(get_Conv_op(node), dest_mode) - 1;
 164         }
 165
 166         if (!is_optimizable_node(node, dest_mode)) {
 167                 return 1;
 168         }
 169
 170         costs = 0;
 171         // The shift count does not participate in the conv optimisation
 172         arity = is_Shl(node) ? 1 : get_irn_arity(node);
 173         for (i = 0; i < arity; ++i) {
 174                 ir_node *pred = get_irn_n(node, i);
 175                 costs += imin(get_conv_costs(pred, dest_mode), 1);
 176         }
 177
 178         return costs;
 179 }
 180
 181 static ir_node *place_conv(ir_node *node, ir_mode *dest_mode)
 182 {
 183         ir_node *block = get_nodes_block(node);
 184         ir_node *conv = new_r_Conv(block, node, dest_mode);
 185         return conv;
 186 }
 187
 188 static ir_node *conv_transform(ir_node *node, ir_mode *dest_mode)
 189 {
 190         ir_mode  *mode = get_irn_mode(node);
 191         ir_graph *irg  = get_irn_irg(node);
 192         int       arity;
 193         int       conv_arity;
 194         int       i;
 195         ir_node  *new_node;
 196         ir_node **ins;
 197
 198         if (mode == dest_mode)
 199                 return node;
 200
 201         if (is_Const(node)) {
 202                 /* TODO tarval module is incomplete and can't convert floats to ints */
 203                 ir_tarval *tv = conv_const_tv(node, dest_mode);
 204                 if (tv == tarval_bad) {
 205                         return place_conv(node, dest_mode);
 206                 } else {
 207                         return new_r_Const(irg, tv);
 208                 }
 209         }
 210
 211         if (is_Conv(node) &&
 212                         is_downconv(mode, dest_mode) &&
 213                         get_irn_mode(get_Conv_op(node)) == dest_mode) {
 214                 return get_Conv_op(node);
 215         }
 216
 217         if (get_irn_n_edges(node) > 1) {
 218                 return place_conv(node, dest_mode);
 219         }
 220
 221         if (!is_downconv(mode, dest_mode)) {
 222                 return place_conv(node, dest_mode);
 223         }
 224
 225         if (is_Conv(node)) {
 226                 ir_node *pred      = get_Conv_op(node);
 227                 ir_mode *pred_mode = get_irn_mode(pred);
 228
 229                 if (!values_in_mode(dest_mode, pred_mode)) {
 230                         return place_conv(node, dest_mode);
 231                 }
 232                 return conv_transform(get_Conv_op(node), dest_mode);
 233         }
 234
 235         if (!is_optimizable_node(node, dest_mode)) {
 236                 return place_conv(node, dest_mode);
 237         }
 238
 239         // We want to create a new node with the right mode
 240         arity = get_irn_arity(node);
 241         ins = ALLOCAN(ir_node *, arity);
 242
 243         // The shift count does not participate in the conv optimisation
 244         conv_arity = is_Shl(node) ? 1 : arity;
 245         for (i = 0; i < conv_arity; i++) {
 246                 ir_node *pred = get_irn_n(node, i);
 247                 ir_node *transformed;
 248                 if (get_conv_costs(pred, dest_mode) > 0) {
 249                         transformed = place_conv(pred, dest_mode);
 250                 } else {
 251                         transformed = conv_transform(pred, dest_mode);
 252                 }
 253                 ins[i] = transformed;
 254         }
 255
 256         for (i = conv_arity; i < arity; i++) {
 257                 ins[i] = get_irn_n(node, i);
 258         }
 259
 260         new_node = new_ir_node(get_irn_dbg_info(node),
 261                                 irg,
 262                                 get_nodes_block(node),
 263                                 get_irn_op(node),
 264                                 dest_mode,
 265                                 arity,
 266                                 ins);
 267         copy_node_attr(irg, node, new_node);
 268
 269         return new_node;
 270 }
 271
 272 static void conv_opt_walker(ir_node *node, void *data)
 273 {
 274         ir_node *transformed;
 275         ir_node *pred;
 276         ir_mode *pred_mode;
 277         ir_mode *mode;
 278         int costs;
 279         bool *changed = (bool*)data;
 280
 281         if (!is_Conv(node))
 282                 return;
 283
 284         pred      = get_Conv_op(node);
 285         mode      = get_irn_mode(node);
 286         pred_mode = get_irn_mode(pred);
 287
 288         if (mode_is_reference(mode) || mode_is_reference(pred_mode))
 289                 return;
 290
 291         if (!is_Phi(pred) && !is_downconv(pred_mode, mode))
 292                 return;
 293
 294         /* - 1 for the initial conv */
 295         costs = get_conv_costs(pred, mode) - 1;
 296         DB((dbg, LEVEL_2, "Costs for %+F -> %+F: %d\n", node, pred, costs));
 297         if (costs > 0)
 298                 return;
 299
 300         transformed = conv_transform(pred, mode);
 301         if (node != transformed) {
 302                 vrp_attr *vrp;
 303
 304                 exchange(node, transformed);
 305                 vrp = vrp_get_info(transformed);
 306                 if (vrp && vrp->valid) {
 307                         vrp->range_type = VRP_VARYING;
 308                         vrp->bits_set = tarval_convert_to(vrp->bits_set, mode);
 309                         vrp->bits_not_set = tarval_convert_to(vrp->bits_not_set, mode);
 310                 }
 311
 312                 *changed = true;
 313         }
 314 }
 315
 316 static ir_graph_state_t do_deconv(ir_graph *irg)
 317 {
 318         bool changed;
 319         FIRM_DBG_REGISTER(dbg, "firm.opt.conv");
 320
 321         DB((dbg, LEVEL_1, "===> Performing conversion optimization on %+F\n", irg));
 322
 323         do {
 324                 changed = false;
 325                 irg_walk_graph(irg, NULL, conv_opt_walker, &changed);
 326                 local_optimize_graph(irg);
 327         } while (changed);
 328
 329         return 0;
 330 }
 331
 332 optdesc_t opt_deconv = {
 333         "deconv",
 334         IR_GRAPH_STATE_CONSISTENT_OUT_EDGES,
 335         do_deconv,
 336 };
 337
 338 int conv_opt(ir_graph *irg)
 339 {
 340         perform_irg_optimization(irg, &opt_deconv);
 341         return 1;
 342 }
 343
 344 /* Creates an ir_graph pass for conv_opt. */
 345 ir_graph_pass_t *conv_opt_pass(const char *name)
 346 {
 347         ir_graph_pass_t *path = def_graph_pass_ret(name ? name : "conv_opt", conv_opt);
 348
 349         /* safe to run parallel on all irgs */
 350         ir_graph_pass_set_parallel(path, 1);
 351
 352         return path;
 353 }