Print this page
new smatch

Split Close
Expand all
Collapse all
          --- old/usr/src/tools/smatch/src/simplify.c
          +++ new/usr/src/tools/smatch/src/simplify.c
   1    1  /*
   2    2   * Simplify - do instruction simplification before CSE
   3    3   *
   4    4   * Copyright (C) 2004 Linus Torvalds
   5    5   */
   6    6  
        7 +///
        8 +// Instruction simplification
        9 +// --------------------------
       10 +//
       11 +// Notation
       12 +// ^^^^^^^^
       13 +// The following conventions are used to describe the simplications:
       14 +// * Uppercase letters are reserved for constants:
       15 +//   * `M` for a constant mask,
       16 +//   * `S` for a constant shift,
       17 +//   * `N` for a constant number of bits (usually other than a shift),
       18 +//   * `C` or 'K' for others constants.
       19 +// * Lowercase letters `a`, `b`, `x`, `y`, ... are used for non-constants
       20 +//   or when it doesn't matter if the pseudo is a constant or not.
       21 +// * Primes are used if needed to distinguish symbols (`M`, `M'`, ...).
       22 +// * Expressions or sub-expressions involving only constants are
       23 +//   understood to be evaluated.
       24 +// * `$mask(N)` is used for `((1 << N) -1)`
       25 +// * `$trunc(x, N)` is used for `(x & $mask(N))`
       26 +// * Expressions like `(-1 << S)`, `(-1 >> S)` and others formulae are
       27 +//   understood to be truncated to the size of the current instruction
       28 +//   (needed, since in general this size is not the same as the one used
       29 +//   by sparse for the evaluation of arithmetic operations).
       30 +// * `TRUNC(x, N)` is used for a truncation *to* a size of `N` bits
       31 +// * `ZEXT(x, N)` is used for a zero-extension *from* a size of `N` bits
       32 +// * `OP(x, C)` is used to represent some generic operation using a constant,
       33 +//   including when the constant is implicit (e.g. `TRUNC(x, N)`).
       34 +// * `MASK(x, M)` is used to respresent a 'masking' instruction:
       35 +//   - `AND(x, M)`
       36 +//   - `LSR(x, S)`, with `M` = (-1 << S)
       37 +//   - `SHL(x, S)`, with `M` = (-1 >> S)
       38 +//   - `TRUNC(x, N)`, with `M` = $mask(N)
       39 +//   - `ZEXT(x, N)`, with `M` = $mask(N)
       40 +// * `SHIFT(x, S)` is used for `LSR(x, S)` or `SHL(x, S)`.
       41 +
   7   42  #include <assert.h>
   8   43  
   9   44  #include "parse.h"
  10   45  #include "expression.h"
  11   46  #include "linearize.h"
  12   47  #include "flow.h"
  13   48  #include "symbol.h"
  14   49  
  15      -/* Find the trivial parent for a phi-source */
       50 +///
       51 +// Utilities
       52 +// ^^^^^^^^^
       53 +
       54 +///
       55 +// find the trivial parent for a phi-source
  16   56  static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseudo)
  17   57  {
  18   58          /* Can't go upwards if the pseudo is defined in the bb it came from.. */
  19   59          if (pseudo->type == PSEUDO_REG) {
  20   60                  struct instruction *def = pseudo->def;
  21   61                  if (def->bb == source)
  22   62                          return source;
  23   63          }
  24   64          if (bb_list_size(source->children) != 1 || bb_list_size(source->parents) != 1)
  25   65                  return source;
  26   66          return first_basic_block(source->parents);
  27   67  }
  28   68  
  29      -/*
  30      - * Copy the phi-node's phisrcs into to given array.
  31      - * Returns 0 if the the list contained the expected
  32      - * number of element, a positive number if there was
  33      - * more than expected and a negative one if less.
  34      - *
  35      - * Note: we can't reuse a function like linearize_ptr_list()
  36      - * because any VOIDs in the phi-list must be ignored here
  37      - * as in this context they mean 'entry has been removed'.
  38      - */
       69 +///
       70 +// copy the phi-node's phisrcs into to given array
       71 +// @return: 0 if the the list contained the expected
       72 +//      number of element, a positive number if there was
       73 +//      more than expected and a negative one if less.
       74 +//
       75 +// :note: we can't reuse a function like linearize_ptr_list()
       76 +//      because any VOIDs in the phi-list must be ignored here
       77 +//      as in this context they mean 'entry has been removed'.
  39   78  static int get_phisources(struct instruction *sources[], int nbr, struct instruction *insn)
  40   79  {
  41   80          pseudo_t phi;
  42   81          int i = 0;
  43   82  
  44   83          assert(insn->opcode == OP_PHI);
  45   84          FOR_EACH_PTR(insn->phi_list, phi) {
  46   85                  struct instruction *def;
  47   86                  if (phi == VOID)
  48   87                          continue;
↓ open down ↓ 12 lines elided ↑ open up ↑
  61  100          struct basic_block *parents[3];
  62  101          struct basic_block *bb, *bb1, *bb2, *source;
  63  102          struct instruction *br;
  64  103          pseudo_t p1, p2;
  65  104  
  66  105          bb = insn->bb;
  67  106          if (get_phisources(array, 2, insn))
  68  107                  return 0;
  69  108          if (linearize_ptr_list((struct ptr_list *)bb->parents, (void **)parents, 3) != 2)
  70  109                  return 0;
  71      -        p1 = array[0]->src1;
      110 +        p1 = array[0]->phi_src;
  72  111          bb1 = array[0]->bb;
  73      -        p2 = array[1]->src1;
      112 +        p2 = array[1]->phi_src;
  74  113          bb2 = array[1]->bb;
  75  114  
  76  115          /* Only try the simple "direct parents" case */
  77  116          if ((bb1 != parents[0] || bb2 != parents[1]) &&
  78  117              (bb1 != parents[1] || bb2 != parents[0]))
  79  118                  return 0;
  80  119  
  81  120          /*
  82  121           * See if we can find a common source for this..
  83  122           */
↓ open down ↓ 42 lines elided ↑ open up ↑
 126  165           * turns out that 'a' or 'b' is entirely
 127  166           * empty (common case), and now no longer
 128  167           * a phi-source, we'll be able to simplify
 129  168           * the conditional branch too.
 130  169           */
 131  170          insert_select(source, br, insn, p1, p2);
 132  171          kill_instruction(insn);
 133  172          return REPEAT_CSE;
 134  173  }
 135  174  
 136      -static int clean_up_phi(struct instruction *insn)
      175 +///
      176 +// detect trivial phi-nodes
      177 +// @insn: the phi-node
      178 +// @pseudo: the candidate resulting pseudo (NULL when starting)
      179 +// @return: the unique result if the phi-node is trivial, NULL otherwise
      180 +//
      181 +// A phi-node is trivial if it has a single possible result:
      182 +//      * all operands are the same
      183 +//      * the operands are themselves defined by a chain or cycle of phi-nodes
      184 +//              and the set of all operands involved contains a single value
      185 +//              not defined by these phi-nodes
      186 +//
      187 +// Since the result is unique, these phi-nodes can be removed.
      188 +static pseudo_t trivial_phi(pseudo_t pseudo, struct instruction *insn, struct pseudo_list **list)
 137  189  {
      190 +        pseudo_t target = insn->target;
 138  191          pseudo_t phi;
 139      -        struct instruction *last;
 140      -        int same;
 141  192  
 142      -        last = NULL;
 143      -        same = 1;
      193 +        add_pseudo(list, target);
      194 +
 144  195          FOR_EACH_PTR(insn->phi_list, phi) {
 145  196                  struct instruction *def;
      197 +                pseudo_t src;
      198 +
 146  199                  if (phi == VOID)
 147  200                          continue;
 148  201                  def = phi->def;
 149      -                if (def->src1 == VOID || !def->bb)
      202 +                if (!def->bb)
 150  203                          continue;
 151      -                if (last) {
 152      -                        if (last->src1 != def->src1)
 153      -                                same = 0;
      204 +                src = def->phi_src; // bypass OP_PHISRC & get the real source
      205 +                if (src == VOID)
 154  206                          continue;
      207 +                if (!pseudo) {
      208 +                        pseudo = src;
      209 +                        continue;
 155  210                  }
 156      -                last = def;
      211 +                if (src == pseudo)
      212 +                        continue;
      213 +                if (src == target)
      214 +                        continue;
      215 +                if (DEF_OPCODE(def, src) == OP_PHI) {
      216 +                        if (pseudo_in_list(*list, src))
      217 +                                continue;
      218 +                        if ((pseudo = trivial_phi(pseudo, def, list)))
      219 +                                continue;
      220 +                }
      221 +                return NULL;
 157  222          } END_FOR_EACH_PTR(phi);
 158  223  
 159      -        if (same) {
 160      -                pseudo_t pseudo = last ? last->src1 : VOID;
      224 +        return pseudo ? pseudo : VOID;
      225 +}
      226 +
      227 +static int clean_up_phi(struct instruction *insn)
      228 +{
      229 +        struct pseudo_list *list = NULL;
      230 +        pseudo_t pseudo;
      231 +
      232 +        if ((pseudo = trivial_phi(NULL, insn, &list))) {
 161  233                  convert_instruction_target(insn, pseudo);
 162  234                  kill_instruction(insn);
 163  235                  return REPEAT_CSE;
 164  236          }
 165  237  
 166  238          return if_convert_phi(insn);
 167  239  }
 168  240  
 169  241  static int delete_pseudo_user_list_entry(struct pseudo_user_list **list, pseudo_t *entry, int count)
 170  242  {
↓ open down ↓ 1 lines elided ↑ open up ↑
 172  244  
 173  245          FOR_EACH_PTR(*list, pu) {
 174  246                  if (pu->userp == entry) {
 175  247                          MARK_CURRENT_DELETED(pu);
 176  248                          if (!--count)
 177  249                                  goto out;
 178  250                  }
 179  251          } END_FOR_EACH_PTR(pu);
 180  252          assert(count <= 0);
 181  253  out:
 182      -        if (ptr_list_size((struct ptr_list *) *list) == 0)
      254 +        if (pseudo_user_list_empty(*list))
 183  255                  *list = NULL;
 184  256          return count;
 185  257  }
 186  258  
 187      -static inline void remove_usage(pseudo_t p, pseudo_t *usep)
      259 +static inline void rem_usage(pseudo_t p, pseudo_t *usep, int kill)
 188  260  {
 189  261          if (has_use_list(p)) {
      262 +                if (p->type == PSEUDO_SYM)
      263 +                        repeat_phase |= REPEAT_SYMBOL_CLEANUP;
 190  264                  delete_pseudo_user_list_entry(&p->users, usep, 1);
 191      -                if (!p->users)
      265 +                if (kill && !p->users)
 192  266                          kill_instruction(p->def);
 193  267          }
 194  268  }
 195  269  
      270 +static inline void remove_usage(pseudo_t p, pseudo_t *usep)
      271 +{
      272 +        rem_usage(p, usep, 1);
      273 +}
      274 +
 196  275  void kill_use(pseudo_t *usep)
 197  276  {
 198  277          if (usep) {
 199  278                  pseudo_t p = *usep;
 200  279                  *usep = VOID;
 201      -                remove_usage(p, usep);
      280 +                rem_usage(p, usep, 1);
 202  281          }
 203  282  }
 204  283  
      284 +// Like kill_use() but do not (recursively) kill dead instructions
      285 +void remove_use(pseudo_t *usep)
      286 +{
      287 +        pseudo_t p = *usep;
      288 +        *usep = VOID;
      289 +        rem_usage(p, usep, 0);
      290 +}
      291 +
 205  292  static void kill_use_list(struct pseudo_list *list)
 206  293  {
 207  294          pseudo_t p;
 208  295          FOR_EACH_PTR(list, p) {
 209  296                  if (p == VOID)
 210  297                          continue;
 211  298                  kill_use(THIS_ADDRESS(p));
 212  299          } END_FOR_EACH_PTR(p);
 213  300  }
 214  301  
 215      -/*
 216      - * kill an instruction:
 217      - * - remove it from its bb
 218      - * - remove the usage of all its operands
 219      - * If forse is zero, the normal case, the function only for
 220      - * instructions free of (possible) side-effects. Otherwise
 221      - * the function does that unconditionally (must only be used
 222      - * for unreachable instructions.
 223      - */
 224      -void kill_insn(struct instruction *insn, int force)
      302 +///
      303 +// kill an instruction
      304 +// @insn: the instruction to be killed
      305 +// @force: if unset, the normal case, the instruction is not killed
      306 +//      if not free of possible side-effect; if set the instruction
      307 +//      is unconditionally killed.
      308 +//
      309 +// The killed instruction is removed from its BB and the usage
      310 +// of all its operands are removed. The instruction is also
      311 +// marked as killed by setting its ->bb to NULL.
      312 +int kill_insn(struct instruction *insn, int force)
 225  313  {
 226  314          if (!insn || !insn->bb)
 227      -                return;
      315 +                return 0;
 228  316  
 229  317          switch (insn->opcode) {
 230  318          case OP_SEL:
 231  319          case OP_RANGE:
 232  320                  kill_use(&insn->src3);
 233  321                  /* fall through */
 234  322  
 235  323          case OP_BINARY ... OP_BINCMP_END:
 236  324                  kill_use(&insn->src2);
 237  325                  /* fall through */
 238  326  
 239      -        case OP_CAST:
 240      -        case OP_SCAST:
 241      -        case OP_FPCAST:
 242      -        case OP_PTRCAST:
      327 +        case OP_UNOP ... OP_UNOP_END:
 243  328          case OP_SETVAL:
 244      -        case OP_NOT: case OP_NEG:
 245  329          case OP_SLICE:
 246  330                  kill_use(&insn->src1);
 247  331                  break;
 248  332  
 249  333          case OP_PHI:
 250  334                  kill_use_list(insn->phi_list);
 251  335                  break;
 252  336          case OP_PHISOURCE:
 253  337                  kill_use(&insn->phi_src);
 254  338                  break;
 255  339  
 256  340          case OP_SYMADDR:
      341 +                kill_use(&insn->src);
 257  342                  repeat_phase |= REPEAT_SYMBOL_CLEANUP;
 258  343                  break;
 259  344  
 260  345          case OP_CBR:
      346 +        case OP_SWITCH:
 261  347          case OP_COMPUTEDGOTO:
 262  348                  kill_use(&insn->cond);
 263  349                  break;
 264  350  
 265  351          case OP_CALL:
 266  352                  if (!force) {
 267  353                          /* a "pure" function can be killed too */
 268  354                          if (!(insn->func->type == PSEUDO_SYM))
 269      -                                return;
      355 +                                return 0;
 270  356                          if (!(insn->func->sym->ctype.modifiers & MOD_PURE))
 271      -                                return;
      357 +                                return 0;
 272  358                  }
 273  359                  kill_use_list(insn->arguments);
 274  360                  if (insn->func->type == PSEUDO_REG)
 275  361                          kill_use(&insn->func);
 276  362                  break;
 277  363  
 278  364          case OP_LOAD:
 279      -                if (!force && insn->type->ctype.modifiers & MOD_VOLATILE)
 280      -                        return;
      365 +                if (!force && insn->is_volatile)
      366 +                        return 0;
 281  367                  kill_use(&insn->src);
 282  368                  break;
 283  369  
 284  370          case OP_STORE:
 285  371                  if (!force)
 286      -                        return;
      372 +                        return 0;
 287  373                  kill_use(&insn->src);
 288  374                  kill_use(&insn->target);
 289  375                  break;
 290  376  
 291  377          case OP_ENTRY:
 292  378                  /* ignore */
 293      -                return;
      379 +                return 0;
 294  380  
 295  381          case OP_BR:
      382 +        case OP_SETFVAL:
 296  383          default:
 297  384                  break;
 298  385          }
 299  386  
 300  387          insn->bb = NULL;
 301      -        repeat_phase |= REPEAT_CSE;
 302      -        return;
      388 +        return repeat_phase |= REPEAT_CSE;
 303  389  }
 304  390  
 305      -/*
 306      - * Kill trivially dead instructions
 307      - */
      391 +///
      392 +// kill trivially dead instructions
 308  393  static int dead_insn(struct instruction *insn, pseudo_t *src1, pseudo_t *src2, pseudo_t *src3)
 309  394  {
 310      -        struct pseudo_user *pu;
 311      -        FOR_EACH_PTR(insn->target->users, pu) {
 312      -                if (*pu->userp != VOID)
 313      -                        return 0;
 314      -        } END_FOR_EACH_PTR(pu);
      395 +        if (has_users(insn->target))
      396 +                return 0;
 315  397  
 316  398          insn->bb = NULL;
 317  399          kill_use(src1);
 318  400          kill_use(src2);
 319  401          kill_use(src3);
 320  402          return REPEAT_CSE;
 321  403  }
 322  404  
      405 +static inline bool has_target(struct instruction *insn)
      406 +{
      407 +        return opcode_table[insn->opcode].flags & OPF_TARGET;
      408 +}
      409 +
      410 +void remove_dead_insns(struct entrypoint *ep)
      411 +{
      412 +        struct basic_block *bb;
      413 +
      414 +        FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
      415 +                struct instruction *insn;
      416 +                FOR_EACH_PTR_REVERSE(bb->insns, insn) {
      417 +                        if (!insn->bb)
      418 +                                continue;
      419 +                        if (!has_target(insn))
      420 +                                continue;
      421 +                        if (!has_users(insn->target))
      422 +                                kill_instruction(insn);
      423 +                } END_FOR_EACH_PTR_REVERSE(insn);
      424 +        } END_FOR_EACH_PTR_REVERSE(bb);
      425 +}
      426 +
 323  427  static inline int constant(pseudo_t pseudo)
 324  428  {
 325  429          return pseudo->type == PSEUDO_VAL;
 326  430  }
 327  431  
      432 +///
      433 +// replace the operand of an instruction
      434 +// @insn: the instruction
      435 +// @pp: the address of the instruction's operand
      436 +// @new: the new value for the operand
      437 +// @return: REPEAT_CSE.
      438 +static inline int replace_pseudo(struct instruction *insn, pseudo_t *pp, pseudo_t new)
      439 +{
      440 +        pseudo_t old = *pp;
      441 +        use_pseudo(insn, new, pp);
      442 +        remove_usage(old, pp);
      443 +        return REPEAT_CSE;
      444 +}
      445 +
 328  446  static int replace_with_pseudo(struct instruction *insn, pseudo_t pseudo)
 329  447  {
 330  448          convert_instruction_target(insn, pseudo);
 331  449  
 332  450          switch (insn->opcode) {
 333  451          case OP_SEL:
 334  452          case OP_RANGE:
 335  453                  kill_use(&insn->src3);
 336  454          case OP_BINARY ... OP_BINCMP_END:
 337  455                  kill_use(&insn->src2);
 338      -        case OP_NOT:
 339      -        case OP_NEG:
      456 +        case OP_UNOP ... OP_UNOP_END:
 340  457          case OP_SYMADDR:
 341      -        case OP_CAST:
 342      -        case OP_SCAST:
 343      -        case OP_FPCAST:
 344      -        case OP_PTRCAST:
 345  458                  kill_use(&insn->src1);
 346  459                  break;
 347  460  
 348  461          default:
 349  462                  assert(0);
 350  463          }
 351  464          insn->bb = NULL;
 352  465          return REPEAT_CSE;
 353  466  }
 354  467  
 355      -unsigned int value_size(long long value)
      468 +static inline int def_opcode(pseudo_t p)
 356  469  {
      470 +        if (p->type != PSEUDO_REG)
      471 +                return OP_BADOP;
      472 +        return p->def->opcode;
      473 +}
      474 +
      475 +static unsigned int value_size(long long value)
      476 +{
 357  477          value >>= 8;
 358  478          if (!value)
 359  479                  return 8;
 360  480          value >>= 8;
 361  481          if (!value)
 362  482                  return 16;
 363  483          value >>= 16;
 364  484          if (!value)
 365  485                  return 32;
 366  486          return 64;
 367  487  }
 368  488  
 369      -/*
 370      - * Try to determine the maximum size of bits in a pseudo.
 371      - *
 372      - * Right now this only follow casts and constant values, but we
 373      - * could look at things like logical 'and' instructions etc.
 374      - */
      489 +///
      490 +// try to determine the maximum size of bits in a pseudo
      491 +//
      492 +// Right now this only follow casts and constant values, but we
      493 +// could look at things like AND instructions, etc.
 375  494  static unsigned int operand_size(struct instruction *insn, pseudo_t pseudo)
 376  495  {
 377  496          unsigned int size = insn->size;
 378  497  
 379  498          if (pseudo->type == PSEUDO_REG) {
 380  499                  struct instruction *src = pseudo->def;
 381      -                if (src && src->opcode == OP_CAST && src->orig_type) {
      500 +                if (src && src->opcode == OP_ZEXT && src->orig_type) {
 382  501                          unsigned int orig_size = src->orig_type->bit_size;
 383  502                          if (orig_size < size)
 384  503                                  size = orig_size;
 385  504                  }
 386  505          }
 387  506          if (pseudo->type == PSEUDO_VAL) {
 388  507                  unsigned int orig_size = value_size(pseudo->value);
 389  508                  if (orig_size < size)
 390  509                          size = orig_size;
 391  510          }
 392  511          return size;
 393  512  }
 394  513  
 395      -static int simplify_asr(struct instruction *insn, pseudo_t pseudo, long long value)
      514 +static pseudo_t eval_insn(struct instruction *insn)
 396  515  {
 397      -        unsigned int size = operand_size(insn, pseudo);
      516 +        /* FIXME! Verify signs and sizes!! */
      517 +        unsigned int size = insn->size;
      518 +        long long left = insn->src1->value;
      519 +        long long right = insn->src2->value;
      520 +        unsigned long long ul, ur;
      521 +        long long res, mask, bits;
 398  522  
 399      -        if (value >= size) {
 400      -                warning(insn->pos, "right shift by bigger than source value");
 401      -                return replace_with_pseudo(insn, value_pseudo(insn->type, 0));
      523 +        mask = 1ULL << (size-1);
      524 +        bits = mask | (mask-1);
      525 +
      526 +        if (left & mask)
      527 +                left |= ~bits;
      528 +        if (right & mask)
      529 +                right |= ~bits;
      530 +        ul = left & bits;
      531 +        ur = right & bits;
      532 +
      533 +        switch (insn->opcode) {
      534 +        case OP_ADD:
      535 +                res = left + right;
      536 +                break;
      537 +        case OP_SUB:
      538 +                res = left - right;
      539 +                break;
      540 +        case OP_MUL:
      541 +                res = ul * ur;
      542 +                break;
      543 +        case OP_DIVU:
      544 +                if (!ur)
      545 +                        goto undef;
      546 +                res = ul / ur;
      547 +                break;
      548 +        case OP_DIVS:
      549 +                if (!right)
      550 +                        goto undef;
      551 +                if (left == mask && right == -1)
      552 +                        goto undef;
      553 +                res = left / right;
      554 +                break;
      555 +        case OP_MODU:
      556 +                if (!ur)
      557 +                        goto undef;
      558 +                res = ul % ur;
      559 +                break;
      560 +        case OP_MODS:
      561 +                if (!right)
      562 +                        goto undef;
      563 +                if (left == mask && right == -1)
      564 +                        goto undef;
      565 +                res = left % right;
      566 +                break;
      567 +        case OP_SHL:
      568 +                if (ur >= size)
      569 +                        goto undef;
      570 +                res = left << right;
      571 +                break;
      572 +        case OP_LSR:
      573 +                if (ur >= size)
      574 +                        goto undef;
      575 +                res = ul >> ur;
      576 +                break;
      577 +        case OP_ASR:
      578 +                if (ur >= size)
      579 +                        goto undef;
      580 +                res = left >> right;
      581 +                break;
      582 +       /* Logical */
      583 +        case OP_AND:
      584 +                res = left & right;
      585 +                break;
      586 +        case OP_OR:
      587 +                res = left | right;
      588 +                break;
      589 +        case OP_XOR:
      590 +                res = left ^ right;
      591 +                break;
      592 +
      593 +        /* Binary comparison */
      594 +        case OP_SET_EQ:
      595 +                res = left == right;
      596 +                break;
      597 +        case OP_SET_NE:
      598 +                res = left != right;
      599 +                break;
      600 +        case OP_SET_LE:
      601 +                res = left <= right;
      602 +                break;
      603 +        case OP_SET_GE:
      604 +                res = left >= right;
      605 +                break;
      606 +        case OP_SET_LT:
      607 +                res = left < right;
      608 +                break;
      609 +        case OP_SET_GT:
      610 +                res = left > right;
      611 +                break;
      612 +        case OP_SET_B:
      613 +                res = ul < ur;
      614 +                break;
      615 +        case OP_SET_A:
      616 +                res = ul > ur;
      617 +                break;
      618 +        case OP_SET_BE:
      619 +                res = ul <= ur;
      620 +                break;
      621 +        case OP_SET_AE:
      622 +                res = ul >= ur;
      623 +                break;
      624 +        default:
      625 +                return NULL;
 402  626          }
      627 +        res &= bits;
      628 +
      629 +        return value_pseudo(res);
      630 +
      631 +undef:
      632 +        return NULL;
      633 +}
      634 +
      635 +///
      636 +// Simplifications
      637 +// ^^^^^^^^^^^^^^^
      638 +
      639 +///
      640 +// try to simplify MASK(OR(AND(x, M'), b), M)
      641 +// @insn: the masking instruction
      642 +// @mask: the associated mask (M)
      643 +// @ora: one of the OR's operands, guaranteed to be PSEUDO_REG
      644 +// @orb: the other OR's operand
      645 +// @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
      646 +static int simplify_mask_or_and(struct instruction *insn, unsigned long long mask,
      647 +        pseudo_t ora, pseudo_t orb)
      648 +{
      649 +        unsigned long long omask, nmask;
      650 +        struct instruction *and = ora->def;
      651 +        pseudo_t src2 = and->src2;
      652 +
      653 +        if (and->opcode != OP_AND)
      654 +                return 0;
      655 +        if (!constant(src2))
      656 +                return 0;
      657 +        omask = src2->value;
      658 +        nmask = omask & mask;
      659 +        if (nmask == 0) {
      660 +                // if (M' & M) == 0: ((a & M') | b) -> b
      661 +                return replace_pseudo(insn, &insn->src1, orb);
      662 +        }
      663 +        if (multi_users(insn->src1))
      664 +                return 0;       // can't modify anything inside the OR
      665 +        if (nmask == mask) {
      666 +                struct instruction *or = insn->src1->def;
      667 +                pseudo_t *arg = (ora == or->src1) ? &or->src1 : &or->src2;
      668 +                // if (M' & M) == M: ((a & M') | b) -> (a | b)
      669 +                return replace_pseudo(or, arg, and->src1);
      670 +        }
      671 +        if (nmask != omask && !multi_users(ora)) {
      672 +                // if (M' & M) != M': AND(a, M') -> AND(a, (M' & M))
      673 +                and->src2 = value_pseudo(nmask);
      674 +                return REPEAT_CSE;
      675 +        }
      676 +        return 0;
      677 +}
      678 +
      679 +///
      680 +// try to simplify MASK(OR(a, b), M)
      681 +// @insn: the masking instruction
      682 +// @mask: the associated mask (M)
      683 +// @or: the OR instruction
      684 +// @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
      685 +static int simplify_mask_or(struct instruction *insn, unsigned long long mask, struct instruction *or)
      686 +{
      687 +        pseudo_t src1 = or->src1;
      688 +        pseudo_t src2 = or->src2;
      689 +        int rc;
      690 +
      691 +        if (src1->type == PSEUDO_REG) {
      692 +                if ((rc = simplify_mask_or_and(insn, mask, src1, src2)))
      693 +                        return rc;
      694 +        }
      695 +        if (src2->type == PSEUDO_REG) {
      696 +                if ((rc = simplify_mask_or_and(insn, mask, src2, src1)))
      697 +                        return rc;
      698 +        } else if (src2->type == PSEUDO_VAL) {
      699 +                unsigned long long oval = src2->value;
      700 +                unsigned long long nval = oval & mask;
      701 +                // Try to simplify:
      702 +                //      MASK(OR(x, C), M)
      703 +                if (nval == 0) {
      704 +                        // if (C & M) == 0: OR(x, C) -> x
      705 +                        return replace_pseudo(insn, &insn->src1, src1);
      706 +                }
      707 +                if (nval == mask) {
      708 +                        // if (C & M) == M: OR(x, C) -> M
      709 +                        return replace_pseudo(insn, &insn->src1, value_pseudo(mask));
      710 +                }
      711 +                if (nval != oval && !multi_users(or->target)) {
      712 +                        // if (C & M) != C: OR(x, C) -> OR(x, (C & M))
      713 +                        return replace_pseudo(or, &or->src2, value_pseudo(nval));
      714 +                }
      715 +        }
      716 +        return 0;
      717 +}
      718 +
      719 +///
      720 +// try to simplify MASK(SHIFT(OR(a, b), S), M)
      721 +// @sh: the shift instruction
      722 +// @or: the OR instruction
      723 +// @mask: the mask associated to MASK (M):
      724 +// @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
      725 +static int simplify_mask_shift_or(struct instruction *sh, struct instruction *or, unsigned long long mask)
      726 +{
      727 +        unsigned long long smask = bits_mask(sh->size);
      728 +        int shift = sh->src2->value;
      729 +
      730 +        if (sh->opcode == OP_LSR)
      731 +                mask <<= shift;
      732 +        else
      733 +                mask >>= shift;
      734 +        return simplify_mask_or(sh, smask & mask, or);
      735 +}
      736 +
      737 +static int simplify_mask_shift(struct instruction *sh, unsigned long long mask)
      738 +{
      739 +        struct instruction *inner;
      740 +
      741 +        if (!constant(sh->src2) || sh->tainted)
      742 +                return 0;
      743 +        switch (DEF_OPCODE(inner, sh->src1)) {
      744 +        case OP_OR:
      745 +                if (!multi_users(sh->target))
      746 +                        return simplify_mask_shift_or(sh, inner, mask);
      747 +                break;
      748 +        }
      749 +        return 0;
      750 +}
      751 +
      752 +static long long check_shift_count(struct instruction *insn, unsigned long long uval)
      753 +{
      754 +        unsigned int size = insn->size;
      755 +        long long sval = uval;
      756 +
      757 +        if (uval < size)
      758 +                return uval;
      759 +
      760 +        sval = sign_extend_safe(sval, size);
      761 +        sval = sign_extend_safe(sval, bits_in_int);
      762 +        if (sval < 0)
      763 +                insn->src2 = value_pseudo(sval);
      764 +        if (insn->tainted)
      765 +                return sval;
      766 +
      767 +        if (sval < 0 && Wshift_count_negative)
      768 +                warning(insn->pos, "shift count is negative (%lld)", sval);
      769 +        if (sval > 0 && Wshift_count_overflow) {
      770 +                struct symbol *ctype = insn->type;
      771 +                const char *tname;
      772 +                if (ctype->type == SYM_NODE)
      773 +                        ctype = ctype->ctype.base_type;
      774 +                tname = show_typename(ctype);
      775 +                warning(insn->pos, "shift too big (%llu) for type %s", sval, tname);
      776 +        }
      777 +        insn->tainted = 1;
      778 +        return sval;
      779 +}
      780 +
      781 +static int simplify_shift(struct instruction *insn, pseudo_t pseudo, long long value)
      782 +{
      783 +        struct instruction *def;
      784 +        unsigned long long mask, omask, nmask;
      785 +        unsigned long long nval;
      786 +        unsigned int size;
      787 +        pseudo_t src2;
      788 +
 403  789          if (!value)
 404  790                  return replace_with_pseudo(insn, pseudo);
      791 +        value = check_shift_count(insn, value);
      792 +        if (value < 0)
      793 +                return 0;
      794 +
      795 +        size = insn->size;
      796 +        switch (insn->opcode) {
      797 +        case OP_ASR:
      798 +                if (value >= size)
      799 +                        return 0;
      800 +                if (pseudo->type != PSEUDO_REG)
      801 +                        break;
      802 +                def = pseudo->def;
      803 +                switch (def->opcode) {
      804 +                case OP_LSR:
      805 +                case OP_ASR:
      806 +                        if (def == insn)        // cyclic DAG!
      807 +                                break;
      808 +                        src2 = def->src2;
      809 +                        if (src2->type != PSEUDO_VAL)
      810 +                                break;
      811 +                        nval = src2->value;
      812 +                        if (nval > insn->size || nval == 0)
      813 +                                break;
      814 +                        value += nval;
      815 +                        if (def->opcode == OP_LSR)
      816 +                                insn->opcode = OP_LSR;
      817 +                        else if (value >= size)
      818 +                                value = size - 1;
      819 +                        goto new_value;
      820 +
      821 +                case OP_ZEXT:
      822 +                        // transform:
      823 +                        //      zext.N  %t <- (O) %a
      824 +                        //      asr.N   %r <- %t, C
      825 +                        // into
      826 +                        //      zext.N  %t <- (O) %a
      827 +                        //      lsr.N   %r <- %t, C
      828 +                        insn->opcode = OP_LSR;
      829 +                        return REPEAT_CSE;
      830 +                }
      831 +                break;
      832 +        case OP_LSR:
      833 +                size = operand_size(insn, pseudo);
      834 +                if (value >= size)
      835 +                        goto zero;
      836 +                switch(DEF_OPCODE(def, pseudo)) {
      837 +                case OP_AND:
      838 +                        // replace (A & M) >> S
      839 +                        // by      (A >> S) & (M >> S)
      840 +                        if (!constant(def->src2))
      841 +                                break;
      842 +                        mask = bits_mask(insn->size - value) << value;
      843 +                        omask = def->src2->value;
      844 +                        nmask = omask & mask;
      845 +                        if (nmask == 0)
      846 +                                return replace_with_pseudo(insn, value_pseudo(0));
      847 +                        if (nmask == mask)
      848 +                                return replace_pseudo(insn, &insn->src1, def->src1);
      849 +                        if (nbr_users(pseudo) > 1)
      850 +                                break;
      851 +                        def->opcode = OP_LSR;
      852 +                        def->src2 = insn->src2;
      853 +                        insn->opcode = OP_AND;
      854 +                        insn->src2 = value_pseudo(omask >> value);
      855 +                        return REPEAT_CSE;
      856 +                case OP_LSR:
      857 +                        goto case_shift_shift;
      858 +                case OP_OR:
      859 +                        mask = bits_mask(size);
      860 +                        return simplify_mask_shift_or(insn, def, mask);
      861 +                case OP_SHL:
      862 +                        // replace ((x << S) >> S)
      863 +                        // by      (x & (-1 >> S))
      864 +                        if (def->src2 != insn->src2)
      865 +                                break;
      866 +                        mask = bits_mask(insn->size - value);
      867 +                        goto replace_mask;
      868 +                }
      869 +                break;
      870 +        case OP_SHL:
      871 +                if (value >= size)
      872 +                        goto zero;
      873 +                switch(DEF_OPCODE(def, pseudo)) {
      874 +                case OP_AND:
      875 +                        // simplify (A & M) << S
      876 +                        if (!constant(def->src2))
      877 +                                break;
      878 +                        mask = bits_mask(insn->size) >> value;
      879 +                        omask = def->src2->value;
      880 +                        nmask = omask & mask;
      881 +                        if (nmask == 0)
      882 +                                return replace_with_pseudo(insn, value_pseudo(0));
      883 +                        if (nmask == mask)
      884 +                                return replace_pseudo(insn, &insn->src1, def->src1);
      885 +                        // do not simplify into ((A << S) & (M << S))
      886 +                        break;
      887 +                case OP_LSR:
      888 +                        // replace ((x >> S) << S)
      889 +                        // by      (x & (-1 << S))
      890 +                        if (def->src2 != insn->src2)
      891 +                                break;
      892 +                        mask = bits_mask(insn->size - value) << value;
      893 +                        goto replace_mask;
      894 +                case OP_OR:
      895 +                        mask = bits_mask(size);
      896 +                        return simplify_mask_shift_or(insn, def, mask);
      897 +                case OP_SHL:
      898 +                case_shift_shift:               // also for LSR - LSR
      899 +                        if (def == insn)        // cyclic DAG!
      900 +                                break;
      901 +                        src2 = def->src2;
      902 +                        if (src2->type != PSEUDO_VAL)
      903 +                                break;
      904 +                        nval = src2->value;
      905 +                        if (nval > insn->size)
      906 +                                break;
      907 +                        value += nval;
      908 +                        goto new_value;
      909 +                }
      910 +                break;
      911 +        }
 405  912          return 0;
      913 +
      914 +new_value:
      915 +        if (value < size) {
      916 +                insn->src2 = value_pseudo(value);
      917 +                return replace_pseudo(insn, &insn->src1, pseudo->def->src1);
      918 +        }
      919 +zero:
      920 +        return replace_with_pseudo(insn, value_pseudo(0));
      921 +replace_mask:
      922 +        insn->opcode = OP_AND;
      923 +        insn->src2 = value_pseudo(mask);
      924 +        return replace_pseudo(insn, &insn->src1, def->src1);
 406  925  }
 407  926  
 408  927  static int simplify_mul_div(struct instruction *insn, long long value)
 409  928  {
 410  929          unsigned long long sbit = 1ULL << (insn->size - 1);
 411  930          unsigned long long bits = sbit | (sbit - 1);
 412  931  
 413  932          if (value == 1)
 414  933                  return replace_with_pseudo(insn, insn->src1);
 415  934  
 416  935          switch (insn->opcode) {
 417      -        case OP_MULS:
 418      -        case OP_MULU:
      936 +        case OP_MUL:
 419  937                  if (value == 0)
 420  938                          return replace_with_pseudo(insn, insn->src2);
 421  939          /* Fall through */
 422  940          case OP_DIVS:
 423  941                  if (!(value & sbit))    // positive
 424  942                          break;
 425  943  
 426  944                  value |= ~bits;
 427  945                  if (value == -1) {
 428  946                          insn->opcode = OP_NEG;
 429  947                          return REPEAT_CSE;
 430  948                  }
 431  949          }
 432  950  
 433  951          return 0;
 434  952  }
 435  953  
 436      -static int compare_opcode(int opcode, int inverse)
 437      -{
 438      -        if (!inverse)
 439      -                return opcode;
 440      -
 441      -        switch (opcode) {
 442      -        case OP_SET_EQ: return OP_SET_NE;
 443      -        case OP_SET_NE: return OP_SET_EQ;
 444      -
 445      -        case OP_SET_LT: return OP_SET_GE;
 446      -        case OP_SET_LE: return OP_SET_GT;
 447      -        case OP_SET_GT: return OP_SET_LE;
 448      -        case OP_SET_GE: return OP_SET_LT;
 449      -
 450      -        case OP_SET_A:  return OP_SET_BE;
 451      -        case OP_SET_AE: return OP_SET_B;
 452      -        case OP_SET_B:  return OP_SET_AE;
 453      -        case OP_SET_BE: return OP_SET_A;
 454      -
 455      -        default:
 456      -                return opcode;
 457      -        }
 458      -}
 459      -
 460  954  static int simplify_seteq_setne(struct instruction *insn, long long value)
 461  955  {
 462  956          pseudo_t old = insn->src1;
 463      -        struct instruction *def = old->def;
 464      -        pseudo_t src1, src2;
      957 +        struct instruction *def;
      958 +        unsigned osize;
 465  959          int inverse;
 466  960          int opcode;
 467  961  
 468  962          if (value != 0 && value != 1)
 469  963                  return 0;
 470  964  
      965 +        if (old->type != PSEUDO_REG)
      966 +                return 0;
      967 +        def = old->def;
 471  968          if (!def)
 472  969                  return 0;
 473  970  
 474  971          inverse = (insn->opcode == OP_SET_NE) == value;
      972 +        if (!inverse && def->size == 1 && insn->size == 1) {
      973 +                // Replace:
      974 +                //      setne   %r <- %s, $0
      975 +                // or:
      976 +                //      seteq   %r <- %s, $1
      977 +                // by %s when boolean
      978 +                return replace_with_pseudo(insn, old);
      979 +        }
 475  980          opcode = def->opcode;
 476  981          switch (opcode) {
 477      -        case OP_BINCMP ... OP_BINCMP_END:
      982 +        case OP_AND:
      983 +                if (inverse)
      984 +                        break;
      985 +                if (def->size != insn->size)
      986 +                        break;
      987 +                if (def->src2->type != PSEUDO_VAL)
      988 +                        break;
      989 +                if (def->src2->value != 1)
      990 +                        break;
      991 +                return replace_with_pseudo(insn, old);
      992 +        case OP_FPCMP ... OP_BINCMP_END:
 478  993                  // Convert:
 479  994                  //      setcc.n %t <- %a, %b
 480  995                  //      setne.m %r <- %t, $0
 481  996                  // into:
 482  997                  //      setcc.n %t <- %a, %b
 483  998                  //      setcc.m %r <- %a, $b
 484  999                  // and similar for setne/eq ... 0/1
 485      -                src1 = def->src1;
 486      -                src2 = def->src2;
 487      -                insn->opcode = compare_opcode(opcode, inverse);
 488      -                use_pseudo(insn, src1, &insn->src1);
 489      -                use_pseudo(insn, src2, &insn->src2);
     1000 +                insn->opcode = inverse ? opcode_table[opcode].negate : opcode;
     1001 +                use_pseudo(insn, def->src1, &insn->src1);
     1002 +                use_pseudo(insn, def->src2, &insn->src2);
 490 1003                  remove_usage(old, &insn->src1);
 491 1004                  return REPEAT_CSE;
 492 1005  
 493      -        default:
 494      -                return 0;
     1006 +        case OP_SEXT:
     1007 +                if (value && (def->orig_type->bit_size == 1))
     1008 +                        break;
     1009 +                /* Fall through */
     1010 +        case OP_ZEXT:
     1011 +                // Convert:
     1012 +                //      *ext.m  %s <- (1) %a
     1013 +                //      setne.1 %r <- %s, $0
     1014 +                // into:
     1015 +                //      setne.1 %s <- %a, $0
     1016 +                // and same for setne/eq ... 0/1
     1017 +                return replace_pseudo(insn, &insn->src1, def->src);
     1018 +        case OP_TRUNC:
     1019 +                if (multi_users(old))
     1020 +                        break;
     1021 +                // convert
     1022 +                //      trunc.n %s <- (o) %a
     1023 +                //      setne.m %r <- %s, $0
     1024 +                // into:
     1025 +                //      and.o   %s <- %a, $((1 << o) - 1)
     1026 +                //      setne.m %r <- %s, $0
     1027 +                // and same for setne/eq ... 0/1
     1028 +                osize = def->size;
     1029 +                def->opcode = OP_AND;
     1030 +                def->type = def->orig_type;
     1031 +                def->size = def->type->bit_size;
     1032 +                def->src2 = value_pseudo(bits_mask(osize));
     1033 +                return REPEAT_CSE;
 495 1034          }
     1035 +        return 0;
 496 1036  }
 497 1037  
     1038 +static int simplify_constant_mask(struct instruction *insn, unsigned long long mask)
     1039 +{
     1040 +        pseudo_t old = insn->src1;
     1041 +        unsigned long long omask;
     1042 +        unsigned long long nmask;
     1043 +        struct instruction *def;
     1044 +        int osize;
     1045 +
     1046 +        switch (DEF_OPCODE(def, old)) {
     1047 +        case OP_FPCMP ... OP_BINCMP_END:
     1048 +                osize = 1;
     1049 +                goto oldsize;
     1050 +        case OP_OR:
     1051 +                return simplify_mask_or(insn, mask, def);
     1052 +        case OP_LSR:
     1053 +        case OP_SHL:
     1054 +                return simplify_mask_shift(def, mask);
     1055 +        case OP_ZEXT:
     1056 +                osize = def->orig_type->bit_size;
     1057 +                /* fall through */
     1058 +        oldsize:
     1059 +                omask = (1ULL << osize) - 1;
     1060 +                nmask = mask & omask;
     1061 +                if (nmask == omask)
     1062 +                        // the AND mask is redundant
     1063 +                        return replace_with_pseudo(insn, old);
     1064 +                if (nmask != mask) {
     1065 +                        // can use a smaller mask
     1066 +                        insn->src2 = value_pseudo(nmask);
     1067 +                        return REPEAT_CSE;
     1068 +                }
     1069 +                break;
     1070 +        }
     1071 +        return 0;
     1072 +}
     1073 +
 498 1074  static int simplify_constant_rightside(struct instruction *insn)
 499 1075  {
 500 1076          long long value = insn->src2->value;
     1077 +        long long sbit = 1ULL << (insn->size - 1);
     1078 +        long long bits = sbit | (sbit - 1);
 501 1079  
 502 1080          switch (insn->opcode) {
 503      -        case OP_OR_BOOL:
 504      -                if (value == 1)
     1081 +        case OP_OR:
     1082 +                if ((value & bits) == bits)
 505 1083                          return replace_with_pseudo(insn, insn->src2);
 506 1084                  goto case_neutral_zero;
 507 1085  
     1086 +        case OP_XOR:
     1087 +                if ((value & bits) == bits) {
     1088 +                        insn->opcode = OP_NOT;
     1089 +                        return REPEAT_CSE;
     1090 +                }
     1091 +                goto case_neutral_zero;
     1092 +
 508 1093          case OP_SUB:
 509 1094                  if (value) {
 510 1095                          insn->opcode = OP_ADD;
 511      -                        insn->src2 = value_pseudo(insn->type, -value);
     1096 +                        insn->src2 = value_pseudo(-value);
 512 1097                          return REPEAT_CSE;
 513 1098                  }
 514 1099          /* Fall through */
 515 1100          case OP_ADD:
 516      -        case OP_OR: case OP_XOR:
 517      -        case OP_SHL:
 518      -        case OP_LSR:
 519 1101          case_neutral_zero:
 520 1102                  if (!value)
 521 1103                          return replace_with_pseudo(insn, insn->src1);
 522 1104                  return 0;
 523 1105          case OP_ASR:
 524      -                return simplify_asr(insn, insn->src1, value);
     1106 +        case OP_SHL:
     1107 +        case OP_LSR:
     1108 +                return simplify_shift(insn, insn->src1, value);
 525 1109  
 526 1110          case OP_MODU: case OP_MODS:
 527 1111                  if (value == 1)
 528      -                        return replace_with_pseudo(insn, value_pseudo(insn->type, 0));
     1112 +                        return replace_with_pseudo(insn, value_pseudo(0));
 529 1113                  return 0;
 530 1114  
 531 1115          case OP_DIVU: case OP_DIVS:
 532      -        case OP_MULU: case OP_MULS:
     1116 +        case OP_MUL:
 533 1117                  return simplify_mul_div(insn, value);
 534 1118  
 535      -        case OP_AND_BOOL:
 536      -                if (value == 1)
 537      -                        return replace_with_pseudo(insn, insn->src1);
 538      -        /* Fall through */
 539 1119          case OP_AND:
 540 1120                  if (!value)
 541 1121                          return replace_with_pseudo(insn, insn->src2);
 542      -                return 0;
     1122 +                if ((value & bits) == bits)
     1123 +                        return replace_with_pseudo(insn, insn->src1);
     1124 +                return simplify_constant_mask(insn, value);
 543 1125  
 544 1126          case OP_SET_NE:
 545 1127          case OP_SET_EQ:
 546 1128                  return simplify_seteq_setne(insn, value);
 547 1129          }
 548 1130          return 0;
 549 1131  }
 550 1132  
 551 1133  static int simplify_constant_leftside(struct instruction *insn)
 552 1134  {
↓ open down ↓ 1 lines elided ↑ open up ↑
 554 1136  
 555 1137          switch (insn->opcode) {
 556 1138          case OP_ADD: case OP_OR: case OP_XOR:
 557 1139                  if (!value)
 558 1140                          return replace_with_pseudo(insn, insn->src2);
 559 1141                  return 0;
 560 1142  
 561 1143          case OP_SHL:
 562 1144          case OP_LSR: case OP_ASR:
 563 1145          case OP_AND:
 564      -        case OP_MULU: case OP_MULS:
     1146 +        case OP_MUL:
 565 1147                  if (!value)
 566 1148                          return replace_with_pseudo(insn, insn->src1);
 567 1149                  return 0;
 568 1150          }
 569 1151          return 0;
 570 1152  }
 571 1153  
 572 1154  static int simplify_constant_binop(struct instruction *insn)
 573 1155  {
 574      -        /* FIXME! Verify signs and sizes!! */
 575      -        long long left = insn->src1->value;
 576      -        long long right = insn->src2->value;
 577      -        unsigned long long ul, ur;
 578      -        long long res, mask, bits;
     1156 +        pseudo_t res = eval_insn(insn);
 579 1157  
 580      -        mask = 1ULL << (insn->size-1);
 581      -        bits = mask | (mask-1);
 582      -
 583      -        if (left & mask)
 584      -                left |= ~bits;
 585      -        if (right & mask)
 586      -                right |= ~bits;
 587      -        ul = left & bits;
 588      -        ur = right & bits;
 589      -
 590      -        switch (insn->opcode) {
 591      -        case OP_ADD:
 592      -                res = left + right;
 593      -                break;
 594      -        case OP_SUB:
 595      -                res = left - right;
 596      -                break;
 597      -        case OP_MULU:
 598      -                res = ul * ur;
 599      -                break;
 600      -        case OP_MULS:
 601      -                res = left * right;
 602      -                break;
 603      -        case OP_DIVU:
 604      -                if (!ur)
 605      -                        return 0;
 606      -                res = ul / ur;
 607      -                break;
 608      -        case OP_DIVS:
 609      -                if (!right)
 610      -                        return 0;
 611      -                if (left == mask && right == -1)
 612      -                        return 0;
 613      -                res = left / right;
 614      -                break;
 615      -        case OP_MODU:
 616      -                if (!ur)
 617      -                        return 0;
 618      -                res = ul % ur;
 619      -                break;
 620      -        case OP_MODS:
 621      -                if (!right)
 622      -                        return 0;
 623      -                if (left == mask && right == -1)
 624      -                        return 0;
 625      -                res = left % right;
 626      -                break;
 627      -        case OP_SHL:
 628      -                res = left << right;
 629      -                break;
 630      -        case OP_LSR:
 631      -                res = ul >> ur;
 632      -                break;
 633      -        case OP_ASR:
 634      -                res = left >> right;
 635      -                break;
 636      -       /* Logical */
 637      -        case OP_AND:
 638      -                res = left & right;
 639      -                break;
 640      -        case OP_OR:
 641      -                res = left | right;
 642      -                break;
 643      -        case OP_XOR:
 644      -                res = left ^ right;
 645      -                break;
 646      -        case OP_AND_BOOL:
 647      -                res = left && right;
 648      -                break;
 649      -        case OP_OR_BOOL:
 650      -                res = left || right;
 651      -                break;
 652      -                               
 653      -        /* Binary comparison */
 654      -        case OP_SET_EQ:
 655      -                res = left == right;
 656      -                break;
 657      -        case OP_SET_NE:
 658      -                res = left != right;
 659      -                break;
 660      -        case OP_SET_LE:
 661      -                res = left <= right;
 662      -                break;
 663      -        case OP_SET_GE:
 664      -                res = left >= right;
 665      -                break;
 666      -        case OP_SET_LT:
 667      -                res = left < right;
 668      -                break;
 669      -        case OP_SET_GT:
 670      -                res = left > right;
 671      -                break;
 672      -        case OP_SET_B:
 673      -                res = ul < ur;
 674      -                break;
 675      -        case OP_SET_A:
 676      -                res = ul > ur;
 677      -                break;
 678      -        case OP_SET_BE:
 679      -                res = ul <= ur;
 680      -                break;
 681      -        case OP_SET_AE:
 682      -                res = ul >= ur;
 683      -                break;
 684      -        default:
     1158 +        if (!res)
 685 1159                  return 0;
 686      -        }
 687      -        res &= bits;
 688 1160  
 689      -        replace_with_pseudo(insn, value_pseudo(insn->type, res));
     1161 +        replace_with_pseudo(insn, res);
 690 1162          return REPEAT_CSE;
 691 1163  }
 692 1164  
 693 1165  static int simplify_binop_same_args(struct instruction *insn, pseudo_t arg)
 694 1166  {
 695 1167          switch (insn->opcode) {
 696 1168          case OP_SET_NE:
 697 1169          case OP_SET_LT: case OP_SET_GT:
 698 1170          case OP_SET_B:  case OP_SET_A:
 699 1171                  if (Wtautological_compare)
 700 1172                          warning(insn->pos, "self-comparison always evaluates to false");
 701 1173          case OP_SUB:
 702 1174          case OP_XOR:
 703      -                return replace_with_pseudo(insn, value_pseudo(insn->type, 0));
     1175 +                return replace_with_pseudo(insn, value_pseudo(0));
 704 1176  
 705 1177          case OP_SET_EQ:
 706 1178          case OP_SET_LE: case OP_SET_GE:
 707 1179          case OP_SET_BE: case OP_SET_AE:
 708 1180                  if (Wtautological_compare)
 709 1181                          warning(insn->pos, "self-comparison always evaluates to true");
 710      -                return replace_with_pseudo(insn, value_pseudo(insn->type, 1));
     1182 +                return replace_with_pseudo(insn, value_pseudo(1));
 711 1183  
 712 1184          case OP_AND:
 713 1185          case OP_OR:
 714 1186                  return replace_with_pseudo(insn, arg);
 715 1187  
 716      -        case OP_AND_BOOL:
 717      -        case OP_OR_BOOL:
 718      -                remove_usage(arg, &insn->src2);
 719      -                insn->src2 = value_pseudo(insn->type, 0);
 720      -                insn->opcode = OP_SET_NE;
 721      -                return REPEAT_CSE;
 722      -
 723 1188          default:
 724 1189                  break;
 725 1190          }
 726 1191  
 727 1192          return 0;
 728 1193  }
 729 1194  
 730 1195  static int simplify_binop(struct instruction *insn)
 731 1196  {
 732 1197          if (dead_insn(insn, &insn->src1, &insn->src2, NULL))
↓ open down ↓ 25 lines elided ↑ open up ↑
 758 1223          /* symbol/constants on the right */
 759 1224          if (p1->type == PSEUDO_VAL)
 760 1225                  return p2->type == PSEUDO_VAL;
 761 1226  
 762 1227          if (p1->type == PSEUDO_SYM)
 763 1228                  return p2->type == PSEUDO_SYM || p2->type == PSEUDO_VAL;
 764 1229  
 765 1230          return 1;
 766 1231  }
 767 1232  
 768      -static int simplify_commutative_binop(struct instruction *insn)
     1233 +static int canonicalize_commutative(struct instruction *insn)
 769 1234  {
 770      -        if (!canonical_order(insn->src1, insn->src2)) {
 771      -                switch_pseudo(insn, &insn->src1, insn, &insn->src2);
 772      -                return REPEAT_CSE;
 773      -        }
 774      -        return 0;
     1235 +        if (canonical_order(insn->src1, insn->src2))
     1236 +                return 0;
     1237 +
     1238 +        switch_pseudo(insn, &insn->src1, insn, &insn->src2);
     1239 +        return repeat_phase |= REPEAT_CSE;
 775 1240  }
 776 1241  
     1242 +static int canonicalize_compare(struct instruction *insn)
     1243 +{
     1244 +        if (canonical_order(insn->src1, insn->src2))
     1245 +                return 0;
     1246 +
     1247 +        switch_pseudo(insn, &insn->src1, insn, &insn->src2);
     1248 +        insn->opcode = opcode_table[insn->opcode].swap;
     1249 +        return repeat_phase |= REPEAT_CSE;
     1250 +}
     1251 +
 777 1252  static inline int simple_pseudo(pseudo_t pseudo)
 778 1253  {
 779 1254          return pseudo->type == PSEUDO_VAL || pseudo->type == PSEUDO_SYM;
 780 1255  }
 781 1256  
 782 1257  static int simplify_associative_binop(struct instruction *insn)
 783 1258  {
 784 1259          struct instruction *def;
 785 1260          pseudo_t pseudo = insn->src1;
 786 1261  
↓ open down ↓ 1 lines elided ↑ open up ↑
 788 1263                  return 0;
 789 1264          if (pseudo->type != PSEUDO_REG)
 790 1265                  return 0;
 791 1266          def = pseudo->def;
 792 1267          if (def == insn)
 793 1268                  return 0;
 794 1269          if (def->opcode != insn->opcode)
 795 1270                  return 0;
 796 1271          if (!simple_pseudo(def->src2))
 797 1272                  return 0;
 798      -        if (ptr_list_size((struct ptr_list *)def->target->users) != 1)
     1273 +        if (multi_users(def->target))
 799 1274                  return 0;
 800 1275          switch_pseudo(def, &def->src1, insn, &insn->src2);
 801 1276          return REPEAT_CSE;
 802 1277  }
 803 1278  
 804 1279  static int simplify_constant_unop(struct instruction *insn)
 805 1280  {
 806 1281          long long val = insn->src1->value;
 807 1282          long long res, mask;
 808 1283  
 809 1284          switch (insn->opcode) {
 810 1285          case OP_NOT:
 811 1286                  res = ~val;
 812 1287                  break;
 813 1288          case OP_NEG:
 814 1289                  res = -val;
 815 1290                  break;
     1291 +        case OP_SEXT:
     1292 +                mask = 1ULL << (insn->orig_type->bit_size-1);
     1293 +                if (val & mask)
     1294 +                        val |= ~(mask | (mask-1));
     1295 +                /* fall through */
     1296 +        case OP_ZEXT:
     1297 +        case OP_TRUNC:
     1298 +                res = val;
     1299 +                break;
 816 1300          default:
 817 1301                  return 0;
 818 1302          }
 819 1303          mask = 1ULL << (insn->size-1);
 820 1304          res &= mask | (mask-1);
 821 1305          
 822      -        replace_with_pseudo(insn, value_pseudo(insn->type, res));
     1306 +        replace_with_pseudo(insn, value_pseudo(res));
 823 1307          return REPEAT_CSE;
 824 1308  }
 825 1309  
 826 1310  static int simplify_unop(struct instruction *insn)
 827 1311  {
 828 1312          if (dead_insn(insn, &insn->src1, NULL, NULL))
 829 1313                  return REPEAT_CSE;
 830 1314          if (constant(insn->src1))
 831 1315                  return simplify_constant_unop(insn);
 832 1316  
↓ open down ↓ 37 lines elided ↑ open up ↑
 870 1354                          off = def->src1;
 871 1355                          if (constant(off))
 872 1356                                  goto offset;
 873 1357                          return 0;
 874 1358                  }
 875 1359          }
 876 1360          return 0;
 877 1361  
 878 1362  offset:
 879 1363          /* Invalid code */
 880      -        if (new == orig) {
     1364 +        if (new == orig || new == addr) {
 881 1365                  if (new == VOID)
 882 1366                          return 0;
 883 1367                  /*
 884 1368                   * If some BB have been removed it is possible that this
 885 1369                   * memop is in fact part of a dead BB. In this case
 886 1370                   * we must not warn since nothing is wrong.
 887 1371                   * If not part of a dead BB this will be redone after
 888 1372                   * the BBs have been cleaned up.
 889 1373                   */
 890 1374                  if (repeat_phase & REPEAT_CFG_CLEANUP)
 891 1375                          return 0;
 892      -                new = VOID;
 893 1376                  warning(insn->pos, "crazy programmer");
     1377 +                replace_pseudo(insn, &insn->src, VOID);
     1378 +                return 0;
 894 1379          }
 895 1380          insn->offset += off->value;
 896      -        use_pseudo(insn, new, &insn->src);
 897      -        remove_usage(addr, &insn->src);
     1381 +        replace_pseudo(insn, &insn->src, new);
 898 1382          return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
 899 1383  }
 900 1384  
 901      -/*
 902      - * We walk the whole chain of adds/subs backwards. That's not
 903      - * only more efficient, but it allows us to find loops.
 904      - */
     1385 +///
     1386 +// simplify memops instructions
     1387 +//
     1388 +// :note: We walk the whole chain of adds/subs backwards.
     1389 +//      That's not only more efficient, but it allows us to find loops.
 905 1390  static int simplify_memop(struct instruction *insn)
 906 1391  {
 907 1392          int one, ret = 0;
 908 1393          pseudo_t orig = insn->src;
 909 1394  
 910 1395          do {
 911 1396                  one = simplify_one_memop(insn, orig);
 912 1397                  ret |= one;
 913 1398          } while (one);
 914 1399          return ret;
 915 1400  }
 916 1401  
 917      -static long long get_cast_value(long long val, int old_size, int new_size, int sign)
 918      -{
 919      -        long long mask;
 920      -
 921      -        if (sign && new_size > old_size) {
 922      -                mask = 1 << (old_size-1);
 923      -                if (val & mask)
 924      -                        val |= ~(mask | (mask-1));
 925      -        }
 926      -        mask = 1 << (new_size-1);
 927      -        return val & (mask | (mask-1));
 928      -}
 929      -
 930 1402  static int simplify_cast(struct instruction *insn)
 931 1403  {
 932      -        struct symbol *orig_type;
 933      -        int orig_size, size;
     1404 +        unsigned long long mask;
     1405 +        struct instruction *def;
 934 1406          pseudo_t src;
     1407 +        pseudo_t val;
     1408 +        int osize;
     1409 +        int size;
 935 1410  
 936 1411          if (dead_insn(insn, &insn->src, NULL, NULL))
 937 1412                  return REPEAT_CSE;
 938 1413  
 939      -        orig_type = insn->orig_type;
 940      -        if (!orig_type)
 941      -                return 0;
     1414 +        src = insn->src;
 942 1415  
 943      -        /* Keep casts with pointer on either side (not only case of OP_PTRCAST) */
 944      -        if (is_ptr_type(orig_type) || is_ptr_type(insn->type))
 945      -                return 0;
     1416 +        /* A cast of a constant? */
     1417 +        if (constant(src))
     1418 +                return simplify_constant_unop(insn);
 946 1419  
 947      -        orig_size = orig_type->bit_size;
     1420 +        // can merge with the previous instruction?
 948 1421          size = insn->size;
 949      -        src = insn->src;
     1422 +        def = src->def;
     1423 +        switch (def_opcode(src)) {
     1424 +        case OP_AND:
     1425 +                val = def->src2;
     1426 +                if (val->type != PSEUDO_VAL)
     1427 +                        break;
     1428 +                /* A cast of a AND might be a no-op.. */
     1429 +                switch (insn->opcode) {
     1430 +                case OP_TRUNC:
     1431 +                        if (multi_users(src))
     1432 +                                break;
     1433 +                        def->opcode = OP_TRUNC;
     1434 +                        def->orig_type = def->type;
     1435 +                        def->type = insn->type;
     1436 +                        def->size = size;
 950 1437  
 951      -        /* A cast of a constant? */
 952      -        if (constant(src)) {
 953      -                int sign = orig_type->ctype.modifiers & MOD_SIGNED;
 954      -                long long val = get_cast_value(src->value, orig_size, size, sign);
 955      -                src = value_pseudo(orig_type, val);
 956      -                goto simplify;
 957      -        }
     1438 +                        insn->opcode = OP_AND;
     1439 +                        mask = val->value;
     1440 +                        mask &= (1ULL << size) - 1;
     1441 +                        insn->src2 = value_pseudo(mask);
     1442 +                        return REPEAT_CSE;
 958 1443  
 959      -        /* A cast of a "and" might be a no-op.. */
 960      -        if (src->type == PSEUDO_REG) {
 961      -                struct instruction *def = src->def;
 962      -                if (def->opcode == OP_AND && def->size >= size) {
 963      -                        pseudo_t val = def->src2;
 964      -                        if (val->type == PSEUDO_VAL) {
 965      -                                unsigned long long value = val->value;
 966      -                                if (!(value >> (size-1)))
 967      -                                        goto simplify;
 968      -                        }
     1444 +                case OP_SEXT:
     1445 +                        if (val->value & (1 << (def->size - 1)))
     1446 +                                break;
     1447 +                        // OK, sign bit is 0
     1448 +                case OP_ZEXT:
     1449 +                        if (multi_users(src))
     1450 +                                break;
     1451 +                        // transform:
     1452 +                        //      and.n   %b <- %a, M
     1453 +                        //      *ext.m  %c <- (n) %b
     1454 +                        // into:
     1455 +                        //      zext.m  %b <- %a
     1456 +                        //      and.m   %c <- %b, M
     1457 +                        // For ZEXT, the mask will always be small
     1458 +                        // enough. For SEXT, it can only be done if
     1459 +                        // the mask force the sign bit to 0.
     1460 +                        def->opcode = OP_ZEXT;
     1461 +                        def->orig_type = insn->orig_type;
     1462 +                        def->type = insn->type;
     1463 +                        def->size = insn->size;
     1464 +                        insn->opcode = OP_AND;
     1465 +                        insn->src2 = val;
     1466 +                        return REPEAT_CSE;
 969 1467                  }
     1468 +                break;
     1469 +        case OP_FPCMP ... OP_BINCMP_END:
     1470 +                switch (insn->opcode) {
     1471 +                case OP_SEXT:
     1472 +                        if (insn->size == 1)
     1473 +                                break;
     1474 +                        /* fall through */
     1475 +                case OP_ZEXT:
     1476 +                case OP_TRUNC:
     1477 +                        // simplify:
     1478 +                        //      setcc.n %t <- %a, %b
     1479 +                        //      zext.m  %r <- (n) %t
     1480 +                        // into:
     1481 +                        //      setcc.m %r <- %a, %b
     1482 +                        // and same for s/zext/trunc/
     1483 +                        insn->opcode = def->opcode;
     1484 +                        use_pseudo(insn, def->src2, &insn->src2);
     1485 +                        return replace_pseudo(insn, &insn->src1, def->src1);
     1486 +                }
     1487 +                break;
     1488 +        case OP_OR:
     1489 +                switch (insn->opcode) {
     1490 +                case OP_TRUNC:
     1491 +                        mask = bits_mask(insn->size);
     1492 +                        return simplify_mask_or(insn, mask, def);
     1493 +                }
     1494 +                break;
     1495 +        case OP_LSR:
     1496 +        case OP_SHL:
     1497 +                if (insn->opcode != OP_TRUNC)
     1498 +                        break;
     1499 +                mask = bits_mask(insn->size);
     1500 +                return simplify_mask_shift(def, mask);
     1501 +        case OP_TRUNC:
     1502 +                switch (insn->opcode) {
     1503 +                case OP_TRUNC:
     1504 +                        insn->orig_type = def->orig_type;
     1505 +                        return replace_pseudo(insn, &insn->src1, def->src);
     1506 +                case OP_ZEXT:
     1507 +                        if (size != def->orig_type->bit_size)
     1508 +                                break;
     1509 +                        insn->opcode = OP_AND;
     1510 +                        insn->src2 = value_pseudo((1ULL << def->size) - 1);
     1511 +                        return replace_pseudo(insn, &insn->src1, def->src);
     1512 +                }
     1513 +                break;
     1514 +        case OP_ZEXT:
     1515 +                switch (insn->opcode) {
     1516 +                case OP_SEXT:
     1517 +                        insn->opcode = OP_ZEXT;
     1518 +                        /* fall through */
     1519 +                case OP_ZEXT:
     1520 +                        insn->orig_type = def->orig_type;
     1521 +                        return replace_pseudo(insn, &insn->src, def->src);
     1522 +                }
     1523 +                /* fall through */
     1524 +        case OP_SEXT:
     1525 +                switch (insn->opcode) {
     1526 +                case OP_TRUNC:
     1527 +                        osize = def->orig_type->bit_size;
     1528 +                        if (size == osize)
     1529 +                                return replace_with_pseudo(insn, def->src);
     1530 +                        if (size > osize)
     1531 +                                insn->opcode = def->opcode;
     1532 +                        insn->orig_type = def->orig_type;
     1533 +                        return replace_pseudo(insn, &insn->src, def->src);
     1534 +                }
     1535 +                switch (insn->opcode) {
     1536 +                case OP_SEXT:
     1537 +                        insn->orig_type = def->orig_type;
     1538 +                        return replace_pseudo(insn, &insn->src, def->src);
     1539 +                }
     1540 +                break;
 970 1541          }
 971 1542  
 972      -        if (size == orig_size) {
 973      -                int op = (orig_type->ctype.modifiers & MOD_SIGNED) ? OP_SCAST : OP_CAST;
 974      -                if (insn->opcode == op)
 975      -                        goto simplify;
 976      -                if (insn->opcode == OP_FPCAST && is_float_type(orig_type))
 977      -                        goto simplify;
 978      -        }
 979      -
 980 1543          return 0;
 981      -
 982      -simplify:
 983      -        return replace_with_pseudo(insn, src);
 984 1544  }
 985 1545  
 986 1546  static int simplify_select(struct instruction *insn)
 987 1547  {
 988 1548          pseudo_t cond, src1, src2;
 989 1549  
 990 1550          if (dead_insn(insn, &insn->src1, &insn->src2, &insn->src3))
 991 1551                  return REPEAT_CSE;
 992 1552  
 993 1553          cond = insn->src1;
↓ open down ↓ 18 lines elided ↑ open up ↑
1012 1572                          if (val1) {
1013 1573                                  src1 = src2;
1014 1574                                  opcode = OP_SET_NE;
1015 1575                          }
1016 1576                          insn->opcode = opcode;
1017 1577                          /* insn->src1 is already cond */
1018 1578                          insn->src2 = src1; /* Zero */
1019 1579                          return REPEAT_CSE;
1020 1580                  }
1021 1581          }
     1582 +        if (cond == src2 && is_zero(src1)) {
     1583 +                kill_use(&insn->src1);
     1584 +                kill_use(&insn->src3);
     1585 +                replace_with_pseudo(insn, value_pseudo(0));
     1586 +                return REPEAT_CSE;
     1587 +        }
1022 1588          return 0;
1023 1589  }
1024 1590  
1025 1591  static int is_in_range(pseudo_t src, long long low, long long high)
1026 1592  {
1027 1593          long long value;
1028 1594  
1029 1595          switch (src->type) {
1030 1596          case PSEUDO_VAL:
1031 1597                  value = src->value;
↓ open down ↓ 12 lines elided ↑ open up ↑
1044 1610          src3 = insn->src3;
1045 1611          if (src2->type != PSEUDO_VAL || src3->type != PSEUDO_VAL)
1046 1612                  return 0;
1047 1613          if (is_in_range(src1, src2->value, src3->value)) {
1048 1614                  kill_instruction(insn);
1049 1615                  return REPEAT_CSE;
1050 1616          }
1051 1617          return 0;
1052 1618  }
1053 1619  
1054      -/*
1055      - * Simplify "set_ne/eq $0 + br"
1056      - */
1057      -static int simplify_cond_branch(struct instruction *br, pseudo_t cond, struct instruction *def, pseudo_t *pp)
     1620 +///
     1621 +// simplify SET_NE/EQ $0 + BR
     1622 +static int simplify_cond_branch(struct instruction *br, struct instruction *def, pseudo_t newcond)
1058 1623  {
1059      -        use_pseudo(br, *pp, &br->cond);
1060      -        remove_usage(cond, &br->cond);
     1624 +        replace_pseudo(br, &br->cond, newcond);
1061 1625          if (def->opcode == OP_SET_EQ) {
1062      -                struct basic_block *true = br->bb_true;
1063      -                struct basic_block *false = br->bb_false;
1064      -                br->bb_false = true;
1065      -                br->bb_true = false;
     1626 +                struct basic_block *tmp = br->bb_true;
     1627 +                br->bb_true = br->bb_false;
     1628 +                br->bb_false = tmp;
1066 1629          }
1067 1630          return REPEAT_CSE;
1068 1631  }
1069 1632  
1070 1633  static int simplify_branch(struct instruction *insn)
1071 1634  {
1072 1635          pseudo_t cond = insn->cond;
1073 1636  
1074 1637          /* Constant conditional */
1075 1638          if (constant(cond)) {
↓ open down ↓ 13 lines elided ↑ open up ↑
1089 1652                  insn->opcode = OP_BR;
1090 1653                  return REPEAT_CSE;
1091 1654          }
1092 1655  
1093 1656          /* Conditional on a SETNE $0 or SETEQ $0 */
1094 1657          if (cond->type == PSEUDO_REG) {
1095 1658                  struct instruction *def = cond->def;
1096 1659  
1097 1660                  if (def->opcode == OP_SET_NE || def->opcode == OP_SET_EQ) {
1098 1661                          if (constant(def->src1) && !def->src1->value)
1099      -                                return simplify_cond_branch(insn, cond, def, &def->src2);
     1662 +                                return simplify_cond_branch(insn, def, def->src2);
1100 1663                          if (constant(def->src2) && !def->src2->value)
1101      -                                return simplify_cond_branch(insn, cond, def, &def->src1);
     1664 +                                return simplify_cond_branch(insn, def, def->src1);
1102 1665                  }
1103 1666                  if (def->opcode == OP_SEL) {
1104 1667                          if (constant(def->src2) && constant(def->src3)) {
1105 1668                                  long long val1 = def->src2->value;
1106 1669                                  long long val2 = def->src3->value;
1107 1670                                  if (!val1 && !val2) {
1108 1671                                          insert_branch(insn->bb, insn, insn->bb_false);
1109 1672                                          return REPEAT_CSE;
1110 1673                                  }
1111 1674                                  if (val1 && val2) {
1112 1675                                          insert_branch(insn->bb, insn, insn->bb_true);
1113 1676                                          return REPEAT_CSE;
1114 1677                                  }
1115 1678                                  if (val2) {
1116      -                                        struct basic_block *true = insn->bb_true;
1117      -                                        struct basic_block *false = insn->bb_false;
1118      -                                        insn->bb_false = true;
1119      -                                        insn->bb_true = false;
     1679 +                                        struct basic_block *tmp = insn->bb_true;
     1680 +                                        insn->bb_true = insn->bb_false;
     1681 +                                        insn->bb_false = tmp;
1120 1682                                  }
1121      -                                use_pseudo(insn, def->src1, &insn->cond);
1122      -                                remove_usage(cond, &insn->cond);
1123      -                                return REPEAT_CSE;
     1683 +                                return replace_pseudo(insn, &insn->cond, def->src1);
1124 1684                          }
1125 1685                  }
1126      -                if (def->opcode == OP_CAST || def->opcode == OP_SCAST) {
1127      -                        int orig_size = def->orig_type ? def->orig_type->bit_size : 0;
1128      -                        if (def->size > orig_size) {
1129      -                                use_pseudo(insn, def->src, &insn->cond);
1130      -                                remove_usage(cond, &insn->cond);
1131      -                                return REPEAT_CSE;
1132      -                        }
1133      -                }
     1686 +                if (def->opcode == OP_SEXT || def->opcode == OP_ZEXT)
     1687 +                        return replace_pseudo(insn, &insn->cond, def->src);
1134 1688          }
1135 1689          return 0;
1136 1690  }
1137 1691  
1138 1692  static int simplify_switch(struct instruction *insn)
1139 1693  {
1140 1694          pseudo_t cond = insn->cond;
1141 1695          long long val;
1142 1696          struct multijmp *jmp;
1143 1697  
↓ open down ↓ 14 lines elided ↑ open up ↑
1158 1712  found:
1159 1713          insert_branch(insn->bb, insn, jmp->target);
1160 1714          return REPEAT_CSE;
1161 1715  }
1162 1716  
1163 1717  int simplify_instruction(struct instruction *insn)
1164 1718  {
1165 1719          if (!insn->bb)
1166 1720                  return 0;
1167 1721          switch (insn->opcode) {
1168      -        case OP_ADD: case OP_MULS:
     1722 +        case OP_ADD: case OP_MUL:
1169 1723          case OP_AND: case OP_OR: case OP_XOR:
1170      -        case OP_AND_BOOL: case OP_OR_BOOL:
     1724 +                canonicalize_commutative(insn);
1171 1725                  if (simplify_binop(insn))
1172 1726                          return REPEAT_CSE;
1173      -                if (simplify_commutative_binop(insn))
1174      -                        return REPEAT_CSE;
1175 1727                  return simplify_associative_binop(insn);
1176 1728  
1177      -        case OP_MULU:
1178 1729          case OP_SET_EQ: case OP_SET_NE:
1179      -                if (simplify_binop(insn))
1180      -                        return REPEAT_CSE;
1181      -                return simplify_commutative_binop(insn);
     1730 +                canonicalize_commutative(insn);
     1731 +                return simplify_binop(insn);
1182 1732  
     1733 +        case OP_SET_LE: case OP_SET_GE:
     1734 +        case OP_SET_LT: case OP_SET_GT:
     1735 +        case OP_SET_B:  case OP_SET_A:
     1736 +        case OP_SET_BE: case OP_SET_AE:
     1737 +                canonicalize_compare(insn);
     1738 +                /* fall through */
1183 1739          case OP_SUB:
1184 1740          case OP_DIVU: case OP_DIVS:
1185 1741          case OP_MODU: case OP_MODS:
1186 1742          case OP_SHL:
1187 1743          case OP_LSR: case OP_ASR:
1188      -        case OP_SET_LE: case OP_SET_GE:
1189      -        case OP_SET_LT: case OP_SET_GT:
1190      -        case OP_SET_B:  case OP_SET_A:
1191      -        case OP_SET_BE: case OP_SET_AE:
1192 1744                  return simplify_binop(insn);
1193 1745  
1194      -        case OP_NOT: case OP_NEG:
     1746 +        case OP_NOT: case OP_NEG: case OP_FNEG:
1195 1747                  return simplify_unop(insn);
1196      -        case OP_LOAD: case OP_STORE:
     1748 +        case OP_LOAD:
     1749 +                if (!has_users(insn->target))
     1750 +                        return kill_instruction(insn);
     1751 +                /* fall-through */
     1752 +        case OP_STORE:
1197 1753                  return simplify_memop(insn);
1198 1754          case OP_SYMADDR:
1199      -                if (dead_insn(insn, NULL, NULL, NULL))
     1755 +                if (dead_insn(insn, &insn->src, NULL, NULL))
1200 1756                          return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
1201      -                return replace_with_pseudo(insn, insn->symbol);
1202      -        case OP_CAST:
1203      -        case OP_SCAST:
1204      -        case OP_FPCAST:
1205      -        case OP_PTRCAST:
     1757 +                return replace_with_pseudo(insn, insn->src);
     1758 +        case OP_SEXT: case OP_ZEXT:
     1759 +        case OP_TRUNC:
1206 1760                  return simplify_cast(insn);
     1761 +        case OP_FCVTU: case OP_FCVTS:
     1762 +        case OP_UCVTF: case OP_SCVTF:
     1763 +        case OP_FCVTF:
     1764 +        case OP_PTRCAST:
     1765 +                if (dead_insn(insn, &insn->src, NULL, NULL))
     1766 +                        return REPEAT_CSE;
     1767 +                break;
     1768 +        case OP_UTPTR:
     1769 +        case OP_PTRTU:
     1770 +                return replace_with_pseudo(insn, insn->src);
     1771 +        case OP_SLICE:
     1772 +                if (dead_insn(insn, &insn->src, NULL, NULL))
     1773 +                        return REPEAT_CSE;
     1774 +                break;
     1775 +        case OP_SETVAL:
     1776 +        case OP_SETFVAL:
     1777 +                if (dead_insn(insn, NULL, NULL, NULL))
     1778 +                        return REPEAT_CSE;
     1779 +                break;
1207 1780          case OP_PHI:
1208 1781                  if (dead_insn(insn, NULL, NULL, NULL)) {
1209 1782                          kill_use_list(insn->phi_list);
1210 1783                          return REPEAT_CSE;
1211 1784                  }
1212 1785                  return clean_up_phi(insn);
1213 1786          case OP_PHISOURCE:
1214 1787                  if (dead_insn(insn, &insn->phi_src, NULL, NULL))
1215 1788                          return REPEAT_CSE;
1216 1789                  break;
1217 1790          case OP_SEL:
1218 1791                  return simplify_select(insn);
1219 1792          case OP_CBR:
1220 1793                  return simplify_branch(insn);
1221 1794          case OP_SWITCH:
1222 1795                  return simplify_switch(insn);
1223 1796          case OP_RANGE:
1224 1797                  return simplify_range(insn);
     1798 +        case OP_FADD:
     1799 +        case OP_FSUB:
     1800 +        case OP_FMUL:
     1801 +        case OP_FDIV:
     1802 +                if (dead_insn(insn, &insn->src1, &insn->src2, NULL))
     1803 +                        return REPEAT_CSE;
     1804 +                break;
1225 1805          }
1226 1806          return 0;
1227 1807  }
    
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX