nsz Git - libfirm/blob - ir/be/bepeephole.c

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief       Peephole optimisation framework keeps track of which registers contain which values
   9  * @author      Matthias Braun
  10  */
  11 #include "config.h"
  12
  13 #include "array_t.h"
  14 #include "bepeephole.h"
  15
  16 #include "iredges_t.h"
  17 #include "irgwalk.h"
  18 #include "irprintf.h"
  19 #include "ircons.h"
  20 #include "irgmod.h"
  21 #include "heights.h"
  22 #include "error.h"
  23
  24 #include "beirg.h"
  25 #include "belive_t.h"
  26 #include "bearch.h"
  27 #include "beintlive_t.h"
  28 #include "benode.h"
  29 #include "besched.h"
  30 #include "bemodule.h"
  31
  32 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
  33
  34 static const arch_env_t *arch_env;
  35 static be_lv_t          *lv;
  36 static ir_node          *current_node;
  37 ir_node                **register_values;
  38
  39 static void clear_reg_value(ir_node *node)
  40 {
  41         const arch_register_t *reg;
  42         unsigned               reg_idx;
  43
  44         if (!mode_is_data(get_irn_mode(node)))
  45                 return;
  46
  47         reg = arch_get_irn_register(node);
  48         if (reg == NULL) {
  49                 panic("No register assigned at %+F", node);
  50         }
  51         if (reg->type & arch_register_type_virtual)
  52                 return;
  53         reg_idx = reg->global_index;
  54
  55         DB((dbg, LEVEL_1, "Clear Register %s\n", reg->name));
  56         register_values[reg_idx] = NULL;
  57 }
  58
  59 static void set_reg_value(ir_node *node)
  60 {
  61         const arch_register_t *reg;
  62         unsigned               reg_idx;
  63
  64         if (!mode_is_data(get_irn_mode(node)))
  65                 return;
  66
  67         reg = arch_get_irn_register(node);
  68         if (reg == NULL) {
  69                 panic("No register assigned at %+F", node);
  70         }
  71         if (reg->type & arch_register_type_virtual)
  72                 return;
  73         reg_idx = reg->global_index;
  74
  75         DB((dbg, LEVEL_1, "Set Register %s: %+F\n", reg->name, node));
  76         register_values[reg_idx] = node;
  77 }
  78
  79 static void clear_defs(ir_node *node)
  80 {
  81         /* clear values defined */
  82         be_foreach_value(node, value,
  83                 clear_reg_value(value);
  84         );
  85 }
  86
  87 static void set_uses(ir_node *node)
  88 {
  89         int i, arity;
  90
  91         /* set values used */
  92         arity = get_irn_arity(node);
  93         for (i = 0; i < arity; ++i) {
  94                 ir_node *in = get_irn_n(node, i);
  95                 set_reg_value(in);
  96         }
  97 }
  98
  99 /**
 100  * must be called from peephole optimisations before a node will be killed
 101  * and its users will be redirected to new_node.
 102  * so bepeephole can update its internal state.
 103  *
 104  * Note: killing a node and rewiring is only allowed if new_node produces
 105  * the same registers as old_node.
 106  */
 107 static void be_peephole_before_exchange(const ir_node *old_node,
 108                                         ir_node *new_node)
 109 {
 110         const arch_register_t *reg;
 111         unsigned               reg_idx;
 112         bool                   old_is_current = false;
 113
 114         DB((dbg, LEVEL_1, "About to exchange and kill %+F with %+F\n", old_node, new_node));
 115
 116         assert(sched_is_scheduled(skip_Proj_const(old_node)));
 117         assert(sched_is_scheduled(skip_Proj(new_node)));
 118
 119         if (current_node == old_node) {
 120                 old_is_current = true;
 121
 122                 /* next node to be processed will be killed. Its scheduling predecessor
 123                  * must be processed next. */
 124                 current_node = sched_next(current_node);
 125                 assert (!is_Bad(current_node));
 126
 127                 /* we can't handle liveness updates correctly when exchange current node
 128                  * with something behind it */
 129                 assert(value_dominates(skip_Proj(new_node), skip_Proj_const(old_node)));
 130         }
 131
 132         if (!mode_is_data(get_irn_mode(old_node)))
 133                 return;
 134
 135         reg = arch_get_irn_register(old_node);
 136         if (reg == NULL) {
 137                 panic("No register assigned at %+F", old_node);
 138         }
 139         assert(reg == arch_get_irn_register(new_node) &&
 140               "KILLING a node and replacing by different register is not allowed");
 141
 142         reg_idx = reg->global_index;
 143         if (register_values[reg_idx] == old_node || old_is_current) {
 144                 register_values[reg_idx] = new_node;
 145         }
 146
 147         be_liveness_remove(lv, old_node);
 148 }
 149
 150 void be_peephole_exchange(ir_node *old, ir_node *nw)
 151 {
 152         be_peephole_before_exchange(old, nw);
 153         sched_remove(old);
 154         exchange(old, nw);
 155         be_liveness_introduce(lv, nw);
 156 }
 157
 158 /**
 159  * block-walker: run peephole optimization on the given block.
 160  */
 161 static void process_block(ir_node *block, void *data)
 162 {
 163         (void) data;
 164
 165         /* construct initial register assignment */
 166         memset(register_values, 0, sizeof(ir_node*) * arch_env->n_registers);
 167
 168         assert(lv->sets_valid && "live sets must be computed");
 169         DB((dbg, LEVEL_1, "\nProcessing block %+F (from end)\n", block));
 170         be_lv_foreach(lv, block, be_lv_state_end, node) {
 171                 set_reg_value(node);
 172         }
 173         DB((dbg, LEVEL_1, "\nstart processing\n"));
 174
 175         /* walk the block from last insn to the first */
 176         current_node = sched_last(block);
 177         for ( ; !sched_is_begin(current_node);
 178                         current_node = sched_prev(current_node)) {
 179                 ir_op             *op;
 180                 peephole_opt_func  peephole_node;
 181
 182                 assert(!is_Bad(current_node));
 183                 if (is_Phi(current_node))
 184                         break;
 185
 186                 clear_defs(current_node);
 187                 set_uses(current_node);
 188
 189                 op            = get_irn_op(current_node);
 190                 peephole_node = (peephole_opt_func)op->ops.generic;
 191                 if (peephole_node == NULL)
 192                         continue;
 193
 194                 DB((dbg, LEVEL_2, "optimize %+F\n", current_node));
 195                 peephole_node(current_node);
 196                 assert(!is_Bad(current_node));
 197         }
 198 }
 199
 200 /**
 201  * Check whether the node has only one user.  Explicitly ignore the anchor.
 202  */
 203 bool be_has_only_one_user(ir_node *node)
 204 {
 205         int n = get_irn_n_edges(node);
 206         int n_users;
 207
 208         if (n <= 1)
 209                 return 1;
 210
 211         n_users = 0;
 212         foreach_out_edge(node, edge) {
 213                 ir_node *src = get_edge_src_irn(edge);
 214                 /* ignore anchor and keep-alive edges */
 215                 if (is_Anchor(src) || is_End(src))
 216                         continue;
 217                 n_users++;
 218         }
 219
 220         return n_users == 1;
 221 }
 222
 223 static inline bool overlapping_regs(const arch_register_t *reg0,
 224         const arch_register_req_t *req0, const arch_register_t *reg1,
 225         const arch_register_req_t *req1)
 226 {
 227         if (reg0 == NULL || reg1 == NULL)
 228                 return false;
 229         return reg0->global_index < (unsigned)reg1->global_index + req1->width
 230                 && reg1->global_index < (unsigned)reg0->global_index + req0->width;
 231 }
 232
 233 bool be_can_move_down(ir_heights_t *heights, const ir_node *node,
 234                       const ir_node *before)
 235 {
 236         assert(get_nodes_block(node) == get_nodes_block(before));
 237         assert(sched_get_time_step(node) < sched_get_time_step(before));
 238
 239         int      node_arity = get_irn_arity(node);
 240         ir_node *schedpoint = sched_next(node);
 241
 242         while (schedpoint != before) {
 243                 /* schedpoint must not use our computed values */
 244                 if (heights_reachable_in_block(heights, schedpoint, node))
 245                         return false;
 246
 247                 /* schedpoint must not overwrite registers of our inputs */
 248                 for (int i = 0; i < node_arity; ++i) {
 249                         ir_node                   *in  = get_irn_n(node, i);
 250                         const arch_register_t     *reg = arch_get_irn_register(in);
 251                         if (reg == NULL)
 252                                 continue;
 253                         const arch_register_req_t *in_req
 254                                 = arch_get_irn_register_req_in(node, i);
 255                         be_foreach_out(schedpoint, o) {
 256                                 const arch_register_t *outreg
 257                                         = arch_get_irn_register_out(schedpoint, o);
 258                                 const arch_register_req_t *outreq
 259                                         = arch_get_irn_register_req_out(schedpoint, o);
 260                                 if (overlapping_regs(reg, in_req, outreg, outreq))
 261                                         return false;
 262                         }
 263                 }
 264
 265                 schedpoint = sched_next(schedpoint);
 266         }
 267         return true;
 268 }
 269
 270 bool be_can_move_up(ir_heights_t *heights, const ir_node *node,
 271                     const ir_node *after)
 272 {
 273         const ir_node *node_block  = get_nodes_block(node);
 274         const ir_node *after_block = get_block_const(after);
 275         const ir_node *schedpoint;
 276         if (node_block != after_block) {
 277                 /* currently we can move up exactly 1 block */
 278                 assert(get_Block_cfgpred_block(node_block, 0) == after_block);
 279                 ir_node *first = sched_first(node_block);
 280
 281                 /* do not move nodes changing memory */
 282                 if (is_memop(node)) {
 283                         ir_node *meminput = get_memop_mem(node);
 284                         if (!is_NoMem(meminput))
 285                                 return false;
 286                 }
 287
 288                 /* make sure we can move to the beginning of the succ block */
 289                 if (node != first && !be_can_move_up(heights, node, sched_prev(first)))
 290                         return false;
 291
 292                 /* check if node overrides any of live-in values of other successors */
 293                 ir_graph *irg = get_irn_irg(node);
 294                 be_lv_t  *lv  = be_get_irg_liveness(irg);
 295                 foreach_block_succ(after_block, edge) {
 296                         ir_node *succ = get_edge_src_irn(edge);
 297                         if (succ == node_block)
 298                                 continue;
 299
 300                         be_lv_foreach(lv, succ, be_lv_state_in, live_node) {
 301                                 const arch_register_t     *reg = arch_get_irn_register(live_node);
 302                                 const arch_register_req_t *req = arch_get_irn_register_req(live_node);
 303                                 be_foreach_out(node, o) {
 304                                         const arch_register_t *outreg
 305                                                 = arch_get_irn_register_out(node, o);
 306                                         const arch_register_req_t *outreq
 307                                                 = arch_get_irn_register_req_out(node, o);
 308                                         if (overlapping_regs(outreg, outreq, reg, req))
 309                                                 return false;
 310                                 }
 311                         }
 312                         sched_foreach(succ, phi) {
 313                                 if (!is_Phi(phi))
 314                                         break;
 315                                 const arch_register_t     *reg = arch_get_irn_register(phi);
 316                                 const arch_register_req_t *req = arch_get_irn_register_req(phi);
 317                                 be_foreach_out(node, o) {
 318                                         const arch_register_t *outreg
 319                                                 = arch_get_irn_register_out(node, o);
 320                                         const arch_register_req_t *outreq
 321                                                 = arch_get_irn_register_req_out(node, o);
 322                                         if (overlapping_regs(outreg, outreq, reg, req))
 323                                                 return false;
 324                                 }
 325                         }
 326                 }
 327                 schedpoint = sched_last(after_block);
 328         } else {
 329                 schedpoint = sched_prev(node);
 330         }
 331
 332         /* move schedule upwards until we hit the "after" node */
 333         while (schedpoint != after) {
 334                 /* TODO: the following heights query only works for nodes in the same
 335                  * block, otherwise we have to be conservative here */
 336                 if (get_nodes_block(node) != get_nodes_block(schedpoint))
 337                         return false;
 338                 /* node must not depend on schedpoint */
 339                 if (heights_reachable_in_block(heights, node, schedpoint))
 340                         return false;
 341
 342                 /* node must not overwrite registers used by schedpoint */
 343                 int arity = get_irn_arity(schedpoint);
 344                 for (int i = 0; i < arity; ++i) {
 345                         const arch_register_t *reg
 346                                 = arch_get_irn_register_in(schedpoint, i);
 347                         if (reg == NULL)
 348                                 continue;
 349                         const arch_register_req_t *in_req
 350                                 = arch_get_irn_register_req_in(schedpoint, i);
 351                         be_foreach_out(node, o) {
 352                                 const arch_register_t *outreg
 353                                         = arch_get_irn_register_out(node, o);
 354                                 const arch_register_req_t *outreq
 355                                         = arch_get_irn_register_req_out(node, o);
 356                                 if (overlapping_regs(outreg, outreq, reg, in_req))
 357                                         return false;
 358                         }
 359                 }
 360
 361                 schedpoint = sched_prev(schedpoint);
 362         }
 363         return true;
 364 }
 365
 366 /*
 367  * Tries to optimize a beIncSP node with its previous IncSP node.
 368  * Must be run from a be_peephole_opt() context.
 369  */
 370 ir_node *be_peephole_IncSP_IncSP(ir_node *node)
 371 {
 372         int      pred_offs;
 373         int      curr_offs;
 374         int      offs;
 375         ir_node *pred = be_get_IncSP_pred(node);
 376
 377         if (!be_is_IncSP(pred))
 378                 return node;
 379
 380         if (!be_has_only_one_user(pred))
 381                 return node;
 382
 383         pred_offs = be_get_IncSP_offset(pred);
 384         curr_offs = be_get_IncSP_offset(node);
 385         offs = curr_offs + pred_offs;
 386
 387         /* add node offset to pred and remove our IncSP */
 388         be_set_IncSP_offset(pred, offs);
 389
 390         be_peephole_exchange(node, pred);
 391         return pred;
 392 }
 393
 394 void be_peephole_opt(ir_graph *irg)
 395 {
 396         be_assure_live_sets(irg);
 397
 398         arch_env = be_get_irg_arch_env(irg);
 399         lv       = be_get_irg_liveness(irg);
 400
 401         register_values = XMALLOCN(ir_node*, arch_env->n_registers);
 402
 403         irg_block_walk_graph(irg, process_block, NULL, NULL);
 404
 405         xfree(register_values);
 406 }
 407
 408 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_peephole)
 409 void be_init_peephole(void)
 410 {
 411         FIRM_DBG_REGISTER(dbg, "firm.be.peephole");
 412 }