mono/mini/alias-analysis.c

   1 /*
   2  * alias-analysis.c: Implement simple alias analysis for local variables.
   3  *
   4  * Author:
   5  *   Rodrigo Kumpera (kumpera@gmail.com)
   6  *
   7  * (C) 2013 Xamarin
   8  */
   9
  10 #include <config.h>
  11 #include <stdio.h>
  12
  13 #include "mini.h"
  14 #include "ir-emit.h"
  15 #include "glib.h"
  16
  17 static gboolean
  18 is_int_stack_size (int type)
  19 {
  20 #if SIZEOF_VOID_P == 4
  21         return type == STACK_I4 || type == STACK_MP;
  22 #else
  23         return type == STACK_I4;
  24 #endif
  25 }
  26
  27 static gboolean
  28 is_long_stack_size (int type)
  29 {
  30 #if SIZEOF_VOID_P == 8
  31         return type == STACK_I8 || type == STACK_MP;
  32 #else
  33         return type == STACK_I8;
  34 #endif
  35 }
  36
  37
  38 static gboolean
  39 lower_load (MonoCompile *cfg, MonoInst *load, MonoInst *ldaddr)
  40 {
  41         MonoInst *var = ldaddr->inst_p0;
  42         MonoType *type = &var->klass->byval_arg;
  43         int replaced_op = mono_type_to_load_membase (cfg, type);
  44
  45         if (load->opcode == OP_LOADV_MEMBASE && load->klass != var->klass) {
  46                 if (cfg->verbose_level > 2)
  47                         printf ("Incompatible load_vtype classes %s x %s\n", load->klass->name, var->klass->name);
  48                 return FALSE;
  49         }
  50
  51         if (replaced_op != load->opcode) {
  52                 if (cfg->verbose_level > 2)
  53                         printf ("Incompatible load type: expected %s but got %s\n",
  54                                 mono_inst_name (replaced_op),
  55                                 mono_inst_name (load->opcode));
  56                 return FALSE;
  57         } else {
  58                 if (cfg->verbose_level > 2) { printf ("mem2reg replacing: "); mono_print_ins (load); }
  59         }
  60
  61         load->opcode = mono_type_to_regmove (cfg, type);
  62         type_to_eval_stack_type (cfg, type, load);
  63         load->sreg1 = var->dreg;
  64         mono_jit_stats.loads_eliminated++;
  65         return TRUE;
  66 }
  67
  68 static gboolean
  69 lower_store (MonoCompile *cfg, MonoInst *store, MonoInst *ldaddr)
  70 {
  71         MonoInst *var = ldaddr->inst_p0;
  72         MonoType *type = &var->klass->byval_arg;
  73         int replaced_op = mono_type_to_store_membase (cfg, type);
  74
  75         if (store->opcode == OP_STOREV_MEMBASE && store->klass != var->klass) {
  76                 if (cfg->verbose_level > 2)
  77                         printf ("Incompatible store_vtype classes %s x %s\n", store->klass->name, store->klass->name);
  78                 return FALSE;
  79         }
  80
  81
  82         if (replaced_op != store->opcode) {
  83                 if (cfg->verbose_level > 2)
  84                         printf ("Incompatible store_reg type: expected %s but got %s\n",
  85                                 mono_inst_name (replaced_op),
  86                                 mono_inst_name (store->opcode));
  87                 return FALSE;
  88         } else {
  89                 if (cfg->verbose_level > 2) { printf ("mem2reg replacing: "); mono_print_ins (store); }
  90         }
  91
  92         store->opcode = mono_type_to_regmove (cfg, type);
  93         type_to_eval_stack_type (cfg, type, store);
  94         store->dreg = var->dreg;
  95         mono_jit_stats.stores_eliminated++;
  96         return TRUE;
  97 }
  98
  99 static gboolean
 100 lower_store_imm (MonoCompile *cfg, MonoInst *store, MonoInst *ldaddr)
 101 {
 102         MonoInst *var = ldaddr->inst_p0;
 103         MonoType *type = &var->klass->byval_arg;
 104         int store_op = mono_type_to_store_membase (cfg, type);
 105         if (store_op == OP_STOREV_MEMBASE || store_op == OP_STOREX_MEMBASE)
 106                 return FALSE;
 107
 108         switch (store->opcode) {
 109 #if SIZEOF_VOID_P == 4
 110         case OP_STORE_MEMBASE_IMM:
 111 #endif
 112         case OP_STOREI4_MEMBASE_IMM:
 113                 if (!is_int_stack_size (var->type)) {
 114                         if (cfg->verbose_level > 2) printf ("Incompatible variable of size != 4\n");
 115                         return FALSE;
 116                 }
 117                 if (cfg->verbose_level > 2) { printf ("mem2reg replacing: "); mono_print_ins (store); }
 118                 store->opcode = OP_ICONST;
 119                 store->type = STACK_I4;
 120                 store->dreg = var->dreg;
 121                 store->inst_c0 = store->inst_imm;
 122                 break;
 123
 124 #if SIZEOF_VOID_P == 8
 125         case OP_STORE_MEMBASE_IMM:
 126 #endif
 127         case OP_STOREI8_MEMBASE_IMM:
 128                 if (!is_long_stack_size (var->type)) {
 129                         if (cfg->verbose_level > 2) printf ("Incompatible variable of size != 8\n");
 130                         return FALSE;
 131                 }
 132                 if (cfg->verbose_level > 2) { printf ("mem2reg replacing: "); mono_print_ins (store); }
 133                 store->opcode = OP_I8CONST;
 134                 store->type = STACK_I8;
 135                 store->dreg = var->dreg;
 136                 store->inst_l = store->inst_imm;
 137                 break;
 138         default:
 139                 return FALSE;
 140         }
 141         mono_jit_stats.stores_eliminated++;
 142         return TRUE;
 143 }
 144
 145 static gboolean
 146 lower_memory_access (MonoCompile *cfg)
 147 {
 148         MonoBasicBlock *bb;
 149         MonoInst *ins, *tmp;
 150         gboolean needs_dce = FALSE;
 151         GHashTable *addr_loads = g_hash_table_new (NULL, NULL);
 152         //FIXME optimize
 153         for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
 154                 g_hash_table_remove_all (addr_loads);
 155
 156                 for (ins = bb->code; ins; ins = ins->next) {
 157                         switch (ins->opcode) {
 158                         case OP_LDADDR:
 159                                 g_hash_table_insert (addr_loads, GINT_TO_POINTER (ins->dreg), ins);
 160                                 if (cfg->verbose_level > 2) { printf ("New address: "); mono_print_ins (ins); }
 161                                 break;
 162                         case OP_MOVE:
 163                                 tmp = (MonoInst*)g_hash_table_lookup (addr_loads, GINT_TO_POINTER (ins->sreg1));
 164                                 /*
 165                                 Forward propagate known aliases
 166                                 ldaddr R10 <- R8
 167                                 mov R11 <- R10
 168                                 */
 169                                 if (tmp) {
 170                                         g_hash_table_insert (addr_loads, GINT_TO_POINTER (ins->dreg), tmp);
 171                                         if (cfg->verbose_level > 2) { printf ("New alias: "); mono_print_ins (ins); }
 172                                 } else {
 173                                         /*
 174                                         Source value is not a know address, kill the variable.
 175                                         */
 176                                         if (g_hash_table_remove (addr_loads, GINT_TO_POINTER (ins->dreg))) {
 177                                                 if (cfg->verbose_level > 2) { printf ("Killed alias: "); mono_print_ins (ins); }
 178                                         }
 179                                 }
 180                                 break;
 181
 182                         case OP_LOADV_MEMBASE:
 183                         case OP_LOAD_MEMBASE:
 184                         case OP_LOADU1_MEMBASE:
 185                         case OP_LOADI2_MEMBASE:
 186                         case OP_LOADU2_MEMBASE:
 187                         case OP_LOADI4_MEMBASE:
 188                         case OP_LOADU4_MEMBASE:
 189                         case OP_LOADI1_MEMBASE:
 190                         case OP_LOADI8_MEMBASE:
 191                         case OP_LOADR4_MEMBASE:
 192                         case OP_LOADR8_MEMBASE:
 193                                 if (ins->inst_offset != 0)
 194                                         continue;
 195                                 tmp = g_hash_table_lookup (addr_loads, GINT_TO_POINTER (ins->sreg1));
 196                                 if (tmp) {
 197                                         if (cfg->verbose_level > 2) { printf ("Found candidate load:"); mono_print_ins (ins); }
 198                                         needs_dce |= lower_load (cfg, ins, tmp);
 199                                 }
 200                                 break;
 201
 202                         case OP_STORE_MEMBASE_REG:
 203                         case OP_STOREI1_MEMBASE_REG:
 204                         case OP_STOREI2_MEMBASE_REG:
 205                         case OP_STOREI4_MEMBASE_REG:
 206                         case OP_STOREI8_MEMBASE_REG:
 207                         case OP_STORER4_MEMBASE_REG:
 208                         case OP_STORER8_MEMBASE_REG:
 209                         case OP_STOREV_MEMBASE:
 210                                 if (ins->inst_offset != 0)
 211                                         continue;
 212                                 tmp = g_hash_table_lookup (addr_loads, GINT_TO_POINTER (ins->dreg));
 213                                 if (tmp) {
 214                                         if (cfg->verbose_level > 2) { printf ("Found candidate store:"); mono_print_ins (ins); }
 215                                         needs_dce |= lower_store (cfg, ins, tmp);
 216                                 }
 217                                 break;
 218
 219                         case OP_STORE_MEMBASE_IMM:
 220                         case OP_STOREI4_MEMBASE_IMM:
 221                         case OP_STOREI8_MEMBASE_IMM:
 222                                 if (ins->inst_offset != 0)
 223                                         continue;
 224                                 tmp = g_hash_table_lookup (addr_loads, GINT_TO_POINTER (ins->dreg));
 225                                 if (tmp) {
 226                                         if (cfg->verbose_level > 2) { printf ("Found candidate store-imm:"); mono_print_ins (ins); }
 227                                         needs_dce |= lower_store_imm (cfg, ins, tmp);
 228                                 }
 229                                 break;
 230                         }
 231                 }
 232         }
 233         g_hash_table_destroy (addr_loads);
 234         return needs_dce;
 235 }
 236
 237 static gboolean
 238 recompute_aliased_variables (MonoCompile *cfg)
 239 {
 240         int i;
 241         MonoBasicBlock *bb;
 242         MonoInst *ins;
 243         int kills = 0;
 244         int adds = 0;
 245
 246         for (i = 0; i < cfg->num_varinfo; i++) {
 247                 MonoInst *var = cfg->varinfo [i];
 248                 if (var->flags & MONO_INST_INDIRECT) {
 249                         if (cfg->verbose_level > 2) {
 250                                 printf ("Killing :"); mono_print_ins (var);
 251                         }
 252                         ++kills;
 253                 }
 254                 var->flags &= ~MONO_INST_INDIRECT;
 255         }
 256
 257         if (!kills)
 258                 return FALSE;
 259
 260         for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
 261                 for (ins = bb->code; ins; ins = ins->next) {
 262                         if (ins->opcode == OP_LDADDR) {
 263                                 MonoInst *var;
 264
 265                                 if (cfg->verbose_level > 2) { printf ("Found op :"); mono_print_ins (ins); }
 266
 267                                 var = (MonoInst*)ins->inst_p0;
 268                                 if (!(var->flags & MONO_INST_INDIRECT)) {
 269                                         if (cfg->verbose_level) { printf ("Restoring :"); mono_print_ins (var); }
 270                                         ++adds;
 271                                 }
 272                                 var->flags |= MONO_INST_INDIRECT;
 273                         }
 274                 }
 275         }
 276
 277         mono_jit_stats.alias_found += kills;
 278         mono_jit_stats.alias_removed += kills - adds;
 279         if (kills > adds) {
 280                 if (cfg->verbose_level > 2) {
 281                         printf ("Method: %s\n", mono_method_full_name (cfg->method, 1));
 282                         printf ("Kills %d Adds %d\n", kills, adds);
 283                 }
 284                 return TRUE;
 285         }
 286         return FALSE;
 287 }
 288
 289 /*
 290 FIXME:
 291         Don't DCE on the whole CFG, only the BBs that have changed.
 292
 293 TODO:
 294         SRVT of small types can fix cases of mismatch for fields of a different type than the component.
 295         Handle aliasing of byrefs in call conventions.
 296 */
 297 void
 298 mono_local_alias_analysis (MonoCompile *cfg)
 299 {
 300         if (!cfg->has_indirection)
 301                 return;
 302
 303         if (cfg->verbose_level > 2)
 304                 mono_print_code (cfg, "BEFORE ALIAS_ANALYSIS");
 305
 306         /*
 307         Remove indirection and memory access of known variables.
 308         */
 309         if (!lower_memory_access (cfg))
 310                 goto done;
 311
 312         /*
 313         By replacing indirect access with direct operations, some LDADDR ops become dead. Kill them.
 314         */
 315         if (cfg->opt & MONO_OPT_DEADCE)
 316                 mono_local_deadce (cfg);
 317
 318         /*
 319         Some variables no longer need to be flagged as indirect, find them.
 320         */
 321         if (!recompute_aliased_variables (cfg))
 322                 goto done;
 323
 324         /*
 325         A lot of simplification just took place, we recompute local variables and do DCE to
 326         really profit from the previous gains
 327         */
 328         mono_handle_global_vregs (cfg);
 329         if (cfg->opt & MONO_OPT_DEADCE)
 330                 mono_local_deadce (cfg);
 331
 332 done:
 333         if (cfg->verbose_level > 2)
 334                 mono_print_code (cfg, "AFTER ALIAS_ANALYSIS");
 335 }