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