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 || type == STACK_PTR;
  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 || type == STACK_PTR;
  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 void
 154 kill_call_arg_alias (MonoCompile *cfg, GHashTable *addr_loads, GSList *l)
 155 {
 156         for (; l; l = l->next) {
 157                 MonoInst *tmp;
 158                 guint32 regpair, reg;
 159
 160                 regpair = (guint32)(gssize)(l->data);
 161                 reg = regpair & 0xffffff;
 162
 163                 tmp = (MonoInst *)g_hash_table_lookup (addr_loads, GINT_TO_POINTER (reg));
 164                 if (tmp) {
 165                         // This call passes an alias as an argument. This means that the contents
 166                         // of the passed pointer can change. If the content is also an alias then
 167                         // we need to forget it as we do for moves.
 168                         if (g_hash_table_remove (addr_loads, GINT_TO_POINTER (((MonoInst*)tmp->inst_p0)->dreg))) {
 169                                 if (cfg->verbose_level > 2)
 170                                         printf ("Killed alias %d\n", ((MonoInst*)tmp->inst_p0)->dreg);
 171                         }
 172
 173                 }
 174         }
 175 }
 176
 177 static gboolean
 178 lower_memory_access (MonoCompile *cfg)
 179 {
 180         MonoBasicBlock *bb;
 181         MonoInst *ins, *tmp;
 182         gboolean needs_dce = FALSE;
 183         GHashTable *addr_loads = g_hash_table_new (NULL, NULL);
 184         //FIXME optimize
 185         for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
 186                 g_hash_table_remove_all (addr_loads);
 187
 188                 for (ins = bb->code; ins; ins = ins->next) {
 189 handle_instruction:
 190                         switch (ins->opcode) {
 191                         case OP_LDADDR: {
 192                                 MonoInst *var = (MonoInst*)ins->inst_p0;
 193                                 if (var->flags & MONO_INST_VOLATILE) {
 194                                         if (cfg->verbose_level > 2) { printf ("Found address to volatile var, can't take it: "); mono_print_ins (ins); }
 195                                 } else {
 196                                         g_hash_table_insert (addr_loads, GINT_TO_POINTER (ins->dreg), ins);
 197                                         if (cfg->verbose_level > 2) { printf ("New address: "); mono_print_ins (ins); }
 198                                 }
 199                                 break;
 200                         }
 201
 202                         case OP_MOVE:
 203                                 tmp = (MonoInst*)g_hash_table_lookup (addr_loads, GINT_TO_POINTER (ins->sreg1));
 204                                 /*
 205                                 Forward propagate known aliases
 206                                 ldaddr R10 <- R8
 207                                 mov R11 <- R10
 208                                 */
 209                                 if (tmp) {
 210                                         g_hash_table_insert (addr_loads, GINT_TO_POINTER (ins->dreg), tmp);
 211                                         if (cfg->verbose_level > 2) { printf ("New alias: "); mono_print_ins (ins); }
 212                                 } else {
 213                                         /*
 214                                         Source value is not a know address, kill the variable.
 215                                         */
 216                                         if (g_hash_table_remove (addr_loads, GINT_TO_POINTER (ins->dreg))) {
 217                                                 if (cfg->verbose_level > 2) { printf ("Killed alias: "); mono_print_ins (ins); }
 218                                         }
 219                                 }
 220                                 break;
 221
 222                         case OP_LOADV_MEMBASE:
 223                         case OP_LOAD_MEMBASE:
 224                         case OP_LOADU1_MEMBASE:
 225                         case OP_LOADI2_MEMBASE:
 226                         case OP_LOADU2_MEMBASE:
 227                         case OP_LOADI4_MEMBASE:
 228                         case OP_LOADU4_MEMBASE:
 229                         case OP_LOADI1_MEMBASE:
 230                         case OP_LOADI8_MEMBASE:
 231 #ifndef MONO_ARCH_SOFT_FLOAT_FALLBACK
 232                         case OP_LOADR4_MEMBASE:
 233 #endif
 234                         case OP_LOADR8_MEMBASE:
 235                                 if (ins->inst_offset != 0)
 236                                         continue;
 237                                 tmp = (MonoInst *)g_hash_table_lookup (addr_loads, GINT_TO_POINTER (ins->sreg1));
 238                                 if (tmp) {
 239                                         if (cfg->verbose_level > 2) { printf ("Found candidate load:"); mono_print_ins (ins); }
 240                                         if (lower_load (cfg, ins, tmp)) {
 241                                                 needs_dce = TRUE;
 242                                                 /* Try to propagate known aliases if an OP_MOVE was inserted */
 243                                                 goto handle_instruction;
 244                                         }
 245                                 }
 246                                 break;
 247
 248                         case OP_STORE_MEMBASE_REG:
 249                         case OP_STOREI1_MEMBASE_REG:
 250                         case OP_STOREI2_MEMBASE_REG:
 251                         case OP_STOREI4_MEMBASE_REG:
 252                         case OP_STOREI8_MEMBASE_REG:
 253 #ifndef MONO_ARCH_SOFT_FLOAT_FALLBACK
 254                         case OP_STORER4_MEMBASE_REG:
 255 #endif
 256                         case OP_STORER8_MEMBASE_REG:
 257                         case OP_STOREV_MEMBASE:
 258                                 if (ins->inst_offset != 0)
 259                                         continue;
 260                                 tmp = (MonoInst *)g_hash_table_lookup (addr_loads, GINT_TO_POINTER (ins->dreg));
 261                                 if (tmp) {
 262                                         if (cfg->verbose_level > 2) { printf ("Found candidate store:"); mono_print_ins (ins); }
 263                                         if (lower_store (cfg, ins, tmp)) {
 264                                                 needs_dce = TRUE;
 265                                                 /* Try to propagate known aliases if an OP_MOVE was inserted */
 266                                                 goto handle_instruction;
 267                                         }
 268                                 }
 269                                 break;
 270                         //FIXME missing storei1_membase_imm and storei2_membase_imm
 271                         case OP_STORE_MEMBASE_IMM:
 272                         case OP_STOREI4_MEMBASE_IMM:
 273                         case OP_STOREI8_MEMBASE_IMM:
 274                                 if (ins->inst_offset != 0)
 275                                         continue;
 276                                 tmp = (MonoInst *)g_hash_table_lookup (addr_loads, GINT_TO_POINTER (ins->dreg));
 277                                 if (tmp) {
 278                                         if (cfg->verbose_level > 2) { printf ("Found candidate store-imm:"); mono_print_ins (ins); }
 279                                         needs_dce |= lower_store_imm (cfg, ins, tmp);
 280                                 }
 281                                 break;
 282                         case OP_CHECK_THIS:
 283                         case OP_NOT_NULL:
 284                                 tmp = (MonoInst *)g_hash_table_lookup (addr_loads, GINT_TO_POINTER (ins->sreg1));
 285                                 if (tmp) {
 286                                         if (cfg->verbose_level > 2) { printf ("Found null check over local: "); mono_print_ins (ins); }
 287                                         NULLIFY_INS (ins);
 288                                         needs_dce = TRUE;
 289                                 }
 290                                 break;
 291                         default: {
 292                                 if (MONO_IS_CALL (ins)) {
 293                                         MonoCallInst *call = (MonoCallInst*)ins;
 294
 295                                         kill_call_arg_alias (cfg, addr_loads, call->out_ireg_args);
 296                                 }
 297                                 // FIXME Kill more aliases if used as dreg, since we are not in ssa form.
 298                                 // This would need some optimizations so we don't lookup hash table for every
 299                                 // instruction
 300                                 break;
 301                         }
 302                         }
 303                 }
 304         }
 305         g_hash_table_destroy (addr_loads);
 306
 307 #ifdef ENABLE_NETCORE
 308         /* There could be ldaddr instructions which already got eliminated */
 309         if (COMPILE_LLVM (cfg))
 310                 return TRUE;
 311 #endif
 312         return needs_dce;
 313 }
 314
 315 static gboolean
 316 recompute_aliased_variables (MonoCompile *cfg, int *restored_vars)
 317 {
 318         int i;
 319         MonoBasicBlock *bb;
 320         MonoInst *ins;
 321         int kills = 0;
 322         int adds = 0;
 323         *restored_vars = 0;
 324
 325         for (i = 0; i < cfg->num_varinfo; i++) {
 326                 MonoInst *var = cfg->varinfo [i];
 327                 if (var->flags & MONO_INST_INDIRECT) {
 328                         if (cfg->verbose_level > 2) {
 329                                 printf ("Killing :"); mono_print_ins (var);
 330                         }
 331                         ++kills;
 332                 }
 333                 var->flags &= ~MONO_INST_INDIRECT;
 334         }
 335
 336         if (!kills)
 337                 return FALSE;
 338
 339         for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
 340                 for (ins = bb->code; ins; ins = ins->next) {
 341                         if (ins->opcode == OP_LDADDR) {
 342                                 MonoInst *var;
 343
 344                                 if (cfg->verbose_level > 2) { printf ("Found op :"); mono_print_ins (ins); }
 345
 346                                 var = (MonoInst*)ins->inst_p0;
 347                                 if (!(var->flags & MONO_INST_INDIRECT)) {
 348                                         if (cfg->verbose_level > 1) { printf ("Restoring :"); mono_print_ins (var); }
 349                                         ++adds;
 350                                 }
 351                                 var->flags |= MONO_INST_INDIRECT;
 352                         }
 353                 }
 354         }
 355         *restored_vars = adds;
 356
 357         mono_atomic_fetch_add_i32 (&mono_jit_stats.alias_found, kills);
 358         mono_atomic_fetch_add_i32 (&mono_jit_stats.alias_removed, kills - adds);
 359         if (kills > adds) {
 360                 if (cfg->verbose_level > 2) {
 361                         printf ("Method: %s\n", mono_method_full_name (cfg->method, 1));
 362                         printf ("Kills %d Adds %d\n", kills, adds);
 363                 }
 364                 return TRUE;
 365         }
 366         return FALSE;
 367 }
 368
 369 /*
 370 FIXME:
 371         Don't DCE on the whole CFG, only the BBs that have changed.
 372
 373 TODO:
 374         SRVT of small types can fix cases of mismatch for fields of a different type than the component.
 375         Handle aliasing of byrefs in call conventions.
 376 */
 377 void
 378 mono_local_alias_analysis (MonoCompile *cfg)
 379 {
 380         int i, restored_vars = 1;
 381         if (!cfg->has_indirection)
 382                 return;
 383
 384         if (cfg->verbose_level > 2)
 385                 mono_print_code (cfg, "BEFORE ALIAS_ANALYSIS");
 386
 387         /*
 388         Remove indirection and memory access of known variables.
 389         */
 390         if (!lower_memory_access (cfg))
 391                 goto done;
 392
 393         /*
 394         By replacing indirect access with direct operations, some LDADDR ops become dead. Kill them.
 395         */
 396         if (cfg->opt & MONO_OPT_DEADCE)
 397                 mono_local_deadce (cfg);
 398
 399         /*
 400         Some variables no longer need to be flagged as indirect, find them.
 401         Since indirect vars are converted into global vregs, each pass eliminates only one level of indirection.
 402         Most cases only need one pass and some 2.
 403         */
 404         for (i = 0; i < 3 && restored_vars > 0 && recompute_aliased_variables (cfg, &restored_vars); ++i) {
 405                 /*
 406                 A lot of simplification just took place, we recompute local variables and do DCE to
 407                 really profit from the previous gains
 408                 */
 409                 mono_handle_global_vregs (cfg);
 410                 if (cfg->opt & MONO_OPT_DEADCE)
 411                         mono_local_deadce (cfg);
 412         }
 413
 414 done:
 415         if (cfg->verbose_level > 2)
 416                 mono_print_code (cfg, "AFTER ALIAS_ANALYSIS");
 417 }
 418
 419 #else /* !DISABLE_JIT */
 420
 421 MONO_EMPTY_SOURCE_FILE (alias_analysis);
 422
 423 #endif /* !DISABLE_JIT */