mono/mini/alias-analysis.c

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