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