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 #define FOLD_BINOP(name,op)     \
  27         case name:      \
  28                 if (inst->inst_i0->opcode != OP_ICONST) \
  29                         return; \
  30                 if (inst->inst_i1->opcode == OP_ICONST) {       \
  31                         inst->opcode = OP_ICONST;       \
  32                         inst->inst_c0 = inst->inst_i0->inst_c0 op inst->inst_i1->inst_c0;       \
  33                 } \
  34                 return;
  35
  36 /*
  37  * We try to put constants on the left side of a commutative operation
  38  * because it reduces register pressure and it matches the usual cpu
  39  * instructions with immediates.
  40  */
  41 #define FOLD_BINOPCOMM(name,op) \
  42         case name:      \
  43                 if (inst->inst_i0->opcode == OP_ICONST) {\
  44                         if (inst->inst_i1->opcode == OP_ICONST) {       \
  45                                 inst->opcode = OP_ICONST;       \
  46                                 inst->inst_c0 = inst->inst_i0->inst_c0 op inst->inst_i1->inst_c0;       \
  47                                 return; \
  48                         } else { \
  49                                 MonoInst *tmp = inst->inst_i0;  \
  50                                 inst->inst_i0 = inst->inst_i1;  \
  51                                 inst->inst_i1 = tmp;    \
  52                        } \
  53                 } \
  54                 if (inst->inst_i1->opcode == OP_ICONST && inst->opcode == CEE_ADD) {    \
  55                         if (inst->inst_i1->inst_c0 == 0) { \
  56                                 *inst = *(inst->inst_i0); \
  57                                 return; \
  58                         } \
  59                 } \
  60                 if (inst->inst_i1->opcode == OP_ICONST && inst->opcode == CEE_MUL) {    \
  61                         int power2;     \
  62                         if (inst->inst_i1->inst_c0 == 1) {      \
  63                                 *inst = *(inst->inst_i0);       \
  64                                 return; \
  65                         } else if (inst->inst_i1->inst_c0 == -1) {      \
  66                                 inst->opcode = CEE_NEG; \
  67                                 return; \
  68                         }       \
  69                         power2 = mono_is_power_of_two (inst->inst_i1->inst_c0); \
  70                         if (power2 < 0) return; \
  71                         inst->opcode = CEE_SHL; \
  72                         inst->inst_i1->inst_c0 = power2;        \
  73                 } \
  74                 return;
  75
  76 #ifndef G_MININT32
  77 #define MYGINT32_MAX 2147483647
  78 #define G_MININT32 (-MYGINT32_MAX -1)
  79 #endif
  80
  81 /*
  82  * We can't let this cause a division by zero exception since the division
  83  * might not be executed during runtime.
  84  */
  85 #define FOLD_BINOPZ(name,op,cast)       \
  86         case name:      \
  87                 if (inst->inst_i1->opcode == OP_ICONST && inst->opcode == CEE_REM_UN && inst->inst_i1->inst_c0 == 2) {  \
  88                         inst->opcode = CEE_AND; \
  89                         inst->inst_i1->inst_c0 = 1;     \
  90                         return; \
  91                 }       \
  92                 if (inst->inst_i1->opcode == OP_ICONST) {       \
  93                         if (!inst->inst_i1->inst_c0) return;    \
  94                         if (inst->inst_i0->opcode == OP_ICONST) {       \
  95                 if ((inst->inst_i0->inst_c0 == G_MININT32) && (inst->inst_i1->inst_c0 == -1)) \
  96                     return; \
  97                                 inst->inst_c0 = (cast)inst->inst_i0->inst_c0 op (cast)inst->inst_i1->inst_c0;   \
  98                                 inst->opcode = OP_ICONST;       \
  99                         } else {        \
 100                                 int power2 = mono_is_power_of_two (inst->inst_i1->inst_c0);     \
 101                                 if (power2 < 0) return; \
 102                                 if (inst->opcode == CEE_REM_UN) {       \
 103                                         inst->opcode = CEE_AND; \
 104                                         inst->inst_i1->inst_c0 = (1 << power2) - 1;     \
 105                                 } else if (inst->opcode == CEE_DIV_UN) {        \
 106                                         inst->opcode = CEE_SHR_UN;      \
 107                                         inst->inst_i1->inst_c0 = power2;        \
 108                                 }       \
 109                         }       \
 110                 } \
 111                 return;
 112
 113 #define FOLD_BINOPA(name,op,cast)       \
 114         case name:      \
 115                 if (inst->inst_i0->opcode != OP_ICONST) \
 116                         return; \
 117                 if (inst->inst_i1->opcode == OP_ICONST) {       \
 118                         inst->opcode = OP_ICONST;       \
 119                         inst->inst_c0 = (cast)inst->inst_i0->inst_c0 op (cast)inst->inst_i1->inst_c0;   \
 120                 } \
 121                 return;
 122
 123 #define FOLD_CXX(name,op,cast)  \
 124         case name:      \
 125                 if (inst->inst_i0->opcode != OP_COMPARE)        \
 126                         return; \
 127                 if (inst->inst_i0->inst_i0->opcode != OP_ICONST)        \
 128                         return; \
 129                 if (inst->inst_i0->inst_i1->opcode == OP_ICONST) {      \
 130                         inst->opcode = OP_ICONST;       \
 131                         inst->inst_c0 = (cast)inst->inst_i0->inst_i0->inst_c0 op (cast)inst->inst_i0->inst_i1->inst_c0; \
 132                 } \
 133                 return;
 134
 135 #define FOLD_UNOP(name,op)      \
 136         case name:      \
 137                 if (inst->inst_i0->opcode == OP_ICONST) {       \
 138                         inst->opcode = OP_ICONST;       \
 139                         inst->inst_c0 = op inst->inst_i0->inst_c0; \
 140                 } else if (inst->inst_i0->opcode == OP_I8CONST) { \
 141                         inst->opcode = OP_I8CONST;      \
 142                         inst->inst_l = op inst->inst_i0->inst_l; \
 143                 } return;
 144
 145 #define FOLD_BRBINOP(name,op,cast)      \
 146         case name:      \
 147                 if (inst->inst_i0->opcode != OP_COMPARE)        \
 148                         return; \
 149                 if (inst->inst_i0->inst_i0->opcode != OP_ICONST)        \
 150                         return; \
 151                 if (inst->inst_i0->inst_i1->opcode == OP_ICONST) {      \
 152                         if ((cast)inst->inst_i0->inst_i0->inst_c0 op (cast)inst->inst_i0->inst_i1->inst_c0)     \
 153                                 inst->opcode = CEE_BR;  \
 154                         else    \
 155                                 inst->opcode = CEE_NOP; \
 156                 } \
 157                 return;
 158
 159 /*
 160  * Helper function to do constant expression evaluation.
 161  * We do constant folding of integers only, FP stuff is much more tricky,
 162  * int64 probably not worth it.
 163  */
 164 void
 165 mono_constant_fold_inst (MonoInst *inst, gpointer data)
 166 {
 167         switch (inst->opcode) {
 168
 169         /* FIXME: the CEE_B* don't contain operands, need to use the OP_COMPARE instruction */
 170         /*FOLD_BRBINOP (CEE_BEQ,==,gint32)
 171         FOLD_BRBINOP (CEE_BGE,>=,gint32)
 172         FOLD_BRBINOP (CEE_BGT,>,gint32)
 173         FOLD_BRBINOP (CEE_BLE,<=,gint32)
 174         FOLD_BRBINOP (CEE_BLT,<,gint32)
 175         FOLD_BRBINOP (CEE_BNE_UN,!=,guint32)
 176         FOLD_BRBINOP (CEE_BGE_UN,>=,guint32)
 177         FOLD_BRBINOP (CEE_BGT_UN,>,guint32)
 178         FOLD_BRBINOP (CEE_BLE_UN,<=,guint32)
 179         FOLD_BRBINOP (CEE_BLT_UN,<,guint32)*/
 180
 181         FOLD_BINOPCOMM (CEE_MUL,*)
 182
 183         FOLD_BINOPCOMM (CEE_ADD,+)
 184         FOLD_BINOP (CEE_SUB,-)
 185         FOLD_BINOPZ (CEE_DIV,/,gint32)
 186         FOLD_BINOPZ (CEE_DIV_UN,/,guint32)
 187         FOLD_BINOPZ (CEE_REM,%,gint32)
 188         FOLD_BINOPZ (CEE_REM_UN,%,guint32)
 189         FOLD_BINOPCOMM (CEE_AND,&)
 190         FOLD_BINOPCOMM (CEE_OR,|)
 191         FOLD_BINOPCOMM (CEE_XOR,^)
 192         FOLD_BINOP (CEE_SHL,<<)
 193         FOLD_BINOP (CEE_SHR,>>)
 194         case CEE_SHR_UN:
 195                 if (inst->inst_i0->opcode != OP_ICONST)
 196                         return;
 197                 if (inst->inst_i1->opcode == OP_ICONST) {
 198                         inst->opcode = OP_ICONST;
 199                         inst->inst_c0 = (guint32)inst->inst_i0->inst_c0 >> (guint32)inst->inst_i1->inst_c0;
 200                 }
 201                 return;
 202         FOLD_UNOP (CEE_NEG,-)
 203         FOLD_UNOP (CEE_NOT,~)
 204         FOLD_CXX (OP_CEQ,==,gint32)
 205         FOLD_CXX (OP_CGT,>,gint32)
 206         FOLD_CXX (OP_CGT_UN,>,guint32)
 207         FOLD_CXX (OP_CLT,<,gint32)
 208         FOLD_CXX (OP_CLT_UN,<,guint32)
 209         case CEE_CONV_I8:
 210                 if (inst->inst_i0->opcode == OP_ICONST) {
 211                         inst->opcode = OP_I8CONST;
 212                         inst->inst_l = inst->inst_i0->inst_c0;
 213                 }
 214                 return;
 215         case CEE_CONV_I:
 216         case CEE_CONV_U:
 217                 if (inst->inst_i0->opcode == OP_ICONST) {
 218                         inst->opcode = OP_ICONST;
 219                         inst->inst_c0 = inst->inst_i0->inst_c0;
 220                 } else if (inst->inst_i0->opcode == CEE_LDIND_I) {
 221                         *inst = *inst->inst_i0;
 222                 }
 223                 return;
 224         /* we should be able to handle isinst and castclass as well */
 225         case CEE_ISINST:
 226         case CEE_CASTCLASS:
 227         /*
 228          * TODO:
 229          *      conv.* opcodes.
 230          *      *ovf* opcodes? I'ts slow and hard to do in C.
 231          *      switch can be replaced by a simple jump
 232          */
 233 #if SIZEOF_VOID_P == 4
 234         case CEE_CONV_I4:
 235                 if ((inst->inst_left->type == STACK_I4) || (inst->inst_left->type == STACK_PTR)) {
 236                         *inst = *inst->inst_left;
 237                 }
 238                 break;
 239 #endif
 240         default:
 241                 return;
 242         }
 243 }
 244
 245 void
 246 mono_constant_fold (MonoCompile *cfg)
 247 {
 248         MonoBasicBlock *bb;
 249
 250         for (bb = cfg->bb_entry; bb; bb = bb->next_bb) {
 251                 MonoInst *ins;
 252                 for (ins = bb->code; ins; ins = ins->next)
 253                         mono_inst_foreach (ins, mono_constant_fold_inst, NULL);
 254         }
 255 }
 256
 257 /*
 258  * If the arguments to the cond branch are constants, eval and
 259  * return BRANCH_NOT_TAKEN for not taken, BRANCH_TAKEN for taken,
 260  * BRANCH_UNDEF otherwise.
 261  * If this code is changed to handle also non-const values, make sure
 262  * side effects are handled in optimize_branches() in mini.c, by
 263  * inserting pop instructions.
 264  */
 265 int
 266 mono_eval_cond_branch (MonoInst *ins)
 267 {
 268         MonoInst *left, *right;
 269         /* FIXME: handle also 64 bit ints */
 270         left = ins->inst_left->inst_left;
 271         if (left->opcode != OP_ICONST && left->opcode != OP_PCONST)
 272                 return BRANCH_UNDEF;
 273         right = ins->inst_left->inst_right;
 274         if (right->opcode != OP_ICONST && right->opcode != OP_PCONST)
 275                 return BRANCH_UNDEF;
 276         switch (ins->opcode) {
 277         case CEE_BEQ:
 278                 if (left->inst_c0 == right->inst_c0)
 279                         return BRANCH_TAKEN;
 280                 return BRANCH_NOT_TAKEN;
 281         case CEE_BGE:
 282                 if (left->inst_c0 >= right->inst_c0)
 283                         return BRANCH_TAKEN;
 284                 return BRANCH_NOT_TAKEN;
 285         case CEE_BGT:
 286                 if (left->inst_c0 > right->inst_c0)
 287                         return BRANCH_TAKEN;
 288                 return BRANCH_NOT_TAKEN;
 289         case CEE_BLE:
 290                 if (left->inst_c0 <= right->inst_c0)
 291                         return BRANCH_TAKEN;
 292                 return BRANCH_NOT_TAKEN;
 293         case CEE_BLT:
 294                 if (left->inst_c0 < right->inst_c0)
 295                         return BRANCH_TAKEN;
 296                 return BRANCH_NOT_TAKEN;
 297         case CEE_BNE_UN:
 298                 if ((gsize)left->inst_c0 != (gsize)right->inst_c0)
 299                         return BRANCH_TAKEN;
 300                 return BRANCH_NOT_TAKEN;
 301         case CEE_BGE_UN:
 302                 if ((gsize)left->inst_c0 >= (gsize)right->inst_c0)
 303                         return BRANCH_TAKEN;
 304                 return BRANCH_NOT_TAKEN;
 305         case CEE_BGT_UN:
 306                 if ((gsize)left->inst_c0 > (gsize)right->inst_c0)
 307                         return BRANCH_TAKEN;
 308                 return BRANCH_NOT_TAKEN;
 309         case CEE_BLE_UN:
 310                 if ((gsize)left->inst_c0 <= (gsize)right->inst_c0)
 311                         return BRANCH_TAKEN;
 312                 return BRANCH_NOT_TAKEN;
 313         case CEE_BLT_UN:
 314                 if ((gsize)left->inst_c0 < (gsize)right->inst_c0)
 315                         return BRANCH_TAKEN;
 316                 return BRANCH_NOT_TAKEN;
 317         }
 318         return BRANCH_UNDEF;
 319 }
 320