nsz Git - libfirm/blob - ir/be/arm/arm_optimize.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       Implements several optimizations for ARM.
  23  * @author      Michael Beck
  24  * @version     $Id: $
  25  */
  26 #ifdef HAVE_CONFIG_H
  27 #include "config.h"
  28 #endif
  29
  30 #include "irgmod.h"
  31 #include "ircons.h"
  32 #include "error.h"
  33
  34 #include "benode_t.h"
  35 #include "bepeephole.h"
  36 #include "besched.h"
  37
  38 #include "arm_optimize.h"
  39 #include "gen_arm_regalloc_if.h"
  40 #include "gen_arm_new_nodes.h"
  41
  42 static const arch_env_t *arch_env;
  43 static arm_code_gen_t  *cg;
  44
  45 /** Execute ARM ROL. */
  46 static unsigned arm_rol(unsigned v, unsigned rol) {
  47         return (v << rol) | (v >> (32 - rol));
  48 }
  49
  50 /*
  51  * construct 8bit values and rot amounts for a value.
  52  */
  53 void arm_gen_vals_from_word(unsigned int value, arm_vals *result)
  54 {
  55         int initial = 0;
  56
  57         memset(result, 0, sizeof(*result));
  58
  59         /* special case: we prefer shift amount 0 */
  60         if (value < 0x100) {
  61                 result->values[0] = value;
  62                 result->ops       = 1;
  63                 return;
  64         }
  65
  66         while (value != 0) {
  67                 if (value & 0xFF) {
  68                         unsigned v = arm_rol(value, 8) & 0xFFFFFF;
  69                         int shf = 0;
  70                         for (;;) {
  71                                 if ((v & 3) != 0)
  72                                         break;
  73                                 shf += 2;
  74                                 v >>= 2;
  75                         }
  76                         v  &= 0xFF;
  77                         shf = (initial + shf - 8) & 0x1F;
  78                         result->values[result->ops] = v;
  79                         result->shifts[result->ops] = shf;
  80                         ++result->ops;
  81
  82                         value ^= arm_rol(v, shf) >> initial;
  83                 }
  84                 else {
  85                         value >>= 8;
  86                         initial += 8;
  87                 }
  88         }
  89 }
  90
  91 /**
  92  * Encodes an immediate with shifter operand
  93  */
  94 unsigned int arm_encode_imm_w_shift(unsigned int shift, unsigned int immediate) {
  95         return immediate | ((shift>>1)<<8);
  96 }
  97
  98 /**
  99  * Decode an immediate with shifter operand
 100  */
 101 unsigned int arm_decode_imm_w_shift(long imm_value) {
 102         unsigned l = (unsigned)imm_value;
 103         unsigned rol = (l & ~0xFF) >> 7;
 104
 105         return arm_rol(l & 0xFF, rol);
 106 }
 107
 108 /**
 109  * Creates a Mov node.
 110  */
 111 static ir_node *create_mov_node(ir_node *sched_point, dbg_info *dbg, ir_node *block, long value) {
 112         ir_graph *irg = current_ir_graph;
 113         ir_node  *mov;
 114
 115         mov = new_rd_arm_Mov_i(dbg, irg, block, mode_Iu, value);
 116         arch_set_irn_register(arch_env, mov, &arm_gp_regs[REG_R12]);
 117         sched_add_before(sched_point, mov);
 118         return mov;
 119 }
 120
 121 /**
 122  * Creates a Mvn node.
 123  */
 124 static ir_node *create_mvn_node(ir_node *sched_point, dbg_info *dbg, ir_node *block, long value) {
 125         ir_graph *irg = current_ir_graph;
 126         ir_node  *mvn;
 127
 128         mvn = new_rd_arm_Mvn_i(dbg, irg, block, mode_Iu, value);
 129         arch_set_irn_register(arch_env, mvn, &arm_gp_regs[REG_R12]);
 130         sched_add_before(sched_point, mvn);
 131         return mvn;
 132 }
 133
 134 /**
 135  * Creates a possible DAG for an constant and schedule it before
 136  * the node sched_point.
 137  * The Dag deliveres it's result in register R12.
 138  */
 139 static ir_node *create_const_graph_value(ir_node *sched_point, unsigned int value) {
 140         dbg_info *dbg;
 141         ir_node  *block, *result;
 142         arm_vals v, vn;
 143         int      cnt;
 144
 145         arm_gen_vals_from_word(value, &v);
 146         arm_gen_vals_from_word(~value, &vn);
 147
 148         dbg   = get_irn_dbg_info(sched_point);
 149         block = get_nodes_block(sched_point);
 150
 151         if (vn.ops < v.ops) {
 152                 /* remove bits */
 153                 result = create_mvn_node(sched_point, dbg, block, arm_encode_imm_w_shift(vn.shifts[0], vn.values[0]));
 154
 155                 for (cnt = 1; cnt < vn.ops; ++cnt) {
 156                         long value = arm_encode_imm_w_shift(vn.shifts[cnt], vn.values[cnt]);
 157                         ir_node *bic_i_node = new_rd_arm_Bic_i(dbg, current_ir_graph, block, result, mode_Iu, value);
 158                         arch_set_irn_register(arch_env, bic_i_node, &arm_gp_regs[REG_R12]);
 159                         sched_add_before(sched_point, bic_i_node);
 160                         result = bic_i_node;
 161                 }
 162         }
 163         else {
 164                 /* add bits */
 165                 result = create_mov_node(sched_point,  dbg, block, arm_encode_imm_w_shift(v.shifts[0], v.values[0]));
 166
 167                 for (cnt = 1; cnt < v.ops; ++cnt) {
 168                         long value = arm_encode_imm_w_shift(v.shifts[cnt], v.values[cnt]);
 169                         ir_node *orr_i_node = new_rd_arm_Or_i(dbg, current_ir_graph, block, result, mode_Iu, value);
 170                         arch_set_irn_register(arch_env, orr_i_node, &arm_gp_regs[REG_R12]);
 171                         sched_add_before(sched_point, orr_i_node);
 172                         result = orr_i_node;
 173                 }
 174         }
 175         return result;
 176 }
 177
 178
 179 /**
 180  * Returns non.zero if the given offset can be directly encoded into an ARM instruction.
 181  */
 182 static int allowed_arm_immediate(int offset, arm_vals *result) {
 183         arm_gen_vals_from_word(offset, result);
 184         return result->ops <= 1;
 185 }
 186
 187 /**
 188  * Fix an IncSP node if the offset gets too big
 189  */
 190 static void peephole_be_IncSP(ir_node *node) {
 191         ir_graph *irg;
 192         ir_node  *block;
 193         int      offset, cnt, align, sign = 1;
 194         arm_vals v;
 195
 196         /* first optimize incsp->incsp combinations */
 197         be_peephole_IncSP_IncSP(node);
 198
 199         offset = be_get_IncSP_offset(node);
 200         /* can be transformed into Add OR Sub */
 201         if (offset < 0) {
 202                 sign = -1;
 203                 offset = -offset;
 204         }
 205         if (allowed_arm_immediate(offset, &v))
 206                 return;
 207
 208         be_set_IncSP_offset(node, (int)arm_encode_imm_w_shift(v.shifts[0], v.values[0]) * sign);
 209
 210         irg   = current_ir_graph;
 211         block = get_nodes_block(node);
 212         align = be_get_IncSP_align(node);
 213         for (cnt = 1; cnt < v.ops; ++cnt) {
 214                 int value = (int)arm_encode_imm_w_shift(v.shifts[cnt], v.values[cnt]);
 215                 ir_node *next = be_new_IncSP(&arm_gp_regs[REG_SP], irg, block, node, value * sign, align);
 216                 sched_add_after(node, next);
 217                 node = next;
 218         }
 219 }
 220
 221 /**
 222  * creates the address by Adds
 223  */
 224 static ir_node *gen_ptr_add(ir_node *node, ir_node *frame, arm_vals *v)
 225 {
 226         ir_graph *irg   = current_ir_graph;
 227         dbg_info *dbg   = get_irn_dbg_info(node);
 228         ir_node  *block = get_nodes_block(node);
 229         int     cnt;
 230         ir_node *ptr;
 231
 232         ptr = new_rd_arm_Add_i(dbg, irg, block, frame, mode_Iu, arm_encode_imm_w_shift(v->shifts[0], v->values[0]));
 233         arch_set_irn_register(arch_env, ptr, &arm_gp_regs[REG_R12]);
 234         sched_add_before(node, ptr);
 235
 236         for (cnt = 1; cnt < v->ops; ++cnt) {
 237                 long value = arm_encode_imm_w_shift(v->shifts[cnt], v->values[cnt]);
 238                 ir_node *next = new_rd_arm_Add_i(dbg, irg, block, ptr, mode_Iu, value);
 239                 arch_set_irn_register(arch_env, next, &arm_gp_regs[REG_R12]);
 240                 sched_add_before(node, next);
 241                 ptr = next;
 242         }
 243         return ptr;
 244 }
 245
 246 /**
 247 * creates the address by Subs
 248 */
 249 static ir_node *gen_ptr_sub(ir_node *node, ir_node *frame, arm_vals *v)
 250 {
 251         ir_graph *irg   = current_ir_graph;
 252         dbg_info *dbg   = get_irn_dbg_info(node);
 253         ir_node  *block = get_nodes_block(node);
 254         int     cnt;
 255         ir_node *ptr;
 256
 257         ptr = new_rd_arm_Sub_i(dbg, irg, block, frame, mode_Iu, arm_encode_imm_w_shift(v->shifts[0], v->values[0]));
 258         arch_set_irn_register(arch_env, ptr, &arm_gp_regs[REG_R12]);
 259         sched_add_before(node, ptr);
 260
 261         for (cnt = 1; cnt < v->ops; ++cnt) {
 262                 long value = arm_encode_imm_w_shift(v->shifts[cnt], v->values[cnt]);
 263                 ir_node *next = new_rd_arm_Sub_i(dbg, irg, block, ptr, mode_Iu, value);
 264                 arch_set_irn_register(arch_env, next, &arm_gp_regs[REG_R12]);
 265                 sched_add_before(node, next);
 266                 ptr = next;
 267         }
 268         return ptr;
 269 }
 270
 271 /**
 272  * Fix an be_Spill node if the offset gets too big
 273  */
 274 static void peephole_be_Spill(ir_node *node) {
 275         ir_entity *ent   = be_get_frame_entity(node);
 276         int       use_add = 1, offset = get_entity_offset(ent);
 277         ir_node   *block, *ptr, *frame, *value, *store;
 278         ir_mode   *mode;
 279         dbg_info  *dbg;
 280         ir_graph  *irg;
 281         arm_vals  v;
 282
 283         if (allowed_arm_immediate(offset, &v))
 284                 return;
 285         if (offset < 0) {
 286                 use_add = 0;
 287                 offset = -offset;
 288         }
 289
 290         frame = be_get_Spill_frame(node);
 291         if (use_add) {
 292                 ptr = gen_ptr_add(node, frame, &v);
 293         } else {
 294                 ptr = gen_ptr_sub(node, frame, &v);
 295         }
 296
 297         value = be_get_Spill_val(node);
 298         mode  = get_irn_mode(value);
 299         irg   = current_ir_graph;
 300         dbg   = get_irn_dbg_info(node);
 301         block = get_nodes_block(node);
 302
 303         if (mode_is_float(mode)) {
 304                 if (USE_FPA(cg->isa)) {
 305                         /* transform into fpaStf */
 306                         store = new_rd_arm_fpaStf(dbg, irg, block, ptr, value, get_irg_no_mem(irg), mode);
 307                         sched_add_before(node, store);
 308                 } else {
 309                         panic("peephole_be_Spill: spill not supported for this mode");
 310                 }
 311         } else if (mode_is_dataM(mode)) {
 312                  /* transform into Store */;
 313                  store = new_rd_arm_Store(dbg, irg, block, ptr, value, get_irg_no_mem(irg));
 314                  sched_add_before(node, store);
 315         } else {
 316                 panic("peephole_be_Spill: spill not supported for this mode");
 317         }
 318
 319         be_peephole_before_exchange(node, store);
 320         sched_remove(node);
 321         exchange(node, store);
 322         be_peephole_after_exchange(store);
 323 }
 324
 325 /**
 326  * Fix an be_Reload node if the offset gets too big
 327  */
 328 static void peephole_be_Reload(ir_node *node) {
 329         ir_entity *ent   = be_get_frame_entity(node);
 330         int       use_add = 1, offset = get_entity_offset(ent);
 331         ir_node   *block, *ptr, *frame, *load, *mem, *proj;
 332         ir_mode   *mode;
 333         dbg_info  *dbg;
 334         ir_graph  *irg;
 335         arm_vals  v;
 336         const arch_register_t *reg;
 337
 338         if (allowed_arm_immediate(offset, &v))
 339                 return;
 340         if (offset < 0) {
 341                 use_add = 0;
 342                 offset = -offset;
 343         }
 344
 345         frame = be_get_Reload_frame(node);
 346         if (use_add) {
 347                 ptr = gen_ptr_add(node, frame, &v);
 348         } else {
 349                 ptr = gen_ptr_sub(node, frame, &v);
 350         }
 351
 352         reg   = arch_get_irn_register(arch_env, node);
 353         mem   = be_get_Reload_mem(node);
 354         mode  = get_irn_mode(node);
 355         irg   = current_ir_graph;
 356         dbg   = get_irn_dbg_info(node);
 357         block = get_nodes_block(node);
 358
 359         if (mode_is_float(mode)) {
 360                 if (USE_FPA(cg->isa)) {
 361                         /* transform into fpaLdf */
 362                         load = new_rd_arm_fpaLdf(dbg, irg, block, ptr, mem, mode);
 363                         sched_add_before(node, load);
 364                         proj = new_rd_Proj(dbg, irg, block, load, mode, pn_arm_fpaLdf_res);
 365                         arch_set_irn_register(arch_env, proj, reg);
 366                 } else {
 367                         panic("peephole_be_Spill: spill not supported for this mode");
 368                 }
 369         } else if (mode_is_dataM(mode)) {
 370                 /* transform into Store */;
 371                 load = new_rd_arm_Load(dbg, irg, block, ptr, mem);
 372                 sched_add_before(node, load);
 373                 proj = new_rd_Proj(dbg, irg, block, load, mode_Iu, pn_arm_Load_res);
 374                 arch_set_irn_register(arch_env, proj, reg);
 375         } else {
 376                 panic("peephole_be_Spill: spill not supported for this mode");
 377         }
 378
 379         be_peephole_before_exchange(node, proj);
 380         sched_remove(node);
 381         exchange(node, proj);
 382         be_peephole_after_exchange(proj);
 383 }
 384
 385 /**
 386  * Register a peephole optimization function.
 387  */
 388 static void register_peephole_optimisation(ir_op *op, peephole_opt_func func) {
 389         assert(op->ops.generic == NULL);
 390         op->ops.generic = (op_func)func;
 391 }
 392
 393 /* Perform peephole-optimizations. */
 394 void arm_peephole_optimization(arm_code_gen_t *new_cg)
 395 {
 396         cg       = new_cg;
 397         arch_env = cg->arch_env;
 398
 399         /* register peephole optimizations */
 400         clear_irp_opcodes_generic_func();
 401         register_peephole_optimisation(op_be_IncSP, peephole_be_IncSP);
 402         register_peephole_optimisation(op_be_Spill, peephole_be_Spill);
 403         register_peephole_optimisation(op_be_Reload, peephole_be_Reload);
 404
 405         be_peephole_opt(cg->birg);
 406 }