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

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief   conv node optimisation
   9  * @author  Matthias Braun, Christoph Mallon
  10  *
  11  * Try to minimize the number of conv nodes by changing modes of operations.
  12  * The typical example is the following structure:
  13  *    (some node mode_Hs)
  14  *            |                                       (some node_Hs)
  15  *         Conv Is                                          |
  16  *            |                                          Add Hs
  17  *          Add Is            gets transformed to           |
  18  *            |
  19  *         Conv Hs
  20  *
  21  * TODO: * try to optimize cmp modes
  22  *       * decide when it is useful to move the convs through phis
  23  */
  24 #include "config.h"
  25
  26 #include "iroptimize.h"
  27
  28 #include <assert.h>
  29 #include <stdbool.h>
  30 #include "debug.h"
  31 #include "ircons.h"
  32 #include "irgmod.h"
  33 #include "irgopt.h"
  34 #include "irnode_t.h"
  35 #include "iropt_t.h"
  36 #include "iredges_t.h"
  37 #include "irgwalk.h"
  38 #include "irprintf.h"
  39 #include "irpass_t.h"
  40 #include "tv.h"
  41 #include "vrp.h"
  42
  43 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
  44
  45 static inline int imin(int a, int b) { return a < b ? a : b; }
  46
  47 static bool is_optimizable_node(const ir_node *node, ir_mode *dest_mode)
  48 {
  49         switch (get_irn_opcode(node)) {
  50         case iro_Minus:
  51         case iro_Phi:
  52         case iro_And:
  53         case iro_Eor:
  54         case iro_Or:
  55         case iro_Not:
  56                 return true;
  57         case iro_Add:
  58         case iro_Mul:
  59         case iro_Sub:
  60                 if (mode_is_float(get_irn_mode(node)))
  61                         return false;
  62                 return true;
  63         case iro_Shl: {
  64                 int modulo_shift = get_mode_modulo_shift(dest_mode);
  65                 int old_shift    = get_mode_modulo_shift(get_irn_mode(node));
  66                 /* bail out if modulo shift changes */
  67                 if (modulo_shift != old_shift)
  68                         return false;
  69                 return true;
  70         }
  71
  72         default:
  73                 return false;
  74         }
  75 }
  76
  77 static ir_tarval* conv_const_tv(const ir_node* cnst, ir_mode* dest_mode)
  78 {
  79         return tarval_convert_to(get_Const_tarval(cnst), dest_mode);
  80 }
  81
  82 static bool is_downconv(ir_mode *src_mode, ir_mode *dest_mode)
  83 {
  84         return ((mode_is_int(src_mode) && mode_is_int(dest_mode))
  85                 || (mode_is_float(src_mode) && mode_is_float(dest_mode)))
  86                 && get_mode_size_bits(dest_mode) <= get_mode_size_bits(src_mode);
  87 }
  88
  89 static int get_conv_costs(const ir_node *node, ir_mode *dest_mode)
  90 {
  91         ir_mode *mode = get_irn_mode(node);
  92         int arity;
  93         int i;
  94         int costs;
  95
  96         if (mode == dest_mode)
  97                 return 0;
  98
  99         if (is_Const(node)) {
 100                 return conv_const_tv(node, dest_mode) == tarval_bad ? 1 : 0;
 101         }
 102
 103         if (is_Conv(node) &&
 104                         is_downconv(mode, dest_mode) &&
 105                         get_irn_mode(get_Conv_op(node)) == dest_mode) {
 106                 return -1;
 107         }
 108
 109         if (get_irn_n_edges(node) > 1) {
 110                 DB((dbg, LEVEL_3, "multi outs at %+F\n", node));
 111                 return 1;
 112         }
 113
 114         if (ir_zero_when_converted(node, dest_mode)) {
 115                 return -1;
 116         }
 117
 118         /* TODO: Phi nodes */
 119
 120         if (!is_downconv(mode, dest_mode)) {
 121                 return 1;
 122         }
 123
 124         if (is_Conv(node)) {
 125                 ir_node *pred      = get_Conv_op(node);
 126                 ir_mode *pred_mode = get_irn_mode(pred);
 127
 128                 if (smaller_mode(pred_mode, dest_mode)) {
 129                         return get_conv_costs(get_Conv_op(node), dest_mode) - 1;
 130                 }
 131                 if (may_leave_out_middle_conv(pred_mode, mode, dest_mode)) {
 132                         return 0;
 133                 } else {
 134                         return 1;
 135                 }
 136         }
 137
 138         if (!is_optimizable_node(node, dest_mode)) {
 139                 return 1;
 140         }
 141
 142         costs = 0;
 143         // The shift count does not participate in the conv optimisation
 144         arity = is_Shl(node) ? 1 : get_irn_arity(node);
 145         for (i = 0; i < arity; ++i) {
 146                 ir_node *pred = get_irn_n(node, i);
 147                 costs += imin(get_conv_costs(pred, dest_mode), 1);
 148         }
 149
 150         return costs;
 151 }
 152
 153 static ir_node *place_conv(ir_node *node, ir_mode *dest_mode)
 154 {
 155         ir_node *block = get_nodes_block(node);
 156         ir_node *conv = new_r_Conv(block, node, dest_mode);
 157         return conv;
 158 }
 159
 160 static ir_node *conv_transform(ir_node *node, ir_mode *dest_mode)
 161 {
 162         ir_mode  *mode = get_irn_mode(node);
 163         ir_graph *irg  = get_irn_irg(node);
 164         int       arity;
 165         int       conv_arity;
 166         int       i;
 167         ir_node  *new_node;
 168         ir_node **ins;
 169
 170         if (mode == dest_mode)
 171                 return node;
 172
 173         if (is_Const(node)) {
 174                 ir_tarval *tv = conv_const_tv(node, dest_mode);
 175                 if (tv == tarval_bad) {
 176                         return place_conv(node, dest_mode);
 177                 } else {
 178                         return new_r_Const(irg, tv);
 179                 }
 180         }
 181
 182         if (is_Conv(node) &&
 183                         is_downconv(mode, dest_mode) &&
 184                         get_irn_mode(get_Conv_op(node)) == dest_mode) {
 185                 return get_Conv_op(node);
 186         }
 187
 188         if (get_irn_n_edges(node) > 1) {
 189                 return place_conv(node, dest_mode);
 190         }
 191
 192         if (!is_downconv(mode, dest_mode)) {
 193                 return place_conv(node, dest_mode);
 194         }
 195
 196         if (is_Conv(node)) {
 197                 ir_node *pred      = get_Conv_op(node);
 198                 ir_mode *pred_mode = get_irn_mode(pred);
 199
 200                 if (smaller_mode(pred_mode, dest_mode)) {
 201                         return conv_transform(get_Conv_op(node), dest_mode);
 202                 }
 203                 return place_conv(node, dest_mode);
 204         }
 205
 206         if (!is_optimizable_node(node, dest_mode)) {
 207                 return place_conv(node, dest_mode);
 208         }
 209
 210         // We want to create a new node with the right mode
 211         arity = get_irn_arity(node);
 212         ins = ALLOCAN(ir_node *, arity);
 213
 214         // The shift count does not participate in the conv optimisation
 215         conv_arity = is_Shl(node) ? 1 : arity;
 216         for (i = 0; i < conv_arity; i++) {
 217                 ir_node *pred = get_irn_n(node, i);
 218                 ir_node *transformed;
 219                 if (get_conv_costs(pred, dest_mode) > 0) {
 220                         transformed = place_conv(pred, dest_mode);
 221                 } else {
 222                         transformed = conv_transform(pred, dest_mode);
 223                 }
 224                 ins[i] = transformed;
 225         }
 226
 227         for (i = conv_arity; i < arity; i++) {
 228                 ins[i] = get_irn_n(node, i);
 229         }
 230
 231         new_node = new_ir_node(get_irn_dbg_info(node),
 232                                 irg,
 233                                 get_nodes_block(node),
 234                                 get_irn_op(node),
 235                                 dest_mode,
 236                                 arity,
 237                                 ins);
 238         copy_node_attr(irg, node, new_node);
 239
 240         return new_node;
 241 }
 242
 243 static void conv_opt_walker(ir_node *node, void *data)
 244 {
 245         ir_node *transformed;
 246         ir_node *pred;
 247         ir_mode *pred_mode;
 248         ir_mode *mode;
 249         int costs;
 250         bool *changed = (bool*)data;
 251
 252         if (!is_Conv(node))
 253                 return;
 254
 255         pred      = get_Conv_op(node);
 256         mode      = get_irn_mode(node);
 257         pred_mode = get_irn_mode(pred);
 258
 259         if (mode_is_reference(mode) || mode_is_reference(pred_mode))
 260                 return;
 261
 262         if (!is_Phi(pred) && !is_downconv(pred_mode, mode))
 263                 return;
 264
 265         /* - 1 for the initial conv */
 266         costs = get_conv_costs(pred, mode) - 1;
 267         DB((dbg, LEVEL_2, "Costs for %+F -> %+F: %d\n", node, pred, costs));
 268         if (costs > 0)
 269                 return;
 270
 271         transformed = conv_transform(pred, mode);
 272         if (node != transformed) {
 273                 exchange(node, transformed);
 274                 *changed = true;
 275         }
 276 }
 277
 278 void conv_opt(ir_graph *irg)
 279 {
 280         bool global_changed = false;
 281         bool changed;
 282         FIRM_DBG_REGISTER(dbg, "firm.opt.conv");
 283
 284         assure_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES);
 285
 286         DB((dbg, LEVEL_1, "===> Performing conversion optimization on %+F\n", irg));
 287
 288         do {
 289                 changed = false;
 290                 irg_walk_graph(irg, NULL, conv_opt_walker, &changed);
 291                 local_optimize_graph(irg);
 292                 global_changed |= changed;
 293         } while (changed);
 294
 295         confirm_irg_properties(irg,
 296                 global_changed ? IR_GRAPH_PROPERTIES_NONE : IR_GRAPH_PROPERTIES_ALL);
 297 }
 298
 299 /* Creates an ir_graph pass for conv_opt. */
 300 ir_graph_pass_t *conv_opt_pass(const char *name)
 301 {
 302         ir_graph_pass_t *path = def_graph_pass(name ? name : "conv_opt", conv_opt);
 303
 304         /* safe to run parallel on all irgs */
 305         ir_graph_pass_set_parallel(path, 1);
 306
 307         return path;
 308 }