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