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

   1 /*
   2  * Copyright (C) 1995-2007 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       modifies schedule so flags dependencies are respected.
  23  * @author      Matthias Braun, Christoph Mallon
  24  * @version     $Id: besched.h 14693 2007-06-21 15:35:49Z beck $
  25  */
  26 #ifdef HAVE_CONFIG_H
  27 #include "config.h"
  28 #endif
  29
  30 #include "irgwalk.h"
  31 #include "irnode_t.h"
  32 #include "irtools.h"
  33 #include "ircons.h"
  34 #include "iredges_t.h"
  35 #include "irprintf.h"
  36 #include "error.h"
  37
  38 #include "beflags.h"
  39 #include "bearch_t.h"
  40 #include "beirg_t.h"
  41 #include "besched_t.h"
  42
  43 static const arch_env_t            *arch_env   = NULL;
  44 static const arch_register_class_t *flag_class = NULL;
  45 static const arch_register_t       *flags_reg  = NULL;
  46 static func_rematerialize           remat      = NULL;
  47
  48 static ir_node *default_remat(ir_node *node, ir_node *after)
  49 {
  50         ir_node *copy  = exact_copy(node);
  51         sched_add_after(after, copy);
  52
  53         return copy;
  54 }
  55
  56 /**
  57  * tests wether we can legally move node node after node after
  58  * (only works for nodes in same block)
  59  */
  60 static int can_move(ir_node *node, ir_node *after)
  61 {
  62         const ir_edge_t *edge;
  63         assert(get_nodes_block(node) == get_nodes_block(after));
  64
  65         /* TODO respect dep edges */
  66         assert(get_irn_n_edges_kind(node, EDGE_KIND_DEP) == 0);
  67
  68         /** all users have to be after the after node */
  69         foreach_out_edge(node, edge) {
  70                 ir_node *out = get_edge_src_irn(edge);
  71                 if(is_Proj(out)) {
  72                         const ir_edge_t *edge2;
  73                         assert(get_irn_n_edges_kind(out, EDGE_KIND_DEP) == 0);
  74                         foreach_out_edge(out, edge2) {
  75                                 ir_node *out2 = get_edge_src_irn(edge2);
  76                                 /* phi represents a usage at block end */
  77                                 if(is_Phi(out2))
  78                                         continue;
  79                                 if(sched_get_time_step(out2) <= sched_get_time_step(after)) {
  80                                         return 0;
  81                                 }
  82                         }
  83                 } else {
  84                         /* phi represents a usage at block end */
  85                         if(is_Phi(out))
  86                                 continue;
  87                         if(sched_get_time_step(out) <= sched_get_time_step(after)) {
  88                                 return 0;
  89                         }
  90                 }
  91         }
  92
  93         ir_fprintf(stderr, "Can move node %+F after node %+F\n", node, after);
  94         return 1;
  95 }
  96
  97 static void rematerialize_or_move(ir_node *flags_needed, ir_node *node,
  98                                   ir_node *flag_consumers, int pn)
  99 {
 100         ir_node *n;
 101         ir_node *copy;
 102         ir_node *value;
 103
 104         if(can_move(flags_needed, node)) {
 105                 /* move it */
 106                 sched_remove(flags_needed);
 107                 sched_add_after(node, flags_needed);
 108                 return;
 109         }
 110
 111         copy = remat(flags_needed, node);
 112
 113         if(get_irn_mode(copy) == mode_T) {
 114                 ir_node *block = get_nodes_block(copy);
 115                 ir_mode *mode  = flag_class->mode;
 116                 value = new_rd_Proj(NULL, current_ir_graph, block,
 117                                                         copy, mode, pn);
 118         } else {
 119                 value = copy;
 120         }
 121
 122         n = flag_consumers;
 123         do {
 124                 int i;
 125                 int arity = get_irn_arity(n);
 126                 for(i = 0; i < arity; ++i) {
 127                         ir_node *in = get_irn_n(n, i);
 128                         in = skip_Proj(in);
 129                         if(in == flags_needed) {
 130                                 set_irn_n(n, i, value);
 131                                 break;
 132                         }
 133                 }
 134                 n = get_irn_link(n);
 135         } while(n != NULL);
 136 }
 137
 138 static void fix_flags_walker(ir_node *block, void *env)
 139 {
 140         ir_node *node;
 141         ir_node *flags_needed   = NULL;
 142         ir_node *flag_consumers = NULL;
 143         int      pn;
 144         (void) env;
 145
 146         sched_foreach_reverse(block, node) {
 147                 int i, arity;
 148                 ir_node *new_flags_needed = NULL;
 149
 150                 if(node == flags_needed) {
 151                         /* all ok */
 152                         flags_needed   = NULL;
 153                         flag_consumers = NULL;
 154                 }
 155
 156                 /* test wether node destroys the flags */
 157                 if(flags_needed != NULL && arch_irn_is(arch_env, node, modify_flags)) {
 158                         /* rematerialize */
 159                         rematerialize_or_move(flags_needed, node, flag_consumers, pn);
 160                         flags_needed   = NULL;
 161                         flag_consumers = NULL;
 162                 }
 163
 164                 /* test wether the current node needs flags */
 165                 arity = get_irn_arity(node);
 166                 for(i = 0; i < arity; ++i) {
 167                         //ir_node *in = get_irn_n(node, i);
 168                         const arch_register_class_t *cls
 169                                 = arch_get_irn_reg_class(arch_env, node, i);
 170                         if(cls == flag_class) {
 171                                 assert(new_flags_needed == NULL);
 172                                 new_flags_needed = get_irn_n(node, i);
 173                         }
 174                 }
 175
 176                 if(new_flags_needed == NULL)
 177                         continue;
 178
 179                 if(new_flags_needed != flags_needed) {
 180                         if(flags_needed != NULL) {
 181                                 /* rematerialize node */
 182                                 rematerialize_or_move(flags_needed, node, flag_consumers, pn);
 183                                 flags_needed    = NULL;
 184                                 flag_consumers = NULL;
 185                         }
 186
 187                         if(get_nodes_block(new_flags_needed) != block) {
 188                                 panic("remat across blocks not implemented yet");
 189                                 flags_needed   = NULL;
 190                                 flag_consumers = NULL;
 191                         } else {
 192                                 flags_needed = new_flags_needed;
 193                                 arch_set_irn_register(arch_env, flags_needed, flags_reg);
 194                                 if(is_Proj(flags_needed)) {
 195                                         pn           = get_Proj_proj(flags_needed);
 196                                         flags_needed = get_Proj_pred(flags_needed);
 197                                 }
 198                                 flag_consumers = node;
 199                                 set_irn_link(flag_consumers, NULL);
 200                                 assert(arch_irn_is(arch_env, flags_needed, rematerializable));
 201                         }
 202                 } else {
 203                         /* link all consumers in a list */
 204                         set_irn_link(flag_consumers, node);
 205                         flag_consumers = node;
 206                 }
 207         }
 208
 209         assert(flags_needed   == NULL);
 210         assert(flag_consumers == NULL);
 211 }
 212
 213 void be_sched_fix_flags(be_irg_t *birg, const arch_register_class_t *flag_cls,
 214                         func_rematerialize remat_func)
 215 {
 216         ir_graph *irg = be_get_birg_irg(birg);
 217
 218         arch_env   = be_get_birg_arch_env(birg);
 219         flag_class = flag_cls;
 220         flags_reg  = & flag_class->regs[0];
 221         remat      = remat_func;
 222         if(remat == NULL)
 223                 remat = &default_remat;
 224
 225         set_using_irn_link(irg);
 226         irg_block_walk_graph(irg, fix_flags_walker, NULL, NULL);
 227         clear_using_irn_link(irg);
 228 }