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