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  */
  25 #include "config.h"
  26
  27 #include "irgmod.h"
  28 #include "ircons.h"
  29 #include "iredges.h"
  30 #include "error.h"
  31
  32 #include "benode.h"
  33 #include "bepeephole.h"
  34 #include "besched.h"
  35
  36 #include "arm_optimize.h"
  37 #include "gen_arm_regalloc_if.h"
  38 #include "gen_arm_new_nodes.h"
  39 #include "arm_nodes_attr.h"
  40 #include "arm_new_nodes.h"
  41
  42 static unsigned arm_ror(unsigned v, unsigned ror)
  43 {
  44         return (v << (32 - ror)) | (v >> ror);
  45 }
  46
  47 /*
  48  * construct 8bit values and rot amounts for a value.
  49  */
  50 void arm_gen_vals_from_word(unsigned int value, arm_vals *result)
  51 {
  52         int initial = 0;
  53
  54         /* TODO: not optimal yet, as we only "shift" the value and don't take advantage of rotations */
  55
  56         /* special case: we prefer shift amount 0 */
  57         if (value <= 0xFF) {
  58                 result->values[0] = value;
  59                 result->rors[0]   = 0;
  60                 result->ops       = 1;
  61                 return;
  62         }
  63
  64         result->ops = 0;
  65         do {
  66                 while ( (value & 0x3) == 0) {
  67                         value  >>= 2;
  68                         initial += 2;
  69                 }
  70
  71                 result->values[result->ops] = value & 0xFF;
  72                 result->rors[result->ops]   = (32-initial) % 32;
  73                 ++result->ops;
  74
  75                 value  >>= 8;
  76                 initial += 8;
  77         } while (value != 0);
  78 }
  79
  80 /**
  81  * Returns non.zero if the given offset can be directly encoded into an ARM
  82  * instruction.
  83  */
  84 static int allowed_arm_immediate(int offset, arm_vals *result)
  85 {
  86         arm_gen_vals_from_word(offset, result);
  87         return result->ops <= 1;
  88 }
  89
  90 /**
  91  * Fix an IncSP node if the offset gets too big
  92  */
  93 static void peephole_be_IncSP(ir_node *node)
  94 {
  95         ir_node  *first;
  96         ir_node  *last;
  97         ir_node  *block;
  98         int       offset;
  99         int       cnt;
 100         int       sign = 1;
 101         arm_vals  v;
 102         const ir_edge_t *edge;
 103         const ir_edge_t *next;
 104
 105         /* first optimize incsp->incsp combinations */
 106         node = be_peephole_IncSP_IncSP(node);
 107
 108         offset = be_get_IncSP_offset(node);
 109         /* can be transformed into Add OR Sub */
 110         if (offset < 0) {
 111                 sign = -1;
 112                 offset = -offset;
 113         }
 114         if (allowed_arm_immediate(offset, &v))
 115                 return;
 116
 117         be_set_IncSP_offset(node, sign * arm_ror(v.values[0], v.rors[0]));
 118
 119         first = node;
 120         block = get_nodes_block(node);
 121         for (cnt = 1; cnt < v.ops; ++cnt) {
 122                 int      value = sign * arm_ror(v.values[cnt], v.rors[cnt]);
 123                 ir_node *incsp = be_new_IncSP(&arm_registers[REG_SP], block, node,
 124                                              value, 1);
 125                 sched_add_after(node, incsp);
 126                 node = incsp;
 127         }
 128
 129         /* reattach IncSP users */
 130         last = node;
 131         node = sched_next(first);
 132         foreach_out_edge_safe(first, edge, next) {
 133                 ir_node *user = get_edge_src_irn(edge);
 134                 int      pos  = get_edge_src_pos(edge);
 135                 if (user == node)
 136                         continue;
 137                 set_irn_n(user, pos, last);
 138         }
 139 }
 140
 141 /**
 142  * creates the address by Adds
 143  */
 144 static ir_node *gen_ptr_add(ir_node *node, ir_node *frame, arm_vals *v)
 145 {
 146         dbg_info *dbgi  = get_irn_dbg_info(node);
 147         ir_node  *block = get_nodes_block(node);
 148         int     cnt;
 149         ir_node *ptr;
 150
 151         ptr = new_bd_arm_Add_imm(dbgi, block, frame, v->values[0], v->rors[0]);
 152         arch_set_irn_register(ptr, &arm_registers[REG_R12]);
 153         sched_add_before(node, ptr);
 154
 155         for (cnt = 1; cnt < v->ops; ++cnt) {
 156                 ir_node *next = new_bd_arm_Add_imm(dbgi, block, ptr, v->values[cnt],
 157                                                    v->rors[cnt]);
 158                 arch_set_irn_register(next, &arm_registers[REG_R12]);
 159                 sched_add_before(node, next);
 160                 ptr = next;
 161         }
 162         return ptr;
 163 }
 164
 165 /**
 166 * creates the address by Subs
 167 */
 168 static ir_node *gen_ptr_sub(ir_node *node, ir_node *frame, arm_vals *v)
 169 {
 170         dbg_info *dbgi  = get_irn_dbg_info(node);
 171         ir_node  *block = get_nodes_block(node);
 172         int     cnt;
 173         ir_node *ptr;
 174
 175         ptr = new_bd_arm_Sub_imm(dbgi, block, frame, v->values[0], v->rors[0]);
 176         arch_set_irn_register(ptr, &arm_registers[REG_R12]);
 177         sched_add_before(node, ptr);
 178
 179         for (cnt = 1; cnt < v->ops; ++cnt) {
 180                 ir_node *next = new_bd_arm_Sub_imm(dbgi, block, ptr, v->values[cnt],
 181                                                    v->rors[cnt]);
 182                 arch_set_irn_register(next, &arm_registers[REG_R12]);
 183                 sched_add_before(node, next);
 184                 ptr = next;
 185         }
 186         return ptr;
 187 }
 188
 189 /** fix frame addresses which are too big */
 190 static void peephole_arm_FrameAddr(ir_node *node)
 191 {
 192         arm_SymConst_attr_t *attr   = get_arm_SymConst_attr(node);
 193         int                  offset = attr->fp_offset;
 194         arm_vals             v;
 195         ir_node             *base;
 196         ir_node             *ptr;
 197
 198         if (allowed_arm_immediate(offset, &v))
 199                 return;
 200
 201         base = get_irn_n(node, n_arm_FrameAddr_base);
 202         /* TODO: suboptimal */
 203         ptr = gen_ptr_add(node, base, &v);
 204
 205         attr->fp_offset = 0;
 206         set_irn_n(node, n_arm_FrameAddr_base, ptr);
 207 }
 208
 209 /**
 210  * Fix stackpointer relative stores if the offset gets too big
 211  */
 212 static void peephole_arm_Str_Ldr(ir_node *node)
 213 {
 214         arm_load_store_attr_t *attr    = get_arm_load_store_attr(node);
 215         int                    offset  = attr->offset;
 216         int                    use_add = 1;
 217         ir_node               *ptr;
 218         arm_vals              v;
 219
 220         if (allowed_arm_immediate(offset, &v))
 221                 return;
 222
 223         /* we should only have too big offsets for frame entities */
 224         if (!attr->is_frame_entity) {
 225                 fprintf(stderr,
 226                         "POSSIBLE ARM BACKEND PROBLEM: offset in Store too big\n");
 227         }
 228         if (offset < 0) {
 229                 use_add = 0;
 230                 offset = -offset;
 231         }
 232
 233         if (is_arm_Str(node)) {
 234                 ptr = get_irn_n(node, n_arm_Str_ptr);
 235         } else {
 236                 assert(is_arm_Ldr(node));
 237                 ptr = get_irn_n(node, n_arm_Ldr_ptr);
 238         }
 239
 240         if (use_add) {
 241                 ptr = gen_ptr_add(node, ptr, &v);
 242         } else {
 243                 ptr = gen_ptr_sub(node, ptr, &v);
 244         }
 245
 246         /* TODO: sub-optimal, the last offset could probably be left inside the
 247            store */
 248         if (is_arm_Str(node)) {
 249                 set_irn_n(node, n_arm_Str_ptr, ptr);
 250         } else {
 251                 assert(is_arm_Ldr(node));
 252                 set_irn_n(node, n_arm_Ldr_ptr, ptr);
 253         }
 254         attr->offset = 0;
 255 }
 256
 257 /**
 258  * Register a peephole optimization function.
 259  */
 260 static void register_peephole_optimisation(ir_op *op, peephole_opt_func func)
 261 {
 262         assert(op->ops.generic == NULL);
 263         op->ops.generic = (op_func)func;
 264 }
 265
 266 /* Perform peephole-optimizations. */
 267 void arm_peephole_optimization(ir_graph *irg)
 268 {
 269         /* register peephole optimizations */
 270         clear_irp_opcodes_generic_func();
 271         register_peephole_optimisation(op_be_IncSP,      peephole_be_IncSP);
 272         register_peephole_optimisation(op_arm_Str,       peephole_arm_Str_Ldr);
 273         register_peephole_optimisation(op_arm_Ldr,       peephole_arm_Str_Ldr);
 274         register_peephole_optimisation(op_arm_FrameAddr, peephole_arm_FrameAddr);
 275
 276         be_peephole_opt(irg);
 277 }