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