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