Print this page
11972 resync smatch
*** 2,20 ****
* Simplify - do instruction simplification before CSE
*
* Copyright (C) 2004 Linus Torvalds
*/
#include <assert.h>
#include "parse.h"
#include "expression.h"
#include "linearize.h"
#include "flow.h"
#include "symbol.h"
! /* Find the trivial parent for a phi-source */
static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseudo)
{
/* Can't go upwards if the pseudo is defined in the bb it came from.. */
if (pseudo->type == PSEUDO_REG) {
struct instruction *def = pseudo->def;
--- 2,60 ----
* Simplify - do instruction simplification before CSE
*
* Copyright (C) 2004 Linus Torvalds
*/
+ ///
+ // Instruction simplification
+ // --------------------------
+ //
+ // Notation
+ // ^^^^^^^^
+ // The following conventions are used to describe the simplications:
+ // * Uppercase letters are reserved for constants:
+ // * `M` for a constant mask,
+ // * `S` for a constant shift,
+ // * `N` for a constant number of bits (usually other than a shift),
+ // * `C` or 'K' for others constants.
+ // * Lowercase letters `a`, `b`, `x`, `y`, ... are used for non-constants
+ // or when it doesn't matter if the pseudo is a constant or not.
+ // * Primes are used if needed to distinguish symbols (`M`, `M'`, ...).
+ // * Expressions or sub-expressions involving only constants are
+ // understood to be evaluated.
+ // * `$mask(N)` is used for `((1 << N) -1)`
+ // * `$trunc(x, N)` is used for `(x & $mask(N))`
+ // * Expressions like `(-1 << S)`, `(-1 >> S)` and others formulae are
+ // understood to be truncated to the size of the current instruction
+ // (needed, since in general this size is not the same as the one used
+ // by sparse for the evaluation of arithmetic operations).
+ // * `TRUNC(x, N)` is used for a truncation *to* a size of `N` bits
+ // * `ZEXT(x, N)` is used for a zero-extension *from* a size of `N` bits
+ // * `OP(x, C)` is used to represent some generic operation using a constant,
+ // including when the constant is implicit (e.g. `TRUNC(x, N)`).
+ // * `MASK(x, M)` is used to respresent a 'masking' instruction:
+ // - `AND(x, M)`
+ // - `LSR(x, S)`, with `M` = (-1 << S)
+ // - `SHL(x, S)`, with `M` = (-1 >> S)
+ // - `TRUNC(x, N)`, with `M` = $mask(N)
+ // - `ZEXT(x, N)`, with `M` = $mask(N)
+ // * `SHIFT(x, S)` is used for `LSR(x, S)` or `SHL(x, S)`.
+
#include <assert.h>
#include "parse.h"
#include "expression.h"
#include "linearize.h"
#include "flow.h"
#include "symbol.h"
! ///
! // Utilities
! // ^^^^^^^^^
!
! ///
! // find the trivial parent for a phi-source
static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseudo)
{
/* Can't go upwards if the pseudo is defined in the bb it came from.. */
if (pseudo->type == PSEUDO_REG) {
struct instruction *def = pseudo->def;
*** 24,43 ****
if (bb_list_size(source->children) != 1 || bb_list_size(source->parents) != 1)
return source;
return first_basic_block(source->parents);
}
! /*
! * Copy the phi-node's phisrcs into to given array.
! * Returns 0 if the the list contained the expected
! * number of element, a positive number if there was
! * more than expected and a negative one if less.
! *
! * Note: we can't reuse a function like linearize_ptr_list()
! * because any VOIDs in the phi-list must be ignored here
! * as in this context they mean 'entry has been removed'.
! */
static int get_phisources(struct instruction *sources[], int nbr, struct instruction *insn)
{
pseudo_t phi;
int i = 0;
--- 64,82 ----
if (bb_list_size(source->children) != 1 || bb_list_size(source->parents) != 1)
return source;
return first_basic_block(source->parents);
}
! ///
! // copy the phi-node's phisrcs into to given array
! // @return: 0 if the the list contained the expected
! // number of element, a positive number if there was
! // more than expected and a negative one if less.
! //
! // :note: we can't reuse a function like linearize_ptr_list()
! // because any VOIDs in the phi-list must be ignored here
! // as in this context they mean 'entry has been removed'.
static int get_phisources(struct instruction *sources[], int nbr, struct instruction *insn)
{
pseudo_t phi;
int i = 0;
*** 66,78 ****
bb = insn->bb;
if (get_phisources(array, 2, insn))
return 0;
if (linearize_ptr_list((struct ptr_list *)bb->parents, (void **)parents, 3) != 2)
return 0;
! p1 = array[0]->src1;
bb1 = array[0]->bb;
! p2 = array[1]->src1;
bb2 = array[1]->bb;
/* Only try the simple "direct parents" case */
if ((bb1 != parents[0] || bb2 != parents[1]) &&
(bb1 != parents[1] || bb2 != parents[0]))
--- 105,117 ----
bb = insn->bb;
if (get_phisources(array, 2, insn))
return 0;
if (linearize_ptr_list((struct ptr_list *)bb->parents, (void **)parents, 3) != 2)
return 0;
! p1 = array[0]->phi_src;
bb1 = array[0]->bb;
! p2 = array[1]->phi_src;
bb2 = array[1]->bb;
/* Only try the simple "direct parents" case */
if ((bb1 != parents[0] || bb2 != parents[1]) &&
(bb1 != parents[1] || bb2 != parents[0]))
*** 131,165 ****
insert_select(source, br, insn, p1, p2);
kill_instruction(insn);
return REPEAT_CSE;
}
! static int clean_up_phi(struct instruction *insn)
{
pseudo_t phi;
- struct instruction *last;
- int same;
! last = NULL;
! same = 1;
FOR_EACH_PTR(insn->phi_list, phi) {
struct instruction *def;
if (phi == VOID)
continue;
def = phi->def;
! if (def->src1 == VOID || !def->bb)
continue;
! if (last) {
! if (last->src1 != def->src1)
! same = 0;
continue;
}
! last = def;
} END_FOR_EACH_PTR(phi);
! if (same) {
! pseudo_t pseudo = last ? last->src1 : VOID;
convert_instruction_target(insn, pseudo);
kill_instruction(insn);
return REPEAT_CSE;
}
--- 170,237 ----
insert_select(source, br, insn, p1, p2);
kill_instruction(insn);
return REPEAT_CSE;
}
! ///
! // detect trivial phi-nodes
! // @insn: the phi-node
! // @pseudo: the candidate resulting pseudo (NULL when starting)
! // @return: the unique result if the phi-node is trivial, NULL otherwise
! //
! // A phi-node is trivial if it has a single possible result:
! // * all operands are the same
! // * the operands are themselves defined by a chain or cycle of phi-nodes
! // and the set of all operands involved contains a single value
! // not defined by these phi-nodes
! //
! // Since the result is unique, these phi-nodes can be removed.
! static pseudo_t trivial_phi(pseudo_t pseudo, struct instruction *insn, struct pseudo_list **list)
{
+ pseudo_t target = insn->target;
pseudo_t phi;
! add_pseudo(list, target);
!
FOR_EACH_PTR(insn->phi_list, phi) {
struct instruction *def;
+ pseudo_t src;
+
if (phi == VOID)
continue;
def = phi->def;
! if (!def->bb)
continue;
! src = def->phi_src; // bypass OP_PHISRC & get the real source
! if (src == VOID)
continue;
+ if (!pseudo) {
+ pseudo = src;
+ continue;
}
! if (src == pseudo)
! continue;
! if (src == target)
! continue;
! if (DEF_OPCODE(def, src) == OP_PHI) {
! if (pseudo_in_list(*list, src))
! continue;
! if ((pseudo = trivial_phi(pseudo, def, list)))
! continue;
! }
! return NULL;
} END_FOR_EACH_PTR(phi);
! return pseudo ? pseudo : VOID;
! }
!
! static int clean_up_phi(struct instruction *insn)
! {
! struct pseudo_list *list = NULL;
! pseudo_t pseudo;
!
! if ((pseudo = trivial_phi(NULL, insn, &list))) {
convert_instruction_target(insn, pseudo);
kill_instruction(insn);
return REPEAT_CSE;
}
*** 177,209 ****
goto out;
}
} END_FOR_EACH_PTR(pu);
assert(count <= 0);
out:
! if (ptr_list_size((struct ptr_list *) *list) == 0)
*list = NULL;
return count;
}
! static inline void remove_usage(pseudo_t p, pseudo_t *usep)
{
if (has_use_list(p)) {
delete_pseudo_user_list_entry(&p->users, usep, 1);
! if (!p->users)
kill_instruction(p->def);
}
}
void kill_use(pseudo_t *usep)
{
if (usep) {
pseudo_t p = *usep;
*usep = VOID;
! remove_usage(p, usep);
}
}
static void kill_use_list(struct pseudo_list *list)
{
pseudo_t p;
FOR_EACH_PTR(list, p) {
if (p == VOID)
--- 249,296 ----
goto out;
}
} END_FOR_EACH_PTR(pu);
assert(count <= 0);
out:
! if (pseudo_user_list_empty(*list))
*list = NULL;
return count;
}
! static inline void rem_usage(pseudo_t p, pseudo_t *usep, int kill)
{
if (has_use_list(p)) {
+ if (p->type == PSEUDO_SYM)
+ repeat_phase |= REPEAT_SYMBOL_CLEANUP;
delete_pseudo_user_list_entry(&p->users, usep, 1);
! if (kill && !p->users)
kill_instruction(p->def);
}
}
+ static inline void remove_usage(pseudo_t p, pseudo_t *usep)
+ {
+ rem_usage(p, usep, 1);
+ }
+
void kill_use(pseudo_t *usep)
{
if (usep) {
pseudo_t p = *usep;
*usep = VOID;
! rem_usage(p, usep, 1);
}
}
+ // Like kill_use() but do not (recursively) kill dead instructions
+ void remove_use(pseudo_t *usep)
+ {
+ pseudo_t p = *usep;
+ *usep = VOID;
+ rem_usage(p, usep, 0);
+ }
+
static void kill_use_list(struct pseudo_list *list)
{
pseudo_t p;
FOR_EACH_PTR(list, p) {
if (p == VOID)
*** 210,232 ****
continue;
kill_use(THIS_ADDRESS(p));
} END_FOR_EACH_PTR(p);
}
! /*
! * kill an instruction:
! * - remove it from its bb
! * - remove the usage of all its operands
! * If forse is zero, the normal case, the function only for
! * instructions free of (possible) side-effects. Otherwise
! * the function does that unconditionally (must only be used
! * for unreachable instructions.
! */
! void kill_insn(struct instruction *insn, int force)
{
if (!insn || !insn->bb)
! return;
switch (insn->opcode) {
case OP_SEL:
case OP_RANGE:
kill_use(&insn->src3);
--- 297,320 ----
continue;
kill_use(THIS_ADDRESS(p));
} END_FOR_EACH_PTR(p);
}
! ///
! // kill an instruction
! // @insn: the instruction to be killed
! // @force: if unset, the normal case, the instruction is not killed
! // if not free of possible side-effect; if set the instruction
! // is unconditionally killed.
! //
! // The killed instruction is removed from its BB and the usage
! // of all its operands are removed. The instruction is also
! // marked as killed by setting its ->bb to NULL.
! int kill_insn(struct instruction *insn, int force)
{
if (!insn || !insn->bb)
! return 0;
switch (insn->opcode) {
case OP_SEL:
case OP_RANGE:
kill_use(&insn->src3);
*** 234,249 ****
case OP_BINARY ... OP_BINCMP_END:
kill_use(&insn->src2);
/* fall through */
! case OP_CAST:
! case OP_SCAST:
! case OP_FPCAST:
! case OP_PTRCAST:
case OP_SETVAL:
- case OP_NOT: case OP_NEG:
case OP_SLICE:
kill_use(&insn->src1);
break;
case OP_PHI:
--- 322,333 ----
case OP_BINARY ... OP_BINCMP_END:
kill_use(&insn->src2);
/* fall through */
! case OP_UNOP ... OP_UNOP_END:
case OP_SETVAL:
case OP_SLICE:
kill_use(&insn->src1);
break;
case OP_PHI:
*** 252,332 ****
case OP_PHISOURCE:
kill_use(&insn->phi_src);
break;
case OP_SYMADDR:
repeat_phase |= REPEAT_SYMBOL_CLEANUP;
break;
case OP_CBR:
case OP_COMPUTEDGOTO:
kill_use(&insn->cond);
break;
case OP_CALL:
if (!force) {
/* a "pure" function can be killed too */
if (!(insn->func->type == PSEUDO_SYM))
! return;
if (!(insn->func->sym->ctype.modifiers & MOD_PURE))
! return;
}
kill_use_list(insn->arguments);
if (insn->func->type == PSEUDO_REG)
kill_use(&insn->func);
break;
case OP_LOAD:
! if (!force && insn->type->ctype.modifiers & MOD_VOLATILE)
! return;
kill_use(&insn->src);
break;
case OP_STORE:
if (!force)
! return;
kill_use(&insn->src);
kill_use(&insn->target);
break;
case OP_ENTRY:
/* ignore */
! return;
case OP_BR:
default:
break;
}
insn->bb = NULL;
! repeat_phase |= REPEAT_CSE;
! return;
}
! /*
! * Kill trivially dead instructions
! */
static int dead_insn(struct instruction *insn, pseudo_t *src1, pseudo_t *src2, pseudo_t *src3)
{
! struct pseudo_user *pu;
! FOR_EACH_PTR(insn->target->users, pu) {
! if (*pu->userp != VOID)
return 0;
- } END_FOR_EACH_PTR(pu);
insn->bb = NULL;
kill_use(src1);
kill_use(src2);
kill_use(src3);
return REPEAT_CSE;
}
static inline int constant(pseudo_t pseudo)
{
return pseudo->type == PSEUDO_VAL;
}
static int replace_with_pseudo(struct instruction *insn, pseudo_t pseudo)
{
convert_instruction_target(insn, pseudo);
switch (insn->opcode) {
--- 336,450 ----
case OP_PHISOURCE:
kill_use(&insn->phi_src);
break;
case OP_SYMADDR:
+ kill_use(&insn->src);
repeat_phase |= REPEAT_SYMBOL_CLEANUP;
break;
case OP_CBR:
+ case OP_SWITCH:
case OP_COMPUTEDGOTO:
kill_use(&insn->cond);
break;
case OP_CALL:
if (!force) {
/* a "pure" function can be killed too */
if (!(insn->func->type == PSEUDO_SYM))
! return 0;
if (!(insn->func->sym->ctype.modifiers & MOD_PURE))
! return 0;
}
kill_use_list(insn->arguments);
if (insn->func->type == PSEUDO_REG)
kill_use(&insn->func);
break;
case OP_LOAD:
! if (!force && insn->is_volatile)
! return 0;
kill_use(&insn->src);
break;
case OP_STORE:
if (!force)
! return 0;
kill_use(&insn->src);
kill_use(&insn->target);
break;
case OP_ENTRY:
/* ignore */
! return 0;
case OP_BR:
+ case OP_SETFVAL:
default:
break;
}
insn->bb = NULL;
! return repeat_phase |= REPEAT_CSE;
}
! ///
! // kill trivially dead instructions
static int dead_insn(struct instruction *insn, pseudo_t *src1, pseudo_t *src2, pseudo_t *src3)
{
! if (has_users(insn->target))
return 0;
insn->bb = NULL;
kill_use(src1);
kill_use(src2);
kill_use(src3);
return REPEAT_CSE;
}
+ static inline bool has_target(struct instruction *insn)
+ {
+ return opcode_table[insn->opcode].flags & OPF_TARGET;
+ }
+
+ void remove_dead_insns(struct entrypoint *ep)
+ {
+ struct basic_block *bb;
+
+ FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
+ struct instruction *insn;
+ FOR_EACH_PTR_REVERSE(bb->insns, insn) {
+ if (!insn->bb)
+ continue;
+ if (!has_target(insn))
+ continue;
+ if (!has_users(insn->target))
+ kill_instruction(insn);
+ } END_FOR_EACH_PTR_REVERSE(insn);
+ } END_FOR_EACH_PTR_REVERSE(bb);
+ }
+
static inline int constant(pseudo_t pseudo)
{
return pseudo->type == PSEUDO_VAL;
}
+ ///
+ // replace the operand of an instruction
+ // @insn: the instruction
+ // @pp: the address of the instruction's operand
+ // @new: the new value for the operand
+ // @return: REPEAT_CSE.
+ static inline int replace_pseudo(struct instruction *insn, pseudo_t *pp, pseudo_t new)
+ {
+ pseudo_t old = *pp;
+ use_pseudo(insn, new, pp);
+ remove_usage(old, pp);
+ return REPEAT_CSE;
+ }
+
static int replace_with_pseudo(struct instruction *insn, pseudo_t pseudo)
{
convert_instruction_target(insn, pseudo);
switch (insn->opcode) {
*** 333,349 ****
case OP_SEL:
case OP_RANGE:
kill_use(&insn->src3);
case OP_BINARY ... OP_BINCMP_END:
kill_use(&insn->src2);
! case OP_NOT:
! case OP_NEG:
case OP_SYMADDR:
- case OP_CAST:
- case OP_SCAST:
- case OP_FPCAST:
- case OP_PTRCAST:
kill_use(&insn->src1);
break;
default:
assert(0);
--- 451,462 ----
case OP_SEL:
case OP_RANGE:
kill_use(&insn->src3);
case OP_BINARY ... OP_BINCMP_END:
kill_use(&insn->src2);
! case OP_UNOP ... OP_UNOP_END:
case OP_SYMADDR:
kill_use(&insn->src1);
break;
default:
assert(0);
*** 350,361 ****
}
insn->bb = NULL;
return REPEAT_CSE;
}
! unsigned int value_size(long long value)
{
value >>= 8;
if (!value)
return 8;
value >>= 8;
if (!value)
--- 463,481 ----
}
insn->bb = NULL;
return REPEAT_CSE;
}
! static inline int def_opcode(pseudo_t p)
{
+ if (p->type != PSEUDO_REG)
+ return OP_BADOP;
+ return p->def->opcode;
+ }
+
+ static unsigned int value_size(long long value)
+ {
value >>= 8;
if (!value)
return 8;
value >>= 8;
if (!value)
*** 364,386 ****
if (!value)
return 32;
return 64;
}
! /*
! * Try to determine the maximum size of bits in a pseudo.
! *
! * Right now this only follow casts and constant values, but we
! * could look at things like logical 'and' instructions etc.
! */
static unsigned int operand_size(struct instruction *insn, pseudo_t pseudo)
{
unsigned int size = insn->size;
if (pseudo->type == PSEUDO_REG) {
struct instruction *src = pseudo->def;
! if (src && src->opcode == OP_CAST && src->orig_type) {
unsigned int orig_size = src->orig_type->bit_size;
if (orig_size < size)
size = orig_size;
}
}
--- 484,505 ----
if (!value)
return 32;
return 64;
}
! ///
! // try to determine the maximum size of bits in a pseudo
! //
! // Right now this only follow casts and constant values, but we
! // could look at things like AND instructions, etc.
static unsigned int operand_size(struct instruction *insn, pseudo_t pseudo)
{
unsigned int size = insn->size;
if (pseudo->type == PSEUDO_REG) {
struct instruction *src = pseudo->def;
! if (src && src->opcode == OP_ZEXT && src->orig_type) {
unsigned int orig_size = src->orig_type->bit_size;
if (orig_size < size)
size = orig_size;
}
}
*** 390,410 ****
size = orig_size;
}
return size;
}
! static int simplify_asr(struct instruction *insn, pseudo_t pseudo, long long value)
{
! unsigned int size = operand_size(insn, pseudo);
! if (value >= size) {
! warning(insn->pos, "right shift by bigger than source value");
! return replace_with_pseudo(insn, value_pseudo(insn->type, 0));
}
if (!value)
return replace_with_pseudo(insn, pseudo);
return 0;
}
static int simplify_mul_div(struct instruction *insn, long long value)
{
unsigned long long sbit = 1ULL << (insn->size - 1);
--- 509,929 ----
size = orig_size;
}
return size;
}
! static pseudo_t eval_insn(struct instruction *insn)
{
! /* FIXME! Verify signs and sizes!! */
! unsigned int size = insn->size;
! long long left = insn->src1->value;
! long long right = insn->src2->value;
! unsigned long long ul, ur;
! long long res, mask, bits;
! mask = 1ULL << (size-1);
! bits = mask | (mask-1);
!
! if (left & mask)
! left |= ~bits;
! if (right & mask)
! right |= ~bits;
! ul = left & bits;
! ur = right & bits;
!
! switch (insn->opcode) {
! case OP_ADD:
! res = left + right;
! break;
! case OP_SUB:
! res = left - right;
! break;
! case OP_MUL:
! res = ul * ur;
! break;
! case OP_DIVU:
! if (!ur)
! goto undef;
! res = ul / ur;
! break;
! case OP_DIVS:
! if (!right)
! goto undef;
! if (left == mask && right == -1)
! goto undef;
! res = left / right;
! break;
! case OP_MODU:
! if (!ur)
! goto undef;
! res = ul % ur;
! break;
! case OP_MODS:
! if (!right)
! goto undef;
! if (left == mask && right == -1)
! goto undef;
! res = left % right;
! break;
! case OP_SHL:
! if (ur >= size)
! goto undef;
! res = left << right;
! break;
! case OP_LSR:
! if (ur >= size)
! goto undef;
! res = ul >> ur;
! break;
! case OP_ASR:
! if (ur >= size)
! goto undef;
! res = left >> right;
! break;
! /* Logical */
! case OP_AND:
! res = left & right;
! break;
! case OP_OR:
! res = left | right;
! break;
! case OP_XOR:
! res = left ^ right;
! break;
!
! /* Binary comparison */
! case OP_SET_EQ:
! res = left == right;
! break;
! case OP_SET_NE:
! res = left != right;
! break;
! case OP_SET_LE:
! res = left <= right;
! break;
! case OP_SET_GE:
! res = left >= right;
! break;
! case OP_SET_LT:
! res = left < right;
! break;
! case OP_SET_GT:
! res = left > right;
! break;
! case OP_SET_B:
! res = ul < ur;
! break;
! case OP_SET_A:
! res = ul > ur;
! break;
! case OP_SET_BE:
! res = ul <= ur;
! break;
! case OP_SET_AE:
! res = ul >= ur;
! break;
! default:
! return NULL;
}
+ res &= bits;
+
+ return value_pseudo(res);
+
+ undef:
+ return NULL;
+ }
+
+ ///
+ // Simplifications
+ // ^^^^^^^^^^^^^^^
+
+ ///
+ // try to simplify MASK(OR(AND(x, M'), b), M)
+ // @insn: the masking instruction
+ // @mask: the associated mask (M)
+ // @ora: one of the OR's operands, guaranteed to be PSEUDO_REG
+ // @orb: the other OR's operand
+ // @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
+ static int simplify_mask_or_and(struct instruction *insn, unsigned long long mask,
+ pseudo_t ora, pseudo_t orb)
+ {
+ unsigned long long omask, nmask;
+ struct instruction *and = ora->def;
+ pseudo_t src2 = and->src2;
+
+ if (and->opcode != OP_AND)
+ return 0;
+ if (!constant(src2))
+ return 0;
+ omask = src2->value;
+ nmask = omask & mask;
+ if (nmask == 0) {
+ // if (M' & M) == 0: ((a & M') | b) -> b
+ return replace_pseudo(insn, &insn->src1, orb);
+ }
+ if (multi_users(insn->src1))
+ return 0; // can't modify anything inside the OR
+ if (nmask == mask) {
+ struct instruction *or = insn->src1->def;
+ pseudo_t *arg = (ora == or->src1) ? &or->src1 : &or->src2;
+ // if (M' & M) == M: ((a & M') | b) -> (a | b)
+ return replace_pseudo(or, arg, and->src1);
+ }
+ if (nmask != omask && !multi_users(ora)) {
+ // if (M' & M) != M': AND(a, M') -> AND(a, (M' & M))
+ and->src2 = value_pseudo(nmask);
+ return REPEAT_CSE;
+ }
+ return 0;
+ }
+
+ ///
+ // try to simplify MASK(OR(a, b), M)
+ // @insn: the masking instruction
+ // @mask: the associated mask (M)
+ // @or: the OR instruction
+ // @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
+ static int simplify_mask_or(struct instruction *insn, unsigned long long mask, struct instruction *or)
+ {
+ pseudo_t src1 = or->src1;
+ pseudo_t src2 = or->src2;
+ int rc;
+
+ if (src1->type == PSEUDO_REG) {
+ if ((rc = simplify_mask_or_and(insn, mask, src1, src2)))
+ return rc;
+ }
+ if (src2->type == PSEUDO_REG) {
+ if ((rc = simplify_mask_or_and(insn, mask, src2, src1)))
+ return rc;
+ } else if (src2->type == PSEUDO_VAL) {
+ unsigned long long oval = src2->value;
+ unsigned long long nval = oval & mask;
+ // Try to simplify:
+ // MASK(OR(x, C), M)
+ if (nval == 0) {
+ // if (C & M) == 0: OR(x, C) -> x
+ return replace_pseudo(insn, &insn->src1, src1);
+ }
+ if (nval == mask) {
+ // if (C & M) == M: OR(x, C) -> M
+ return replace_pseudo(insn, &insn->src1, value_pseudo(mask));
+ }
+ if (nval != oval && !multi_users(or->target)) {
+ // if (C & M) != C: OR(x, C) -> OR(x, (C & M))
+ return replace_pseudo(or, &or->src2, value_pseudo(nval));
+ }
+ }
+ return 0;
+ }
+
+ ///
+ // try to simplify MASK(SHIFT(OR(a, b), S), M)
+ // @sh: the shift instruction
+ // @or: the OR instruction
+ // @mask: the mask associated to MASK (M):
+ // @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
+ static int simplify_mask_shift_or(struct instruction *sh, struct instruction *or, unsigned long long mask)
+ {
+ unsigned long long smask = bits_mask(sh->size);
+ int shift = sh->src2->value;
+
+ if (sh->opcode == OP_LSR)
+ mask <<= shift;
+ else
+ mask >>= shift;
+ return simplify_mask_or(sh, smask & mask, or);
+ }
+
+ static int simplify_mask_shift(struct instruction *sh, unsigned long long mask)
+ {
+ struct instruction *inner;
+
+ if (!constant(sh->src2) || sh->tainted)
+ return 0;
+ switch (DEF_OPCODE(inner, sh->src1)) {
+ case OP_OR:
+ if (!multi_users(sh->target))
+ return simplify_mask_shift_or(sh, inner, mask);
+ break;
+ }
+ return 0;
+ }
+
+ static long long check_shift_count(struct instruction *insn, unsigned long long uval)
+ {
+ unsigned int size = insn->size;
+ long long sval = uval;
+
+ if (uval < size)
+ return uval;
+
+ sval = sign_extend_safe(sval, size);
+ sval = sign_extend_safe(sval, bits_in_int);
+ if (sval < 0)
+ insn->src2 = value_pseudo(sval);
+ if (insn->tainted)
+ return sval;
+
+ if (sval < 0 && Wshift_count_negative)
+ warning(insn->pos, "shift count is negative (%lld)", sval);
+ if (sval > 0 && Wshift_count_overflow) {
+ struct symbol *ctype = insn->type;
+ const char *tname;
+ if (ctype->type == SYM_NODE)
+ ctype = ctype->ctype.base_type;
+ tname = show_typename(ctype);
+ warning(insn->pos, "shift too big (%llu) for type %s", sval, tname);
+ }
+ insn->tainted = 1;
+ return sval;
+ }
+
+ static int simplify_shift(struct instruction *insn, pseudo_t pseudo, long long value)
+ {
+ struct instruction *def;
+ unsigned long long mask, omask, nmask;
+ unsigned long long nval;
+ unsigned int size;
+ pseudo_t src2;
+
if (!value)
return replace_with_pseudo(insn, pseudo);
+ value = check_shift_count(insn, value);
+ if (value < 0)
return 0;
+
+ size = insn->size;
+ switch (insn->opcode) {
+ case OP_ASR:
+ if (value >= size)
+ return 0;
+ if (pseudo->type != PSEUDO_REG)
+ break;
+ def = pseudo->def;
+ switch (def->opcode) {
+ case OP_LSR:
+ case OP_ASR:
+ if (def == insn) // cyclic DAG!
+ break;
+ src2 = def->src2;
+ if (src2->type != PSEUDO_VAL)
+ break;
+ nval = src2->value;
+ if (nval > insn->size || nval == 0)
+ break;
+ value += nval;
+ if (def->opcode == OP_LSR)
+ insn->opcode = OP_LSR;
+ else if (value >= size)
+ value = size - 1;
+ goto new_value;
+
+ case OP_ZEXT:
+ // transform:
+ // zext.N %t <- (O) %a
+ // asr.N %r <- %t, C
+ // into
+ // zext.N %t <- (O) %a
+ // lsr.N %r <- %t, C
+ insn->opcode = OP_LSR;
+ return REPEAT_CSE;
+ }
+ break;
+ case OP_LSR:
+ size = operand_size(insn, pseudo);
+ if (value >= size)
+ goto zero;
+ switch(DEF_OPCODE(def, pseudo)) {
+ case OP_AND:
+ // replace (A & M) >> S
+ // by (A >> S) & (M >> S)
+ if (!constant(def->src2))
+ break;
+ mask = bits_mask(insn->size - value) << value;
+ omask = def->src2->value;
+ nmask = omask & mask;
+ if (nmask == 0)
+ return replace_with_pseudo(insn, value_pseudo(0));
+ if (nmask == mask)
+ return replace_pseudo(insn, &insn->src1, def->src1);
+ if (nbr_users(pseudo) > 1)
+ break;
+ def->opcode = OP_LSR;
+ def->src2 = insn->src2;
+ insn->opcode = OP_AND;
+ insn->src2 = value_pseudo(omask >> value);
+ return REPEAT_CSE;
+ case OP_LSR:
+ goto case_shift_shift;
+ case OP_OR:
+ mask = bits_mask(size);
+ return simplify_mask_shift_or(insn, def, mask);
+ case OP_SHL:
+ // replace ((x << S) >> S)
+ // by (x & (-1 >> S))
+ if (def->src2 != insn->src2)
+ break;
+ mask = bits_mask(insn->size - value);
+ goto replace_mask;
+ }
+ break;
+ case OP_SHL:
+ if (value >= size)
+ goto zero;
+ switch(DEF_OPCODE(def, pseudo)) {
+ case OP_AND:
+ // simplify (A & M) << S
+ if (!constant(def->src2))
+ break;
+ mask = bits_mask(insn->size) >> value;
+ omask = def->src2->value;
+ nmask = omask & mask;
+ if (nmask == 0)
+ return replace_with_pseudo(insn, value_pseudo(0));
+ if (nmask == mask)
+ return replace_pseudo(insn, &insn->src1, def->src1);
+ // do not simplify into ((A << S) & (M << S))
+ break;
+ case OP_LSR:
+ // replace ((x >> S) << S)
+ // by (x & (-1 << S))
+ if (def->src2 != insn->src2)
+ break;
+ mask = bits_mask(insn->size - value) << value;
+ goto replace_mask;
+ case OP_OR:
+ mask = bits_mask(size);
+ return simplify_mask_shift_or(insn, def, mask);
+ case OP_SHL:
+ case_shift_shift: // also for LSR - LSR
+ if (def == insn) // cyclic DAG!
+ break;
+ src2 = def->src2;
+ if (src2->type != PSEUDO_VAL)
+ break;
+ nval = src2->value;
+ if (nval > insn->size)
+ break;
+ value += nval;
+ goto new_value;
+ }
+ break;
+ }
+ return 0;
+
+ new_value:
+ if (value < size) {
+ insn->src2 = value_pseudo(value);
+ return replace_pseudo(insn, &insn->src1, pseudo->def->src1);
+ }
+ zero:
+ return replace_with_pseudo(insn, value_pseudo(0));
+ replace_mask:
+ insn->opcode = OP_AND;
+ insn->src2 = value_pseudo(mask);
+ return replace_pseudo(insn, &insn->src1, def->src1);
}
static int simplify_mul_div(struct instruction *insn, long long value)
{
unsigned long long sbit = 1ULL << (insn->size - 1);
*** 412,423 ****
if (value == 1)
return replace_with_pseudo(insn, insn->src1);
switch (insn->opcode) {
! case OP_MULS:
! case OP_MULU:
if (value == 0)
return replace_with_pseudo(insn, insn->src2);
/* Fall through */
case OP_DIVS:
if (!(value & sbit)) // positive
--- 931,941 ----
if (value == 1)
return replace_with_pseudo(insn, insn->src1);
switch (insn->opcode) {
! case OP_MUL:
if (value == 0)
return replace_with_pseudo(insn, insn->src2);
/* Fall through */
case OP_DIVS:
if (!(value & sbit)) // positive
*** 431,547 ****
}
return 0;
}
- static int compare_opcode(int opcode, int inverse)
- {
- if (!inverse)
- return opcode;
-
- switch (opcode) {
- case OP_SET_EQ: return OP_SET_NE;
- case OP_SET_NE: return OP_SET_EQ;
-
- case OP_SET_LT: return OP_SET_GE;
- case OP_SET_LE: return OP_SET_GT;
- case OP_SET_GT: return OP_SET_LE;
- case OP_SET_GE: return OP_SET_LT;
-
- case OP_SET_A: return OP_SET_BE;
- case OP_SET_AE: return OP_SET_B;
- case OP_SET_B: return OP_SET_AE;
- case OP_SET_BE: return OP_SET_A;
-
- default:
- return opcode;
- }
- }
-
static int simplify_seteq_setne(struct instruction *insn, long long value)
{
pseudo_t old = insn->src1;
! struct instruction *def = old->def;
! pseudo_t src1, src2;
int inverse;
int opcode;
if (value != 0 && value != 1)
return 0;
if (!def)
return 0;
inverse = (insn->opcode == OP_SET_NE) == value;
opcode = def->opcode;
switch (opcode) {
! case OP_BINCMP ... OP_BINCMP_END:
// Convert:
// setcc.n %t <- %a, %b
// setne.m %r <- %t, $0
// into:
// setcc.n %t <- %a, %b
// setcc.m %r <- %a, $b
// and similar for setne/eq ... 0/1
! src1 = def->src1;
! src2 = def->src2;
! insn->opcode = compare_opcode(opcode, inverse);
! use_pseudo(insn, src1, &insn->src1);
! use_pseudo(insn, src2, &insn->src2);
remove_usage(old, &insn->src1);
return REPEAT_CSE;
! default:
return 0;
}
}
static int simplify_constant_rightside(struct instruction *insn)
{
long long value = insn->src2->value;
switch (insn->opcode) {
! case OP_OR_BOOL:
! if (value == 1)
return replace_with_pseudo(insn, insn->src2);
goto case_neutral_zero;
case OP_SUB:
if (value) {
insn->opcode = OP_ADD;
! insn->src2 = value_pseudo(insn->type, -value);
return REPEAT_CSE;
}
/* Fall through */
case OP_ADD:
- case OP_OR: case OP_XOR:
- case OP_SHL:
- case OP_LSR:
case_neutral_zero:
if (!value)
return replace_with_pseudo(insn, insn->src1);
return 0;
case OP_ASR:
! return simplify_asr(insn, insn->src1, value);
case OP_MODU: case OP_MODS:
if (value == 1)
! return replace_with_pseudo(insn, value_pseudo(insn->type, 0));
return 0;
case OP_DIVU: case OP_DIVS:
! case OP_MULU: case OP_MULS:
return simplify_mul_div(insn, value);
- case OP_AND_BOOL:
- if (value == 1)
- return replace_with_pseudo(insn, insn->src1);
- /* Fall through */
case OP_AND:
if (!value)
return replace_with_pseudo(insn, insn->src2);
! return 0;
case OP_SET_NE:
case OP_SET_EQ:
return simplify_seteq_setne(insn, value);
}
--- 949,1129 ----
}
return 0;
}
static int simplify_seteq_setne(struct instruction *insn, long long value)
{
pseudo_t old = insn->src1;
! struct instruction *def;
! unsigned osize;
int inverse;
int opcode;
if (value != 0 && value != 1)
return 0;
+ if (old->type != PSEUDO_REG)
+ return 0;
+ def = old->def;
if (!def)
return 0;
inverse = (insn->opcode == OP_SET_NE) == value;
+ if (!inverse && def->size == 1 && insn->size == 1) {
+ // Replace:
+ // setne %r <- %s, $0
+ // or:
+ // seteq %r <- %s, $1
+ // by %s when boolean
+ return replace_with_pseudo(insn, old);
+ }
opcode = def->opcode;
switch (opcode) {
! case OP_AND:
! if (inverse)
! break;
! if (def->size != insn->size)
! break;
! if (def->src2->type != PSEUDO_VAL)
! break;
! if (def->src2->value != 1)
! break;
! return replace_with_pseudo(insn, old);
! case OP_FPCMP ... OP_BINCMP_END:
// Convert:
// setcc.n %t <- %a, %b
// setne.m %r <- %t, $0
// into:
// setcc.n %t <- %a, %b
// setcc.m %r <- %a, $b
// and similar for setne/eq ... 0/1
! insn->opcode = inverse ? opcode_table[opcode].negate : opcode;
! use_pseudo(insn, def->src1, &insn->src1);
! use_pseudo(insn, def->src2, &insn->src2);
remove_usage(old, &insn->src1);
return REPEAT_CSE;
! case OP_SEXT:
! if (value && (def->orig_type->bit_size == 1))
! break;
! /* Fall through */
! case OP_ZEXT:
! // Convert:
! // *ext.m %s <- (1) %a
! // setne.1 %r <- %s, $0
! // into:
! // setne.1 %s <- %a, $0
! // and same for setne/eq ... 0/1
! return replace_pseudo(insn, &insn->src1, def->src);
! case OP_TRUNC:
! if (multi_users(old))
! break;
! // convert
! // trunc.n %s <- (o) %a
! // setne.m %r <- %s, $0
! // into:
! // and.o %s <- %a, $((1 << o) - 1)
! // setne.m %r <- %s, $0
! // and same for setne/eq ... 0/1
! osize = def->size;
! def->opcode = OP_AND;
! def->type = def->orig_type;
! def->size = def->type->bit_size;
! def->src2 = value_pseudo(bits_mask(osize));
! return REPEAT_CSE;
! }
return 0;
+ }
+
+ static int simplify_constant_mask(struct instruction *insn, unsigned long long mask)
+ {
+ pseudo_t old = insn->src1;
+ unsigned long long omask;
+ unsigned long long nmask;
+ struct instruction *def;
+ int osize;
+
+ switch (DEF_OPCODE(def, old)) {
+ case OP_FPCMP ... OP_BINCMP_END:
+ osize = 1;
+ goto oldsize;
+ case OP_OR:
+ return simplify_mask_or(insn, mask, def);
+ case OP_LSR:
+ case OP_SHL:
+ return simplify_mask_shift(def, mask);
+ case OP_ZEXT:
+ osize = def->orig_type->bit_size;
+ /* fall through */
+ oldsize:
+ omask = (1ULL << osize) - 1;
+ nmask = mask & omask;
+ if (nmask == omask)
+ // the AND mask is redundant
+ return replace_with_pseudo(insn, old);
+ if (nmask != mask) {
+ // can use a smaller mask
+ insn->src2 = value_pseudo(nmask);
+ return REPEAT_CSE;
}
+ break;
+ }
+ return 0;
}
static int simplify_constant_rightside(struct instruction *insn)
{
long long value = insn->src2->value;
+ long long sbit = 1ULL << (insn->size - 1);
+ long long bits = sbit | (sbit - 1);
switch (insn->opcode) {
! case OP_OR:
! if ((value & bits) == bits)
return replace_with_pseudo(insn, insn->src2);
goto case_neutral_zero;
+ case OP_XOR:
+ if ((value & bits) == bits) {
+ insn->opcode = OP_NOT;
+ return REPEAT_CSE;
+ }
+ goto case_neutral_zero;
+
case OP_SUB:
if (value) {
insn->opcode = OP_ADD;
! insn->src2 = value_pseudo(-value);
return REPEAT_CSE;
}
/* Fall through */
case OP_ADD:
case_neutral_zero:
if (!value)
return replace_with_pseudo(insn, insn->src1);
return 0;
case OP_ASR:
! case OP_SHL:
! case OP_LSR:
! return simplify_shift(insn, insn->src1, value);
case OP_MODU: case OP_MODS:
if (value == 1)
! return replace_with_pseudo(insn, value_pseudo(0));
return 0;
case OP_DIVU: case OP_DIVS:
! case OP_MUL:
return simplify_mul_div(insn, value);
case OP_AND:
if (!value)
return replace_with_pseudo(insn, insn->src2);
! if ((value & bits) == bits)
! return replace_with_pseudo(insn, insn->src1);
! return simplify_constant_mask(insn, value);
case OP_SET_NE:
case OP_SET_EQ:
return simplify_seteq_setne(insn, value);
}
*** 559,694 ****
return 0;
case OP_SHL:
case OP_LSR: case OP_ASR:
case OP_AND:
! case OP_MULU: case OP_MULS:
if (!value)
return replace_with_pseudo(insn, insn->src1);
return 0;
}
return 0;
}
static int simplify_constant_binop(struct instruction *insn)
{
! /* FIXME! Verify signs and sizes!! */
! long long left = insn->src1->value;
! long long right = insn->src2->value;
! unsigned long long ul, ur;
! long long res, mask, bits;
! mask = 1ULL << (insn->size-1);
! bits = mask | (mask-1);
!
! if (left & mask)
! left |= ~bits;
! if (right & mask)
! right |= ~bits;
! ul = left & bits;
! ur = right & bits;
!
! switch (insn->opcode) {
! case OP_ADD:
! res = left + right;
! break;
! case OP_SUB:
! res = left - right;
! break;
! case OP_MULU:
! res = ul * ur;
! break;
! case OP_MULS:
! res = left * right;
! break;
! case OP_DIVU:
! if (!ur)
return 0;
- res = ul / ur;
- break;
- case OP_DIVS:
- if (!right)
- return 0;
- if (left == mask && right == -1)
- return 0;
- res = left / right;
- break;
- case OP_MODU:
- if (!ur)
- return 0;
- res = ul % ur;
- break;
- case OP_MODS:
- if (!right)
- return 0;
- if (left == mask && right == -1)
- return 0;
- res = left % right;
- break;
- case OP_SHL:
- res = left << right;
- break;
- case OP_LSR:
- res = ul >> ur;
- break;
- case OP_ASR:
- res = left >> right;
- break;
- /* Logical */
- case OP_AND:
- res = left & right;
- break;
- case OP_OR:
- res = left | right;
- break;
- case OP_XOR:
- res = left ^ right;
- break;
- case OP_AND_BOOL:
- res = left && right;
- break;
- case OP_OR_BOOL:
- res = left || right;
- break;
! /* Binary comparison */
! case OP_SET_EQ:
! res = left == right;
! break;
! case OP_SET_NE:
! res = left != right;
! break;
! case OP_SET_LE:
! res = left <= right;
! break;
! case OP_SET_GE:
! res = left >= right;
! break;
! case OP_SET_LT:
! res = left < right;
! break;
! case OP_SET_GT:
! res = left > right;
! break;
! case OP_SET_B:
! res = ul < ur;
! break;
! case OP_SET_A:
! res = ul > ur;
! break;
! case OP_SET_BE:
! res = ul <= ur;
! break;
! case OP_SET_AE:
! res = ul >= ur;
! break;
! default:
! return 0;
! }
! res &= bits;
!
! replace_with_pseudo(insn, value_pseudo(insn->type, res));
return REPEAT_CSE;
}
static int simplify_binop_same_args(struct instruction *insn, pseudo_t arg)
{
--- 1141,1166 ----
return 0;
case OP_SHL:
case OP_LSR: case OP_ASR:
case OP_AND:
! case OP_MUL:
if (!value)
return replace_with_pseudo(insn, insn->src1);
return 0;
}
return 0;
}
static int simplify_constant_binop(struct instruction *insn)
{
! pseudo_t res = eval_insn(insn);
! if (!res)
return 0;
! replace_with_pseudo(insn, res);
return REPEAT_CSE;
}
static int simplify_binop_same_args(struct instruction *insn, pseudo_t arg)
{
*** 698,727 ****
case OP_SET_B: case OP_SET_A:
if (Wtautological_compare)
warning(insn->pos, "self-comparison always evaluates to false");
case OP_SUB:
case OP_XOR:
! return replace_with_pseudo(insn, value_pseudo(insn->type, 0));
case OP_SET_EQ:
case OP_SET_LE: case OP_SET_GE:
case OP_SET_BE: case OP_SET_AE:
if (Wtautological_compare)
warning(insn->pos, "self-comparison always evaluates to true");
! return replace_with_pseudo(insn, value_pseudo(insn->type, 1));
case OP_AND:
case OP_OR:
return replace_with_pseudo(insn, arg);
- case OP_AND_BOOL:
- case OP_OR_BOOL:
- remove_usage(arg, &insn->src2);
- insn->src2 = value_pseudo(insn->type, 0);
- insn->opcode = OP_SET_NE;
- return REPEAT_CSE;
-
default:
break;
}
return 0;
--- 1170,1192 ----
case OP_SET_B: case OP_SET_A:
if (Wtautological_compare)
warning(insn->pos, "self-comparison always evaluates to false");
case OP_SUB:
case OP_XOR:
! return replace_with_pseudo(insn, value_pseudo(0));
case OP_SET_EQ:
case OP_SET_LE: case OP_SET_GE:
case OP_SET_BE: case OP_SET_AE:
if (Wtautological_compare)
warning(insn->pos, "self-comparison always evaluates to true");
! return replace_with_pseudo(insn, value_pseudo(1));
case OP_AND:
case OP_OR:
return replace_with_pseudo(insn, arg);
default:
break;
}
return 0;
*** 763,779 ****
return p2->type == PSEUDO_SYM || p2->type == PSEUDO_VAL;
return 1;
}
! static int simplify_commutative_binop(struct instruction *insn)
{
! if (!canonical_order(insn->src1, insn->src2)) {
switch_pseudo(insn, &insn->src1, insn, &insn->src2);
! return REPEAT_CSE;
! }
return 0;
}
static inline int simple_pseudo(pseudo_t pseudo)
{
return pseudo->type == PSEUDO_VAL || pseudo->type == PSEUDO_SYM;
--- 1228,1254 ----
return p2->type == PSEUDO_SYM || p2->type == PSEUDO_VAL;
return 1;
}
! static int canonicalize_commutative(struct instruction *insn)
{
! if (canonical_order(insn->src1, insn->src2))
! return 0;
!
switch_pseudo(insn, &insn->src1, insn, &insn->src2);
! return repeat_phase |= REPEAT_CSE;
! }
!
! static int canonicalize_compare(struct instruction *insn)
! {
! if (canonical_order(insn->src1, insn->src2))
return 0;
+
+ switch_pseudo(insn, &insn->src1, insn, &insn->src2);
+ insn->opcode = opcode_table[insn->opcode].swap;
+ return repeat_phase |= REPEAT_CSE;
}
static inline int simple_pseudo(pseudo_t pseudo)
{
return pseudo->type == PSEUDO_VAL || pseudo->type == PSEUDO_SYM;
*** 793,803 ****
return 0;
if (def->opcode != insn->opcode)
return 0;
if (!simple_pseudo(def->src2))
return 0;
! if (ptr_list_size((struct ptr_list *)def->target->users) != 1)
return 0;
switch_pseudo(def, &def->src1, insn, &insn->src2);
return REPEAT_CSE;
}
--- 1268,1278 ----
return 0;
if (def->opcode != insn->opcode)
return 0;
if (!simple_pseudo(def->src2))
return 0;
! if (multi_users(def->target))
return 0;
switch_pseudo(def, &def->src1, insn, &insn->src2);
return REPEAT_CSE;
}
*** 811,827 ****
res = ~val;
break;
case OP_NEG:
res = -val;
break;
default:
return 0;
}
mask = 1ULL << (insn->size-1);
res &= mask | (mask-1);
! replace_with_pseudo(insn, value_pseudo(insn->type, res));
return REPEAT_CSE;
}
static int simplify_unop(struct instruction *insn)
{
--- 1286,1311 ----
res = ~val;
break;
case OP_NEG:
res = -val;
break;
+ case OP_SEXT:
+ mask = 1ULL << (insn->orig_type->bit_size-1);
+ if (val & mask)
+ val |= ~(mask | (mask-1));
+ /* fall through */
+ case OP_ZEXT:
+ case OP_TRUNC:
+ res = val;
+ break;
default:
return 0;
}
mask = 1ULL << (insn->size-1);
res &= mask | (mask-1);
! replace_with_pseudo(insn, value_pseudo(res));
return REPEAT_CSE;
}
static int simplify_unop(struct instruction *insn)
{
*** 875,885 ****
}
return 0;
offset:
/* Invalid code */
! if (new == orig) {
if (new == VOID)
return 0;
/*
* If some BB have been removed it is possible that this
* memop is in fact part of a dead BB. In this case
--- 1359,1369 ----
}
return 0;
offset:
/* Invalid code */
! if (new == orig || new == addr) {
if (new == VOID)
return 0;
/*
* If some BB have been removed it is possible that this
* memop is in fact part of a dead BB. In this case
*** 887,909 ****
* If not part of a dead BB this will be redone after
* the BBs have been cleaned up.
*/
if (repeat_phase & REPEAT_CFG_CLEANUP)
return 0;
- new = VOID;
warning(insn->pos, "crazy programmer");
}
insn->offset += off->value;
! use_pseudo(insn, new, &insn->src);
! remove_usage(addr, &insn->src);
return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
}
! /*
! * We walk the whole chain of adds/subs backwards. That's not
! * only more efficient, but it allows us to find loops.
! */
static int simplify_memop(struct instruction *insn)
{
int one, ret = 0;
pseudo_t orig = insn->src;
--- 1371,1394 ----
* If not part of a dead BB this will be redone after
* the BBs have been cleaned up.
*/
if (repeat_phase & REPEAT_CFG_CLEANUP)
return 0;
warning(insn->pos, "crazy programmer");
+ replace_pseudo(insn, &insn->src, VOID);
+ return 0;
}
insn->offset += off->value;
! replace_pseudo(insn, &insn->src, new);
return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
}
! ///
! // simplify memops instructions
! //
! // :note: We walk the whole chain of adds/subs backwards.
! // That's not only more efficient, but it allows us to find loops.
static int simplify_memop(struct instruction *insn)
{
int one, ret = 0;
pseudo_t orig = insn->src;
*** 912,988 ****
ret |= one;
} while (one);
return ret;
}
- static long long get_cast_value(long long val, int old_size, int new_size, int sign)
- {
- long long mask;
-
- if (sign && new_size > old_size) {
- mask = 1 << (old_size-1);
- if (val & mask)
- val |= ~(mask | (mask-1));
- }
- mask = 1 << (new_size-1);
- return val & (mask | (mask-1));
- }
-
static int simplify_cast(struct instruction *insn)
{
! struct symbol *orig_type;
! int orig_size, size;
pseudo_t src;
if (dead_insn(insn, &insn->src, NULL, NULL))
return REPEAT_CSE;
! orig_type = insn->orig_type;
! if (!orig_type)
! return 0;
! /* Keep casts with pointer on either side (not only case of OP_PTRCAST) */
! if (is_ptr_type(orig_type) || is_ptr_type(insn->type))
! return 0;
! orig_size = orig_type->bit_size;
size = insn->size;
! src = insn->src;
! /* A cast of a constant? */
! if (constant(src)) {
! int sign = orig_type->ctype.modifiers & MOD_SIGNED;
! long long val = get_cast_value(src->value, orig_size, size, sign);
! src = value_pseudo(orig_type, val);
! goto simplify;
! }
! /* A cast of a "and" might be a no-op.. */
! if (src->type == PSEUDO_REG) {
! struct instruction *def = src->def;
! if (def->opcode == OP_AND && def->size >= size) {
! pseudo_t val = def->src2;
! if (val->type == PSEUDO_VAL) {
! unsigned long long value = val->value;
! if (!(value >> (size-1)))
! goto simplify;
}
}
}
!
! if (size == orig_size) {
! int op = (orig_type->ctype.modifiers & MOD_SIGNED) ? OP_SCAST : OP_CAST;
! if (insn->opcode == op)
! goto simplify;
! if (insn->opcode == OP_FPCAST && is_float_type(orig_type))
! goto simplify;
}
return 0;
-
- simplify:
- return replace_with_pseudo(insn, src);
}
static int simplify_select(struct instruction *insn)
{
pseudo_t cond, src1, src2;
--- 1397,1548 ----
ret |= one;
} while (one);
return ret;
}
static int simplify_cast(struct instruction *insn)
{
! unsigned long long mask;
! struct instruction *def;
pseudo_t src;
+ pseudo_t val;
+ int osize;
+ int size;
if (dead_insn(insn, &insn->src, NULL, NULL))
return REPEAT_CSE;
! src = insn->src;
! /* A cast of a constant? */
! if (constant(src))
! return simplify_constant_unop(insn);
! // can merge with the previous instruction?
size = insn->size;
! def = src->def;
! switch (def_opcode(src)) {
! case OP_AND:
! val = def->src2;
! if (val->type != PSEUDO_VAL)
! break;
! /* A cast of a AND might be a no-op.. */
! switch (insn->opcode) {
! case OP_TRUNC:
! if (multi_users(src))
! break;
! def->opcode = OP_TRUNC;
! def->orig_type = def->type;
! def->type = insn->type;
! def->size = size;
! insn->opcode = OP_AND;
! mask = val->value;
! mask &= (1ULL << size) - 1;
! insn->src2 = value_pseudo(mask);
! return REPEAT_CSE;
! case OP_SEXT:
! if (val->value & (1 << (def->size - 1)))
! break;
! // OK, sign bit is 0
! case OP_ZEXT:
! if (multi_users(src))
! break;
! // transform:
! // and.n %b <- %a, M
! // *ext.m %c <- (n) %b
! // into:
! // zext.m %b <- %a
! // and.m %c <- %b, M
! // For ZEXT, the mask will always be small
! // enough. For SEXT, it can only be done if
! // the mask force the sign bit to 0.
! def->opcode = OP_ZEXT;
! def->orig_type = insn->orig_type;
! def->type = insn->type;
! def->size = insn->size;
! insn->opcode = OP_AND;
! insn->src2 = val;
! return REPEAT_CSE;
}
+ break;
+ case OP_FPCMP ... OP_BINCMP_END:
+ switch (insn->opcode) {
+ case OP_SEXT:
+ if (insn->size == 1)
+ break;
+ /* fall through */
+ case OP_ZEXT:
+ case OP_TRUNC:
+ // simplify:
+ // setcc.n %t <- %a, %b
+ // zext.m %r <- (n) %t
+ // into:
+ // setcc.m %r <- %a, %b
+ // and same for s/zext/trunc/
+ insn->opcode = def->opcode;
+ use_pseudo(insn, def->src2, &insn->src2);
+ return replace_pseudo(insn, &insn->src1, def->src1);
}
+ break;
+ case OP_OR:
+ switch (insn->opcode) {
+ case OP_TRUNC:
+ mask = bits_mask(insn->size);
+ return simplify_mask_or(insn, mask, def);
}
! break;
! case OP_LSR:
! case OP_SHL:
! if (insn->opcode != OP_TRUNC)
! break;
! mask = bits_mask(insn->size);
! return simplify_mask_shift(def, mask);
! case OP_TRUNC:
! switch (insn->opcode) {
! case OP_TRUNC:
! insn->orig_type = def->orig_type;
! return replace_pseudo(insn, &insn->src1, def->src);
! case OP_ZEXT:
! if (size != def->orig_type->bit_size)
! break;
! insn->opcode = OP_AND;
! insn->src2 = value_pseudo((1ULL << def->size) - 1);
! return replace_pseudo(insn, &insn->src1, def->src);
}
+ break;
+ case OP_ZEXT:
+ switch (insn->opcode) {
+ case OP_SEXT:
+ insn->opcode = OP_ZEXT;
+ /* fall through */
+ case OP_ZEXT:
+ insn->orig_type = def->orig_type;
+ return replace_pseudo(insn, &insn->src, def->src);
+ }
+ /* fall through */
+ case OP_SEXT:
+ switch (insn->opcode) {
+ case OP_TRUNC:
+ osize = def->orig_type->bit_size;
+ if (size == osize)
+ return replace_with_pseudo(insn, def->src);
+ if (size > osize)
+ insn->opcode = def->opcode;
+ insn->orig_type = def->orig_type;
+ return replace_pseudo(insn, &insn->src, def->src);
+ }
+ switch (insn->opcode) {
+ case OP_SEXT:
+ insn->orig_type = def->orig_type;
+ return replace_pseudo(insn, &insn->src, def->src);
+ }
+ break;
+ }
return 0;
}
static int simplify_select(struct instruction *insn)
{
pseudo_t cond, src1, src2;
*** 1017,1026 ****
--- 1577,1592 ----
/* insn->src1 is already cond */
insn->src2 = src1; /* Zero */
return REPEAT_CSE;
}
}
+ if (cond == src2 && is_zero(src1)) {
+ kill_use(&insn->src1);
+ kill_use(&insn->src3);
+ replace_with_pseudo(insn, value_pseudo(0));
+ return REPEAT_CSE;
+ }
return 0;
}
static int is_in_range(pseudo_t src, long long low, long long high)
{
*** 1049,1070 ****
return REPEAT_CSE;
}
return 0;
}
! /*
! * Simplify "set_ne/eq $0 + br"
! */
! static int simplify_cond_branch(struct instruction *br, pseudo_t cond, struct instruction *def, pseudo_t *pp)
{
! use_pseudo(br, *pp, &br->cond);
! remove_usage(cond, &br->cond);
if (def->opcode == OP_SET_EQ) {
! struct basic_block *true = br->bb_true;
! struct basic_block *false = br->bb_false;
! br->bb_false = true;
! br->bb_true = false;
}
return REPEAT_CSE;
}
static int simplify_branch(struct instruction *insn)
--- 1615,1633 ----
return REPEAT_CSE;
}
return 0;
}
! ///
! // simplify SET_NE/EQ $0 + BR
! static int simplify_cond_branch(struct instruction *br, struct instruction *def, pseudo_t newcond)
{
! replace_pseudo(br, &br->cond, newcond);
if (def->opcode == OP_SET_EQ) {
! struct basic_block *tmp = br->bb_true;
! br->bb_true = br->bb_false;
! br->bb_false = tmp;
}
return REPEAT_CSE;
}
static int simplify_branch(struct instruction *insn)
*** 1094,1106 ****
if (cond->type == PSEUDO_REG) {
struct instruction *def = cond->def;
if (def->opcode == OP_SET_NE || def->opcode == OP_SET_EQ) {
if (constant(def->src1) && !def->src1->value)
! return simplify_cond_branch(insn, cond, def, &def->src2);
if (constant(def->src2) && !def->src2->value)
! return simplify_cond_branch(insn, cond, def, &def->src1);
}
if (def->opcode == OP_SEL) {
if (constant(def->src2) && constant(def->src3)) {
long long val1 = def->src2->value;
long long val2 = def->src3->value;
--- 1657,1669 ----
if (cond->type == PSEUDO_REG) {
struct instruction *def = cond->def;
if (def->opcode == OP_SET_NE || def->opcode == OP_SET_EQ) {
if (constant(def->src1) && !def->src1->value)
! return simplify_cond_branch(insn, def, def->src2);
if (constant(def->src2) && !def->src2->value)
! return simplify_cond_branch(insn, def, def->src1);
}
if (def->opcode == OP_SEL) {
if (constant(def->src2) && constant(def->src3)) {
long long val1 = def->src2->value;
long long val2 = def->src3->value;
*** 1111,1139 ****
if (val1 && val2) {
insert_branch(insn->bb, insn, insn->bb_true);
return REPEAT_CSE;
}
if (val2) {
! struct basic_block *true = insn->bb_true;
! struct basic_block *false = insn->bb_false;
! insn->bb_false = true;
! insn->bb_true = false;
}
! use_pseudo(insn, def->src1, &insn->cond);
! remove_usage(cond, &insn->cond);
! return REPEAT_CSE;
}
}
! if (def->opcode == OP_CAST || def->opcode == OP_SCAST) {
! int orig_size = def->orig_type ? def->orig_type->bit_size : 0;
! if (def->size > orig_size) {
! use_pseudo(insn, def->src, &insn->cond);
! remove_usage(cond, &insn->cond);
! return REPEAT_CSE;
}
- }
- }
return 0;
}
static int simplify_switch(struct instruction *insn)
{
--- 1674,1693 ----
if (val1 && val2) {
insert_branch(insn->bb, insn, insn->bb_true);
return REPEAT_CSE;
}
if (val2) {
! struct basic_block *tmp = insn->bb_true;
! insn->bb_true = insn->bb_false;
! insn->bb_false = tmp;
}
! return replace_pseudo(insn, &insn->cond, def->src1);
}
}
! if (def->opcode == OP_SEXT || def->opcode == OP_ZEXT)
! return replace_pseudo(insn, &insn->cond, def->src);
}
return 0;
}
static int simplify_switch(struct instruction *insn)
{
*** 1163,1211 ****
int simplify_instruction(struct instruction *insn)
{
if (!insn->bb)
return 0;
switch (insn->opcode) {
! case OP_ADD: case OP_MULS:
case OP_AND: case OP_OR: case OP_XOR:
! case OP_AND_BOOL: case OP_OR_BOOL:
if (simplify_binop(insn))
return REPEAT_CSE;
- if (simplify_commutative_binop(insn))
- return REPEAT_CSE;
return simplify_associative_binop(insn);
- case OP_MULU:
case OP_SET_EQ: case OP_SET_NE:
! if (simplify_binop(insn))
! return REPEAT_CSE;
! return simplify_commutative_binop(insn);
case OP_SUB:
case OP_DIVU: case OP_DIVS:
case OP_MODU: case OP_MODS:
case OP_SHL:
case OP_LSR: case OP_ASR:
- case OP_SET_LE: case OP_SET_GE:
- case OP_SET_LT: case OP_SET_GT:
- case OP_SET_B: case OP_SET_A:
- case OP_SET_BE: case OP_SET_AE:
return simplify_binop(insn);
! case OP_NOT: case OP_NEG:
return simplify_unop(insn);
! case OP_LOAD: case OP_STORE:
return simplify_memop(insn);
case OP_SYMADDR:
! if (dead_insn(insn, NULL, NULL, NULL))
return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
! return replace_with_pseudo(insn, insn->symbol);
! case OP_CAST:
! case OP_SCAST:
! case OP_FPCAST:
! case OP_PTRCAST:
return simplify_cast(insn);
case OP_PHI:
if (dead_insn(insn, NULL, NULL, NULL)) {
kill_use_list(insn->phi_list);
return REPEAT_CSE;
}
--- 1717,1784 ----
int simplify_instruction(struct instruction *insn)
{
if (!insn->bb)
return 0;
switch (insn->opcode) {
! case OP_ADD: case OP_MUL:
case OP_AND: case OP_OR: case OP_XOR:
! canonicalize_commutative(insn);
if (simplify_binop(insn))
return REPEAT_CSE;
return simplify_associative_binop(insn);
case OP_SET_EQ: case OP_SET_NE:
! canonicalize_commutative(insn);
! return simplify_binop(insn);
+ case OP_SET_LE: case OP_SET_GE:
+ case OP_SET_LT: case OP_SET_GT:
+ case OP_SET_B: case OP_SET_A:
+ case OP_SET_BE: case OP_SET_AE:
+ canonicalize_compare(insn);
+ /* fall through */
case OP_SUB:
case OP_DIVU: case OP_DIVS:
case OP_MODU: case OP_MODS:
case OP_SHL:
case OP_LSR: case OP_ASR:
return simplify_binop(insn);
! case OP_NOT: case OP_NEG: case OP_FNEG:
return simplify_unop(insn);
! case OP_LOAD:
! if (!has_users(insn->target))
! return kill_instruction(insn);
! /* fall-through */
! case OP_STORE:
return simplify_memop(insn);
case OP_SYMADDR:
! if (dead_insn(insn, &insn->src, NULL, NULL))
return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
! return replace_with_pseudo(insn, insn->src);
! case OP_SEXT: case OP_ZEXT:
! case OP_TRUNC:
return simplify_cast(insn);
+ case OP_FCVTU: case OP_FCVTS:
+ case OP_UCVTF: case OP_SCVTF:
+ case OP_FCVTF:
+ case OP_PTRCAST:
+ if (dead_insn(insn, &insn->src, NULL, NULL))
+ return REPEAT_CSE;
+ break;
+ case OP_UTPTR:
+ case OP_PTRTU:
+ return replace_with_pseudo(insn, insn->src);
+ case OP_SLICE:
+ if (dead_insn(insn, &insn->src, NULL, NULL))
+ return REPEAT_CSE;
+ break;
+ case OP_SETVAL:
+ case OP_SETFVAL:
+ if (dead_insn(insn, NULL, NULL, NULL))
+ return REPEAT_CSE;
+ break;
case OP_PHI:
if (dead_insn(insn, NULL, NULL, NULL)) {
kill_use_list(insn->phi_list);
return REPEAT_CSE;
}
*** 1220,1227 ****
--- 1793,1807 ----
return simplify_branch(insn);
case OP_SWITCH:
return simplify_switch(insn);
case OP_RANGE:
return simplify_range(insn);
+ case OP_FADD:
+ case OP_FSUB:
+ case OP_FMUL:
+ case OP_FDIV:
+ if (dead_insn(insn, &insn->src1, &insn->src2, NULL))
+ return REPEAT_CSE;
+ break;
}
return 0;
}