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