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

   1 /**
   2  * Author:      Daniel Grund
   3  * Date:                17.01.2006
   4  * Copyright:   (c) Universitaet Karlsruhe
   5  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
   6  *
   7  */
   8
   9
  10 #ifdef HAVE_CONFIG_H
  11 #include "config.h"
  12 #endif
  13
  14 #ifdef HAVE_MALLOC_H
  15  #include <malloc.h>
  16 #endif
  17 #ifdef HAVE_ALLOCA_H
  18  #include <alloca.h>
  19 #endif
  20
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <limits.h>
  24 #ifdef WITH_LIBCORE
  25 #include <libcore/lc_opts.h>
  26 #include <libcore/lc_opts_enum.h>
  27 #endif
  28
  29 #include "set.h"
  30 #include "pset.h"
  31 #include "pmap.h"
  32 #include "bitset.h"
  33
  34 #include "irprintf_t.h"
  35 #include "irnode_t.h"
  36 #include "irgraph_t.h"
  37 #include "irgwalk.h"
  38 #include "iredges_t.h"
  39 #include "irdom_t.h"
  40 #include "phiclass.h"
  41
  42 #include "beraextern.h"
  43 #include "beabi.h"
  44 #include "bearch.h"
  45 #include "benode_t.h"
  46 #include "beirgmod.h"
  47 #include "besched_t.h"
  48 #include "beutil.h"
  49 #include "belive_t.h"
  50 #include "beinsn_t.h"
  51
  52 #include "bessadestrsimple.h"
  53
  54 #define DBG_LEVEL 2
  55
  56 typedef struct _ssa_destr_env_t {
  57         ir_graph *irg;
  58         const arch_register_class_t *cls;
  59         const arch_env_t *aenv;
  60         set *vars;
  61 } ssa_destr_env_t;
  62
  63 #define pset_foreach(pset, irn)  for(irn=pset_first(pset); irn; irn=pset_next(pset))
  64 #define set_foreach(set, e)  for(e=set_first(set); e; e=set_next(set))
  65
  66 /******************************************************************************
  67    __      __   _       ___   __      __
  68    \ \    / /  | |     |__ \  \ \    / /
  69     \ \  / /_ _| |___     ) |  \ \  / /_ _ _ __ ___
  70      \ \/ / _` | / __|   / /    \ \/ / _` | '__/ __|
  71       \  / (_| | \__ \  / /_     \  / (_| | |  \__ \
  72        \/ \__,_|_|___/ |____|     \/ \__,_|_|  |___/
  73  *****************************************************************************/
  74
  75 /**
  76  * The link field of an irn points to the var_info struct
  77  * representing the corresponding variable.
  78  */
  79 #define set_var_info(irn, vi)                           set_irn_link(irn, vi)
  80
  81 #define HASH_VAR_NR(var_nr) var_nr
  82
  83 static int compare_var_infos(const void *e1, const void *e2, size_t size) {
  84         const be_var_info_t *v1 = e1;
  85         const be_var_info_t *v2 = e2;
  86
  87         if (v1->var_nr == SET_REMOVED || v2->var_nr == SET_REMOVED)
  88                 return 1;
  89
  90         return v1->var_nr != v2->var_nr;
  91 }
  92
  93 be_var_info_t *be_var_find(set *vars, int var_nr) {
  94         be_var_info_t vi;
  95         vi.var_nr = var_nr;
  96
  97         return set_find(vars, &vi, sizeof(vi), HASH_VAR_NR(var_nr));
  98 }
  99
 100 be_var_info_t *be_var_find_or_insert(set *vars, int var_nr) {
 101         be_var_info_t vi, *found;
 102         memset(&vi, 0, sizeof(vi));
 103         vi.var_nr = var_nr;
 104
 105         found = set_insert(vars, &vi, sizeof(vi), HASH_VAR_NR(var_nr));
 106
 107         if (!found->values)
 108                 found->values  = pset_new_ptr(1);
 109
 110         return found;
 111 }
 112
 113 /**
 114  * Adds a value to a variable. Sets all pointers accordingly.
 115  */
 116 be_var_info_t *be_var_add_value(set *vars, int var_nr, ir_node *irn) {
 117         be_var_info_t *vi = be_var_find_or_insert(vars, var_nr);
 118
 119         /* var 2 value mapping */
 120         pset_insert_ptr(vi->values, irn);
 121
 122         /* value 2 var mapping */
 123         set_var_info(irn, vi);
 124
 125         return vi;
 126 }
 127
 128 pset *be_get_var_values(set *vars, int var_nr) {
 129         be_var_info_t *vi = be_var_find(vars, var_nr);
 130         assert(vi && "Variable does not exist");
 131         return vi->values;
 132 }
 133
 134 static INLINE ir_node *get_first_phi(pset *s) {
 135         ir_node *irn;
 136
 137         pset_foreach(s, irn)
 138                 if (is_Phi(irn)) {
 139                         pset_break(s);
 140                         return irn;
 141                 }
 142
 143         assert(0 && "There must be a phi in this");
 144         return NULL;
 145 }
 146
 147
 148 /**
 149  * Define variables (numbers) for all SSA-values.
 150  * All values in a phi class get assigned the same variable name.
 151  * The link field maps values to the var-name
 152  */
 153 static void values_to_vars(ir_node *irn, void *env) {
 154         ssa_destr_env_t *sde = env;
 155         int nr;
 156         pset *vals;
 157
 158         if(arch_get_irn_reg_class(sde->aenv, irn, -1) == NULL)
 159                 return;
 160
 161         vals = get_phi_class(irn);
 162
 163         if (vals) {
 164                 nr = get_irn_node_nr(get_first_phi(vals));
 165         } else {
 166                 /* not a phi class member, value == var */
 167                 nr = get_irn_node_nr(irn);
 168                 vals = pset_new_ptr(1);
 169                 pset_insert_ptr(vals, irn);
 170         }
 171
 172         /* values <--> var mapping */
 173         pset_foreach(vals, irn) {
 174                 be_var_add_value(sde->vars, nr, irn);
 175         }
 176 }
 177
 178 /******************************************************************************
 179      _____ _____              _____            _
 180     / ____/ ____|  /\        |  __ \          | |
 181    | (___| (___   /  \ ______| |  | | ___  ___| |_ _ __
 182     \___ \\___ \ / /\ \______| |  | |/ _ \/ __| __| '__|
 183     ____) |___) / ____ \     | |__| |  __/\__ \ |_| |
 184    |_____/_____/_/    \_\    |_____/ \___||___/\__|_|
 185
 186  *****************************************************************************/
 187
 188 #define mark_as_done(irn, pos)                  set_irn_link(irn, INT_TO_PTR(pos+1))
 189 #define has_been_done(irn, pos)                 (PTR_TO_INT(get_irn_link(irn)) > pos)
 190
 191 /**
 192  * Insert a copy for the argument of @p start_phi found at position @p pos.
 193  * Also searches a phi-loop of arbitrary length to detect and resolve
 194  *   the class of phi-swap-problems. To search for a loop recursion is used.
 195  *
 196  * 1) Simplest case (phi with a non-phi arg):
 197  *     A single copy is inserted.
 198  *
 199  * 2) Phi chain (phi (with phi-arg)* with non=phi arg):
 200  *     Several copies are placed, each after returning from recursion.
 201  *
 202  * 3) Phi-loop:
 203  *     On detection a loop breaker is inserted, which is a copy of the start_phi.
 204  *     This copy then pretends beeing the argumnent of the last phi.
 205  *     Now case 2) can be used.
 206  *
 207  * The values of @p start_phi and @p pos never change during recursion.
 208  *
 209  * @p start_phi  Phi node to process
 210  * @p pos        Argument position to insert copy/copies for
 211  * @p curr_phi   Phi node currently processed during recursion. Equals start_phi on initial call
 212  *
 213  * @return NULL  If no copy is necessary
 214  *         NULL  If the phi has already been processed at this pos
 215  *               Link field is used to keep track of processed positions
 216  *         In all other cases the ir_node *copy which was placed is returned.
 217  */
 218 static ir_node *insert_copies(ssa_destr_env_t *sde, const arch_register_class_t *cls, ir_node *start_phi, int pos, ir_node *curr_phi) {
 219         ir_node *arg = get_irn_n(curr_phi, pos);
 220         ir_node *arg_blk = get_nodes_block(arg);
 221         ir_node *pred_blk = get_Block_cfgpred_block(get_nodes_block(curr_phi), pos);
 222         ir_node *curr_cpy, *last_cpy;
 223
 224         assert(is_Phi(start_phi) && is_Phi(curr_phi));
 225
 226         if (has_been_done(start_phi, pos))
 227                 return NULL;
 228
 229         /* In case this is a 'normal' phi we insert at the
 230          * end of the pred block before cf nodes */
 231         last_cpy = sched_skip(pred_blk, 0, sched_skip_cf_predicator, (void *)sde->aenv);
 232         last_cpy = sched_next(last_cpy);
 233
 234         /* If we detect a loop stop recursion. */
 235         if (arg == start_phi) {
 236                 ir_node *loop_breaker;
 237                 if (start_phi == curr_phi) {
 238                         /* Phi directly uses itself. No copy necessary */
 239                         return NULL;
 240                 }
 241
 242                 /* At least 2 phis are involved */
 243                 /* Insert a loop breaking copy (an additional variable T) */
 244                 loop_breaker = be_new_Copy(cls, sde->irg, pred_blk, start_phi);
 245                 sched_add_before(last_cpy, loop_breaker);
 246
 247                 arg = loop_breaker;
 248         }
 249
 250         /* If arg is a phi in the same block we have to continue search */
 251         if (is_Phi(arg) && arg_blk == get_nodes_block(start_phi))
 252                 last_cpy = insert_copies(sde, cls, start_phi, pos, arg);
 253
 254         /* Insert copy of argument (may be the loop-breaker) */
 255         curr_cpy = be_new_Copy(cls, sde->irg, pred_blk, arg);
 256         set_irn_n(curr_phi, pos, curr_cpy);
 257         mark_as_done(curr_phi, pos);
 258         sched_add_before(last_cpy, curr_cpy);
 259         return curr_cpy;
 260 }
 261
 262
 263 /**
 264  * Perform simple SSA-destruction with copies.
 265  * The order of processing _must_ be
 266  *  for all positions {
 267  *    for all phis {
 268  *      doit
 269  *    }
 270  *  }
 271  * else the magic to keep track of processed phi-positions will fail in
 272  * function 'insert_copies'
 273  */
 274 static void ssa_destr_simple_walker(ir_node *blk, void *env) {
 275         ssa_destr_env_t *sde = env;
 276         int pos, max;
 277         ir_node *phi;
 278         const arch_register_class_t *cls;
 279
 280         /* for all argument positions of the phis */
 281         for (pos=0, max=get_irn_arity(blk); pos<max; ++pos) {
 282
 283                 /* for all phi nodes (which are scheduled first) */
 284                 sched_foreach(blk, phi) {
 285                         if (!is_Phi(phi))
 286                                 break;
 287
 288                         if (arch_irn_is(sde->aenv, phi, ignore))
 289                                 continue;
 290
 291                         cls = arch_get_irn_reg_class(sde->aenv, phi, -1);
 292                         insert_copies(sde, cls, phi, pos, phi);
 293                 }
 294         }
 295 }
 296
 297
 298 set *be_ssa_destr_simple(ir_graph *irg, const arch_env_t *aenv) {
 299         ssa_destr_env_t sde;
 300
 301         sde.irg = irg;
 302         sde.aenv = aenv;
 303         sde.vars = new_set(compare_var_infos, 16);
 304
 305         be_clear_links(irg);
 306         irg_block_walk_graph(irg, ssa_destr_simple_walker, NULL, &sde);
 307
 308         /* Mapping of SSA-Values <--> Variables */
 309         phi_class_compute(irg);
 310         be_clear_links(irg);
 311         irg_walk_graph(irg, values_to_vars, NULL, &sde);
 312
 313         return sde.vars;
 314 }
 315
 316 void free_ssa_destr_simple(set *vars)
 317 {
 318   be_var_info_t *vi;
 319
 320   set_foreach(vars, vi)
 321     del_pset(vi->values);
 322
 323   del_set(vars);
 324 }