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 = (MonoInst *)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 = (MonoInst *)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 = (MonoInst *)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 handle_instruction:
 160                         switch (ins->opcode) {
 161                         case OP_LDADDR:
 162                                 g_hash_table_insert (addr_loads, GINT_TO_POINTER (ins->dreg), ins);
 163                                 if (cfg->verbose_level > 2) { printf ("New address: "); mono_print_ins (ins); }
 164                                 break;
 165                         case OP_MOVE:
 166                                 tmp = (MonoInst*)g_hash_table_lookup (addr_loads, GINT_TO_POINTER (ins->sreg1));
 167                                 /*
 168                                 Forward propagate known aliases
 169                                 ldaddr R10 <- R8
 170                                 mov R11 <- R10
 171                                 */
 172                                 if (tmp) {
 173                                         g_hash_table_insert (addr_loads, GINT_TO_POINTER (ins->dreg), tmp);
 174                                         if (cfg->verbose_level > 2) { printf ("New alias: "); mono_print_ins (ins); }
 175                                 } else {
 176                                         /*
 177                                         Source value is not a know address, kill the variable.
 178                                         */
 179                                         if (g_hash_table_remove (addr_loads, GINT_TO_POINTER (ins->dreg))) {
 180                                                 if (cfg->verbose_level > 2) { printf ("Killed alias: "); mono_print_ins (ins); }
 181                                         }
 182                                 }
 183                                 break;
 184
 185                         case OP_LOADV_MEMBASE:
 186                         case OP_LOAD_MEMBASE:
 187                         case OP_LOADU1_MEMBASE:
 188                         case OP_LOADI2_MEMBASE:
 189                         case OP_LOADU2_MEMBASE:
 190                         case OP_LOADI4_MEMBASE:
 191                         case OP_LOADU4_MEMBASE:
 192                         case OP_LOADI1_MEMBASE:
 193                         case OP_LOADI8_MEMBASE:
 194 #ifndef MONO_ARCH_SOFT_FLOAT_FALLBACK
 195                         case OP_LOADR4_MEMBASE:
 196 #endif
 197                         case OP_LOADR8_MEMBASE:
 198                                 if (ins->inst_offset != 0)
 199                                         continue;
 200                                 tmp = (MonoInst *)g_hash_table_lookup (addr_loads, GINT_TO_POINTER (ins->sreg1));
 201                                 if (tmp) {
 202                                         if (cfg->verbose_level > 2) { printf ("Found candidate load:"); mono_print_ins (ins); }
 203                                         if (lower_load (cfg, ins, tmp)) {
 204                                                 needs_dce = TRUE;
 205                                                 /* Try to propagate known aliases if an OP_MOVE was inserted */
 206                                                 goto handle_instruction;
 207                                         }
 208                                 }
 209                                 break;
 210
 211                         case OP_STORE_MEMBASE_REG:
 212                         case OP_STOREI1_MEMBASE_REG:
 213                         case OP_STOREI2_MEMBASE_REG:
 214                         case OP_STOREI4_MEMBASE_REG:
 215                         case OP_STOREI8_MEMBASE_REG:
 216 #ifndef MONO_ARCH_SOFT_FLOAT_FALLBACK
 217                         case OP_STORER4_MEMBASE_REG:
 218 #endif
 219                         case OP_STORER8_MEMBASE_REG:
 220                         case OP_STOREV_MEMBASE:
 221                                 if (ins->inst_offset != 0)
 222                                         continue;
 223                                 tmp = (MonoInst *)g_hash_table_lookup (addr_loads, GINT_TO_POINTER (ins->dreg));
 224                                 if (tmp) {
 225                                         if (cfg->verbose_level > 2) { printf ("Found candidate store:"); mono_print_ins (ins); }
 226                                         if (lower_store (cfg, ins, tmp)) {
 227                                                 needs_dce = TRUE;
 228                                                 /* Try to propagate known aliases if an OP_MOVE was inserted */
 229                                                 goto handle_instruction;
 230                                         }
 231                                 }
 232                                 break;
 233                         //FIXME missing storei1_membase_imm and storei2_membase_imm
 234                         case OP_STORE_MEMBASE_IMM:
 235                         case OP_STOREI4_MEMBASE_IMM:
 236                         case OP_STOREI8_MEMBASE_IMM:
 237                                 if (ins->inst_offset != 0)
 238                                         continue;
 239                                 tmp = (MonoInst *)g_hash_table_lookup (addr_loads, GINT_TO_POINTER (ins->dreg));
 240                                 if (tmp) {
 241                                         if (cfg->verbose_level > 2) { printf ("Found candidate store-imm:"); mono_print_ins (ins); }
 242                                         needs_dce |= lower_store_imm (cfg, ins, tmp);
 243                                 }
 244                                 break;
 245                         case OP_CHECK_THIS:
 246                         case OP_NOT_NULL:
 247                                 tmp = (MonoInst *)g_hash_table_lookup (addr_loads, GINT_TO_POINTER (ins->sreg1));
 248                                 if (tmp) {
 249                                         if (cfg->verbose_level > 2) { printf ("Found null check over local: "); mono_print_ins (ins); }
 250                                         NULLIFY_INS (ins);
 251                                         needs_dce = TRUE;
 252                                 }
 253                                 break;
 254                         }
 255                 }
 256         }
 257         g_hash_table_destroy (addr_loads);
 258         return needs_dce;
 259 }
 260
 261 static gboolean
 262 recompute_aliased_variables (MonoCompile *cfg, int *restored_vars)
 263 {
 264         int i;
 265         MonoBasicBlock *bb;
 266         MonoInst *ins;
 267         int kills = 0;
 268         int adds = 0;
 269         *restored_vars = 0;
 270
 271         for (i = 0; i < cfg->num_varinfo; i++) {
 272                 MonoInst *var = cfg->varinfo [i];
 273                 if (var->flags & MONO_INST_INDIRECT) {
 274                         if (cfg->verbose_level > 2) {
 275                                 printf ("Killing :"); mono_print_ins (var);
 276                         }
 277                         ++kills;
 278                 }
 279                 var->flags &= ~MONO_INST_INDIRECT;
 280         }
 281
 282         if (!kills)
 283                 return FALSE;
 284
 285         for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
 286                 for (ins = bb->code; ins; ins = ins->next) {
 287                         if (ins->opcode == OP_LDADDR) {
 288                                 MonoInst *var;
 289
 290                                 if (cfg->verbose_level > 2) { printf ("Found op :"); mono_print_ins (ins); }
 291
 292                                 var = (MonoInst*)ins->inst_p0;
 293                                 if (!(var->flags & MONO_INST_INDIRECT)) {
 294                                         if (cfg->verbose_level > 1) { printf ("Restoring :"); mono_print_ins (var); }
 295                                         ++adds;
 296                                 }
 297                                 var->flags |= MONO_INST_INDIRECT;
 298                         }
 299                 }
 300         }
 301         *restored_vars = adds;
 302
 303         mono_jit_stats.alias_found += kills;
 304         mono_jit_stats.alias_removed += kills - adds;
 305         if (kills > adds) {
 306                 if (cfg->verbose_level > 2) {
 307                         printf ("Method: %s\n", mono_method_full_name (cfg->method, 1));
 308                         printf ("Kills %d Adds %d\n", kills, adds);
 309                 }
 310                 return TRUE;
 311         }
 312         return FALSE;
 313 }
 314
 315 /*
 316 FIXME:
 317         Don't DCE on the whole CFG, only the BBs that have changed.
 318
 319 TODO:
 320         SRVT of small types can fix cases of mismatch for fields of a different type than the component.
 321         Handle aliasing of byrefs in call conventions.
 322 */
 323 void
 324 mono_local_alias_analysis (MonoCompile *cfg)
 325 {
 326         int i, restored_vars = 1;
 327         if (!cfg->has_indirection)
 328                 return;
 329
 330         if (cfg->verbose_level > 2)
 331                 mono_print_code (cfg, "BEFORE ALIAS_ANALYSIS");
 332
 333         /*
 334         Remove indirection and memory access of known variables.
 335         */
 336         if (!lower_memory_access (cfg))
 337                 goto done;
 338
 339         /*
 340         By replacing indirect access with direct operations, some LDADDR ops become dead. Kill them.
 341         */
 342         if (cfg->opt & MONO_OPT_DEADCE)
 343                 mono_local_deadce (cfg);
 344
 345         /*
 346         Some variables no longer need to be flagged as indirect, find them.
 347         Since indirect vars are converted into global vregs, each pass eliminates only one level of indirection.
 348         Most cases only need one pass and some 2.
 349         */
 350         for (i = 0; i < 3 && restored_vars > 0 && recompute_aliased_variables (cfg, &restored_vars); ++i) {
 351                 /*
 352                 A lot of simplification just took place, we recompute local variables and do DCE to
 353                 really profit from the previous gains
 354                 */
 355                 mono_handle_global_vregs (cfg);
 356                 if (cfg->opt & MONO_OPT_DEADCE)
 357                         mono_local_deadce (cfg);
 358         }
 359
 360 done:
 361         if (cfg->verbose_level > 2)
 362                 mono_print_code (cfg, "AFTER ALIAS_ANALYSIS");
 363 }
 364
 365 #endif /* !DISABLE_JIT */