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 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         return needs_dce;
 307 }
 308
 309 static gboolean
 310 recompute_aliased_variables (MonoCompile *cfg, int *restored_vars)
 311 {
 312         int i;
 313         MonoBasicBlock *bb;
 314         MonoInst *ins;
 315         int kills = 0;
 316         int adds = 0;
 317         *restored_vars = 0;
 318
 319         for (i = 0; i < cfg->num_varinfo; i++) {
 320                 MonoInst *var = cfg->varinfo [i];
 321                 if (var->flags & MONO_INST_INDIRECT) {
 322                         if (cfg->verbose_level > 2) {
 323                                 printf ("Killing :"); mono_print_ins (var);
 324                         }
 325                         ++kills;
 326                 }
 327                 var->flags &= ~MONO_INST_INDIRECT;
 328         }
 329
 330         if (!kills)
 331                 return FALSE;
 332
 333         for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
 334                 for (ins = bb->code; ins; ins = ins->next) {
 335                         if (ins->opcode == OP_LDADDR) {
 336                                 MonoInst *var;
 337
 338                                 if (cfg->verbose_level > 2) { printf ("Found op :"); mono_print_ins (ins); }
 339
 340                                 var = (MonoInst*)ins->inst_p0;
 341                                 if (!(var->flags & MONO_INST_INDIRECT)) {
 342                                         if (cfg->verbose_level > 1) { printf ("Restoring :"); mono_print_ins (var); }
 343                                         ++adds;
 344                                 }
 345                                 var->flags |= MONO_INST_INDIRECT;
 346                         }
 347                 }
 348         }
 349         *restored_vars = adds;
 350
 351         mono_atomic_fetch_add_i32 (&mono_jit_stats.alias_found, kills);
 352         mono_atomic_fetch_add_i32 (&mono_jit_stats.alias_removed, kills - adds);
 353         if (kills > adds) {
 354                 if (cfg->verbose_level > 2) {
 355                         printf ("Method: %s\n", mono_method_full_name (cfg->method, 1));
 356                         printf ("Kills %d Adds %d\n", kills, adds);
 357                 }
 358                 return TRUE;
 359         }
 360         return FALSE;
 361 }
 362
 363 /*
 364 FIXME:
 365         Don't DCE on the whole CFG, only the BBs that have changed.
 366
 367 TODO:
 368         SRVT of small types can fix cases of mismatch for fields of a different type than the component.
 369         Handle aliasing of byrefs in call conventions.
 370 */
 371 void
 372 mono_local_alias_analysis (MonoCompile *cfg)
 373 {
 374         int i, restored_vars = 1;
 375         if (!cfg->has_indirection)
 376                 return;
 377
 378         if (cfg->verbose_level > 2)
 379                 mono_print_code (cfg, "BEFORE ALIAS_ANALYSIS");
 380
 381         /*
 382         Remove indirection and memory access of known variables.
 383         */
 384         if (!lower_memory_access (cfg))
 385                 goto done;
 386
 387         /*
 388         By replacing indirect access with direct operations, some LDADDR ops become dead. Kill them.
 389         */
 390         if (cfg->opt & MONO_OPT_DEADCE)
 391                 mono_local_deadce (cfg);
 392
 393         /*
 394         Some variables no longer need to be flagged as indirect, find them.
 395         Since indirect vars are converted into global vregs, each pass eliminates only one level of indirection.
 396         Most cases only need one pass and some 2.
 397         */
 398         for (i = 0; i < 3 && restored_vars > 0 && recompute_aliased_variables (cfg, &restored_vars); ++i) {
 399                 /*
 400                 A lot of simplification just took place, we recompute local variables and do DCE to
 401                 really profit from the previous gains
 402                 */
 403                 mono_handle_global_vregs (cfg);
 404                 if (cfg->opt & MONO_OPT_DEADCE)
 405                         mono_local_deadce (cfg);
 406         }
 407
 408 done:
 409         if (cfg->verbose_level > 2)
 410                 mono_print_code (cfg, "AFTER ALIAS_ANALYSIS");
 411 }
 412
 413 #else /* !DISABLE_JIT */
 414
 415 MONO_EMPTY_SOURCE_FILE (alias_analysis);
 416
 417 #endif /* !DISABLE_JIT */