mono/mini/cfold.c

   1 /*
   2  * cfold.c: Constant folding support
   3  *
   4  * Author:
   5  *   Paolo Molaro (lupus@ximian.com)
   6  *   Dietmar Maurer (dietmar@ximian.com)
   7  *
   8  * (C) 2003 Ximian, Inc.  http://www.ximian.com
   9  */
  10 #include "mini.h"
  11
  12 int
  13 mono_is_power_of_two (guint32 val)
  14 {
  15         int i, j, k;
  16
  17         for (i = 0, j = 1, k = 0xfffffffe; i < 32; ++i, j = j << 1, k = k << 1) {
  18                 if (val & j)
  19                         break;
  20         }
  21         if (i == 32 || val & k)
  22                 return -1;
  23         return i;
  24 }
  25
  26 #ifndef G_MININT32
  27 #define MYGINT32_MAX 2147483647
  28 #define G_MININT32 (-MYGINT32_MAX -1)
  29 #endif
  30
  31 #define FOLD_UNOP(name,op)      \
  32         case name:      \
  33             dest->inst_c0 = op arg1->inst_c0; \
  34         break;
  35
  36 #define FOLD_BINOP(name, op) \
  37         case name:      \
  38             dest->inst_c0 = arg1->inst_c0 op arg2->inst_c0;     \
  39         break;
  40
  41 #define FOLD_BINOPC(name,op,cast)       \
  42         case name:      \
  43             dest->inst_c0 = (cast)arg1->inst_c0 op (cast)arg2->inst_c0; \
  44         break;
  45
  46 #define FOLD_BINOP2_IMM(name, op) \
  47         case name:      \
  48             dest->inst_c0 = arg1->inst_c0 op ins->inst_imm;     \
  49         break;
  50
  51 #define FOLD_BINOPC2_IMM(name, op, cast) \
  52         case name:      \
  53             dest->inst_c0 = (cast)arg1->inst_c0 op (cast)ins->inst_imm; \
  54         break;
  55
  56 #define FOLD_BINOPCXX(name,op,cast)     \
  57         case name:      \
  58             res = (cast)arg1->inst_c0 op (cast)arg2->inst_c0;   \
  59         break; \
  60
  61 #undef MONO_INST_NEW
  62 #define MONO_INST_NEW(cfg,dest,op) do { \
  63                 (dest) = mono_mempool_alloc ((cfg)->mempool, sizeof (MonoInst));        \
  64         (dest)->inst_p0 = (dest)->inst_p1 = (dest)->next = NULL; \
  65                 (dest)->opcode = (op);  \
  66         (dest)->flags = 0; \
  67         (dest)->dreg = (dest)->sreg1 = (dest)->sreg2 = -1;  \
  68         } while (0)
  69
  70 #define ALLOC_DEST(cfg, dest, ins) do { \
  71     if (!(dest)) { \
  72         MONO_INST_NEW ((cfg), (dest), -1); \
  73         (dest)->dreg = (ins)->dreg; \
  74     } \
  75 } while (0)
  76
  77 /**
  78  * mono_constant_fold_ins:
  79  *
  80  * Perform constant folding on INS, using ARG1 and ARG2 as the arguments. If OVERWRITE is
  81  * true, then store the result back into INS and return INS. Otherwise allocate a new ins,
  82  * store the result into it and return it. If constant folding cannot be performed, return
  83  * NULL.
  84  */
  85 MonoInst*
  86 mono_constant_fold_ins (MonoCompile *cfg, MonoInst *ins, MonoInst *arg1, MonoInst *arg2, gboolean overwrite)
  87 {
  88         MonoInst *dest = NULL;
  89
  90         if (overwrite)
  91                 dest = ins;
  92
  93         switch (ins->opcode) {
  94         case OP_IMUL:
  95         case OP_IADD:
  96         case OP_IAND:
  97         case OP_IOR:
  98         case OP_IXOR:
  99                 if (arg2->opcode == OP_ICONST) {
 100                         if (arg1->opcode == OP_ICONST) {
 101                                 ALLOC_DEST (cfg, dest, ins);
 102                                 switch (ins->opcode) {
 103                                         FOLD_BINOP (OP_IMUL, *);
 104                                         FOLD_BINOP (OP_IADD, +);
 105                                         FOLD_BINOP (OP_IAND, &);
 106                                         FOLD_BINOP (OP_IOR, |);
 107                                         FOLD_BINOP (OP_IXOR, ^);
 108                                 }
 109                                 dest->opcode = OP_ICONST;
 110                                 dest->sreg1 = dest->sreg2 = -1;
 111                         }
 112                 } else if (arg1->opcode == OP_ICONST) {
 113                         /*
 114                          * This is commutative so swap the arguments, allowing the _imm variant
 115                          * to be used later.
 116                          */
 117                         if (mono_op_to_op_imm (ins->opcode) != -1) {
 118                                 ALLOC_DEST (cfg, dest, ins);
 119                                 dest->opcode = mono_op_to_op_imm (ins->opcode);
 120                                 dest->sreg1 = ins->sreg2;
 121                                 dest->sreg2 = -1;
 122                                 dest->inst_imm = arg1->inst_c0;
 123                         }
 124                 }
 125                 break;
 126         case OP_IMUL_IMM:
 127         case OP_IADD_IMM:
 128         case OP_IAND_IMM:
 129         case OP_IOR_IMM:
 130         case OP_IXOR_IMM:
 131         case OP_ISUB_IMM:
 132         case OP_ISHL_IMM:
 133         case OP_ISHR_IMM:
 134         case OP_ISHR_UN_IMM:
 135         case OP_SHL_IMM:
 136                 if (arg1->opcode == OP_ICONST) {
 137                         ALLOC_DEST (cfg, dest, ins);
 138                         switch (ins->opcode) {
 139                                 FOLD_BINOP2_IMM (OP_IMUL_IMM, *);
 140                                 FOLD_BINOP2_IMM (OP_IADD_IMM, +);
 141                                 FOLD_BINOP2_IMM (OP_IAND_IMM, &);
 142                                 FOLD_BINOP2_IMM (OP_IOR_IMM, |);
 143                                 FOLD_BINOP2_IMM (OP_IXOR_IMM, ^);
 144                                 FOLD_BINOP2_IMM (OP_ISUB_IMM, -);
 145                                 FOLD_BINOP2_IMM (OP_ISHL_IMM, <<);
 146                                 FOLD_BINOP2_IMM (OP_ISHR_IMM, >>);
 147                                 FOLD_BINOPC2_IMM (OP_ISHR_UN_IMM, >>, guint32);
 148                                 FOLD_BINOP2_IMM (OP_SHL_IMM, <<);
 149                         }
 150                         dest->opcode = OP_ICONST;
 151                         dest->sreg1 = dest->sreg2 = -1;
 152                 }
 153                 break;
 154         case OP_ISUB:
 155         case OP_ISHL:
 156         case OP_ISHR:
 157         case OP_ISHR_UN:
 158                 if ((arg1->opcode == OP_ICONST) && (arg2->opcode == OP_ICONST)) {
 159                         ALLOC_DEST (cfg, dest, ins);
 160                         switch (ins->opcode) {
 161                                 FOLD_BINOP (OP_ISUB, -);
 162                                 FOLD_BINOP (OP_ISHL, <<);
 163                                 FOLD_BINOP (OP_ISHR, >>);
 164                                 FOLD_BINOPC (OP_ISHR_UN, >>, guint32);
 165                         }
 166                         dest->opcode = OP_ICONST;
 167                         dest->sreg1 = dest->sreg2 = -1;
 168                 }
 169                 break;
 170         case OP_IDIV:
 171         case OP_IDIV_UN:
 172         case OP_IREM:
 173         case OP_IREM_UN:
 174                 if ((arg1->opcode == OP_ICONST) && (arg2->opcode == OP_ICONST)) {
 175                         if ((arg2->inst_c0 == 0) || ((arg1->inst_c0 == G_MININT32) && (arg2->inst_c0 == -1)))
 176                                 return NULL;
 177                         ALLOC_DEST (cfg, dest, ins);
 178                         switch (ins->opcode) {
 179                                 FOLD_BINOPC (OP_IDIV, /, gint32);
 180                                 FOLD_BINOPC (OP_IDIV_UN, /, guint32);
 181                                 FOLD_BINOPC (OP_IREM, %, gint32);
 182                                 FOLD_BINOPC (OP_IREM_UN, %, guint32);
 183                         }
 184                         dest->opcode = OP_ICONST;
 185                         dest->sreg1 = dest->sreg2 = -1;
 186                 }
 187                 break;
 188         case OP_IDIV_IMM:
 189         case OP_IDIV_UN_IMM:
 190         case OP_IREM_IMM:
 191         case OP_IREM_UN_IMM:
 192                 if (arg1->opcode == OP_ICONST) {
 193                         if ((ins->inst_imm == 0) || ((arg1->inst_c0 == G_MININT32) && (ins->inst_imm == -1)))
 194                                 return NULL;
 195                         ALLOC_DEST (cfg, dest, ins);
 196                         switch (ins->opcode) {
 197                                 FOLD_BINOPC2_IMM (OP_IDIV_IMM, /, gint32);
 198                                 FOLD_BINOPC2_IMM (OP_IDIV_UN_IMM, /, guint32);
 199                                 FOLD_BINOPC2_IMM (OP_IREM_IMM, %, gint32);
 200                                 FOLD_BINOPC2_IMM (OP_IREM_UN_IMM, %, guint32);
 201                         default:
 202                                 g_assert_not_reached ();
 203                         }
 204                         dest->opcode = OP_ICONST;
 205                         dest->sreg1 = dest->sreg2 = -1;
 206                 }
 207                 break;
 208                 /* case OP_INEG: */
 209         case OP_INOT:
 210         case OP_INEG:
 211                 if (arg1->opcode == OP_ICONST) {
 212                         /* INEG sets cflags on x86, and the LNEG decomposition depends on that */
 213                         if ((ins->opcode == OP_INEG) && ins->next && (ins->next->opcode == OP_ADC_IMM))
 214                                 return NULL;
 215                         ALLOC_DEST (cfg, dest, ins);
 216                         switch (ins->opcode) {
 217                                 FOLD_UNOP (OP_INEG,-);
 218                                 FOLD_UNOP (OP_INOT,~);
 219                         }
 220                         dest->opcode = OP_ICONST;
 221                         dest->sreg1 = dest->sreg2 = -1;
 222                 }
 223                 break;
 224         case OP_MOVE:
 225 #if SIZEOF_REGISTER == 8
 226                 if ((arg1->opcode == OP_ICONST) || (arg1->opcode == OP_I8CONST)) {
 227 #else
 228                 if (arg1->opcode == OP_ICONST) {
 229 #endif
 230                         ALLOC_DEST (cfg, dest, ins);
 231                         dest->opcode = arg1->opcode;
 232                         dest->sreg1 = dest->sreg2 = -1;
 233                         dest->inst_c0 = arg1->inst_c0;
 234                 }
 235                 break;
 236         case OP_VMOVE:
 237                 if (arg1->opcode == OP_VZERO) {
 238                         ALLOC_DEST (cfg, dest, ins);
 239                         dest->opcode = OP_VZERO;
 240                         dest->sreg1 = -1;
 241                 }
 242                 break;
 243         case OP_XMOVE:
 244                 if (arg1->opcode == OP_XZERO) {
 245                         ALLOC_DEST (cfg, dest, ins);
 246                         dest->opcode = OP_XZERO;
 247                         dest->sreg1 = -1;
 248                 }
 249                 break;
 250         case OP_COMPARE:
 251         case OP_ICOMPARE:
 252         case OP_COMPARE_IMM:
 253         case OP_ICOMPARE_IMM: {
 254                 MonoInst dummy_arg2;
 255                 if (ins->sreg2 == -1) {
 256                         arg2 = &dummy_arg2;
 257                         arg2->opcode = OP_ICONST;
 258                         arg2->inst_c0 = ins->inst_imm;
 259                 }
 260
 261                 if ((arg1->opcode == OP_ICONST) && (arg2->opcode == OP_ICONST) && ins->next) {
 262                         MonoInst *next = ins->next;
 263                         gboolean res = FALSE;
 264
 265                         switch (next->opcode) {
 266                         case OP_CEQ:
 267                         case OP_ICEQ:
 268                         case OP_CGT:
 269                         case OP_ICGT:
 270                         case OP_CGT_UN:
 271                         case OP_ICGT_UN:
 272                         case OP_CLT:
 273                         case OP_ICLT:
 274                         case OP_CLT_UN:
 275                         case OP_ICLT_UN:
 276                                 switch (next->opcode) {
 277                                         FOLD_BINOPCXX (OP_CEQ,==,gint32);
 278                                         FOLD_BINOPCXX (OP_ICEQ,==,gint32);
 279                                         FOLD_BINOPCXX (OP_CGT,>,gint32);
 280                                         FOLD_BINOPCXX (OP_ICGT,>,gint32);
 281                                         FOLD_BINOPCXX (OP_CGT_UN,>,guint32);
 282                                         FOLD_BINOPCXX (OP_ICGT_UN,>,guint32);
 283                                         FOLD_BINOPCXX (OP_CLT,<,gint32);
 284                                         FOLD_BINOPCXX (OP_ICLT,<,gint32);
 285                                         FOLD_BINOPCXX (OP_CLT_UN,<,guint32);
 286                                         FOLD_BINOPCXX (OP_ICLT_UN,<,guint32);
 287                                 }
 288
 289                                 if (overwrite) {
 290                                         NULLIFY_INS (ins);
 291                                         next->opcode = OP_ICONST;
 292                                         next->inst_c0 = res;
 293                                         next->sreg1 = next->sreg2 = -1;
 294                                 } else {
 295                                         ALLOC_DEST (cfg, dest, ins);
 296                                         dest->opcode = OP_ICONST;
 297                                         dest->inst_c0 = res;
 298                                 }
 299                                 break;
 300                         case OP_IBEQ:
 301                         case OP_IBNE_UN:
 302                         case OP_IBGT:
 303                         case OP_IBGT_UN:
 304                         case OP_IBGE:
 305                         case OP_IBGE_UN:
 306                         case OP_IBLT:
 307                         case OP_IBLT_UN:
 308                         case OP_IBLE:
 309                         case OP_IBLE_UN:
 310                                 switch (next->opcode) {
 311                                         FOLD_BINOPCXX (OP_IBEQ,==,gint32);
 312                                         FOLD_BINOPCXX (OP_IBNE_UN,!=,guint32);
 313                                         FOLD_BINOPCXX (OP_IBGT,>,gint32);
 314                                         FOLD_BINOPCXX (OP_IBGT_UN,>,guint32);
 315                                         FOLD_BINOPCXX (OP_IBGE,>=,gint32);
 316                                         FOLD_BINOPCXX (OP_IBGE_UN,>=,guint32);
 317                                         FOLD_BINOPCXX (OP_IBLT,<,gint32);
 318                                         FOLD_BINOPCXX (OP_IBLT_UN,<,guint32);
 319                                         FOLD_BINOPCXX (OP_IBLE,<=,gint32);
 320                                         FOLD_BINOPCXX (OP_IBLE_UN,<=,guint32);
 321                                 }
 322
 323                                 if (overwrite) {
 324                                         /*
 325                                          * Can't nullify OP_COMPARE here since the decompose long branch
 326                                          * opcodes depend on it being executed. Also, the branch might not
 327                                          * be eliminated after all if loop opts is disabled, for example.
 328                                          */
 329                                         if (res)
 330                                                 next->flags |= MONO_INST_CFOLD_TAKEN;
 331                                         else
 332                                                 next->flags |= MONO_INST_CFOLD_NOT_TAKEN;
 333                                 } else {
 334                                         ALLOC_DEST (cfg, dest, ins);
 335                                         dest->opcode = OP_ICONST;
 336                                         dest->inst_c0 = res;
 337                                 }
 338                                 break;
 339                         case OP_NOP:
 340                         case OP_BR:
 341                                 /* This happens when a conditional branch is eliminated */
 342                                 if (next->next == NULL) {
 343                                         /* Last ins */
 344                                         if (overwrite)
 345                                                 NULLIFY_INS (ins);
 346                                 }
 347                                 break;
 348                         default:
 349                                 return NULL;
 350                         }
 351                 }
 352                 break;
 353         }
 354         case OP_FMOVE:
 355                 if (arg1->opcode == OP_R8CONST) {
 356                         ALLOC_DEST (cfg, dest, ins);
 357                         dest->opcode = OP_R8CONST;
 358                         dest->sreg1 = -1;
 359                         dest->inst_p0 = arg1->inst_p0;
 360                 }
 361                 break;
 362
 363                 /*
 364                  * TODO:
 365                  *      conv.* opcodes.
 366                  *      *ovf* opcodes? It's slow and hard to do in C.
 367                  *      switch can be replaced by a simple jump
 368                  */
 369         default:
 370                 return NULL;
 371         }
 372
 373     return dest;
 374 }